I’ve seen explanations about this, but I don’t see how will the program run in the first place. Example program that will be fed to itself:
define haltOrLoop(P):
if halt(P): loop forever
else: exit
If we run `haltOrLoop(haltOrLoop)` wouldn’t that be incomplete as `haltOrLoop` (the one inside the parenthesis) needs a program to run first?
In: 2
The point is we can’t solve the Halting Problem with computers. Computers can’t tell the difference between “a program that is running for a long time” and “a program that cannot ever finish”.
What you did is called “infinite recursion”, and on a real computer it causes a problem called “stack overflow”. But when we’re being computer scientists and talking about Turing Machines, they have infinite memory. You can’t stack overflow with infinite memory, but you will keep using more and more memory forever.
The point of this exercise is to showcase it’s not simple to write `halt(P)` that works for all `P`, because we just wrote a program `P` that cannot be properly evaluated by `halt(P)`.
It’s easy to propose a solution to this case, but real-life infinite recursions are often more subtle and more difficult to detect. Stack overflows don’t really mean that the program can’t finish, they just mean a program has taken so many iterations to complete it’s hit the finite memory bounds of the computer. For example, a recursive AI for a chess program may take what looks like “the same steps” millions of times yet still find a move to make.
Humans can figure this out because we can use intuition and make non-deterministic decisions. Computers (at least not Turing Machines) can’t do this so they cannot reliably distinguish “does the same things very often” from “an infinite loop”. THAT is core of the halting problem.
Latest Answers