|
> How does a simple Python program, that one cannot determine whether it halts or not, look? That's not exactly the right way to look at it. The better way to think of it is to say: for every potential solution to the halting problem, there is a program for which that solution doesn't work. So what the counterexample looks like will depend on your proposed halting problem decider. Let's imagine your wrote a function "halts(program)" that takes a program as input and returns whether that program halts or not. Let's also for simplicity assume that the program input is just the string representation of the source code in e.g. Python. And let's ignore programs that depend on arguments for now. Now write the following program, let's call it X: if halts(X):
while true:
pass
it might seem strange to see the value X, which is supposed to be the string value of the source of the whole program, appear within X. In fact, this seems impossible at first. However, with some clever tricks, you can actually always do that, at least in a turing complete language (including Turing Machines themselves).now, what is the response of "halts(X)"? (remember: X is just the source code of the program above) Well, let's first assume that X is a program that halts. Then, wenn we run X, it checks whether it itself halts. Since it does, it then goes into an infinite loop... wait, but then halts can't be right, since it told us X would halt, but it doesn't. If we assume that X doesn't halt, then conversely, X checks itself, finds out it doesn't halt and then... halts. Another contradiction. This proves that the function "halts" cannot actually be written, for if it could, it would immediately give the wrong answer for this program X. The central argument is, in principle, not more complex than what I've shown. The actual complexity of the proof comes from the whole self-referentiality argument, namely that we can actually embed X within itself. This is quite non-trivial, since we have to prove it in the general case. |
When I first read about it years ago, I mistakenly assumed it was ‘deeper’ or more profound.
But, at the end of the day, it is just a variant in the old “This Sentence Is False” riddle you’d encounter as a kid.
Papers on the topic are frequently spruced up with complicated gibberish... but, unless we are both missing something fundamental, it’s really as simple as set forth in your post.