The Halting problem – Given a program/algorithm will ever halt or not?
Halting means that the program on certain input will accept it and halt or reject it
and halt and it would never go into an infinite loop. Basically halting means terminating. So
can we have an algorithm that will tell that the given program will halt or not. In terms of
Turing machine, will it terminate when run on some machine with some particular given
input string.
The answer is no we cannot design a generalized algorithm which can appropriately
say that given a program will ever halt or not?
The only way is to run the program and check whether it halts or not.
We can refrain the halting problem question in such a way also: Given a program written in
some programming language(c/c++/java) will it ever get into an infinite loop(loop never
stops) or will it always terminate(halt)?
This is an undecidable problem because we cannot have an algorithm which will tell
us whether a given program will halt or not in a generalized way i.e by having specific
program/[Link] general we can’t always know that’s why we can’t have a general
[Link] best possible way is to run the program and see whether it halts or [Link] this
way for many programs we can see that it will sometimes loop and always halt.
Proof by Contradiction –
Problem statement: Can we design a machine which if given a program can find out if that
program will always halt or not halt on a particular input?
Solution:
Let us assume that we can design that kind of machine called as HM(P, I) where HM
is the machine/program, P is the program and I is the input. On taking input the both
arguments the machine HM will tell that the program P either halts or not.
If we can design such a program this allows us to write another program we call this
program CM(X) where X is any program(taken as argument) and according to the definition
of the program CM(X) shown in the figure.
In the program CM(X) we call the function HM(X), which we have already defined
and to HM() we pass the arguments (X, X), according to the definition of HM() it can take
two arguments i.e one is program and another is the [Link] in the second program we
pass X as a program and X as input to the function HM().We know that the program HM()
gives two output either “Halt” or “Not Halt”.But in case second program, when HM(X, X) will
halt loop body tells to go in loop and when it doesn’t halt that means loop, it is asked to
return.
Now we take one more situation where the program CM is passed to CM() function
as an argument. Then there would be some impossibility, i.e., a condition arises which is not
possible.
It is impossible for outer function to halt if its code (inner body) is in loop and also it is
impossible for outer non halting function to halt even after its inner code is halting. So the both
condition is non halting for CM machine/program even we had assumed in the beginning that it
would [Link] this is the contradiction and we can say that our assumption was wrong and this
problem, i.e., halting problem is undecidable.
This is how we proved that halting problem is undecidable.