If it's worth saying, but not worth its own post (even in Discussion), then it goes here.
Notes for future OT posters:
1. Please add the 'open_thread' tag.
2. Check if there is an active Open Thread before posting a new one. (Immediately before; refresh the list-of-threads page before posting.)
3. Open Threads should be posted in Discussion, and not Main.
4. Open Threads should start on Monday, and end on Sunday.
From the link:
H proves that it can't decide the question one way or the other. The assumption that H can only return TRUE or FALSE is flawed: if a proof exists that something is undecidable, then H would need to be able to return "undecidable".
This example seems to verify the halting problem: you came up with an algorithm that tries to decide whether a program halts, and then came up with an input for which the algorithm can't decide one way or another.
H
is literally defined as either returning true or false. Or it can run forever, if it can't find a proof. It's possible to create another program which does return "UNDECIDABLE" sometimes. But that is notH
.The point is that the behavior of
H
is paradoxical. We can prove that it can't returntrue
orfalse
without contradiction. But if that's provable, that also creates a contradiction, sinceH
can prove it to.Not only can
H
not decide, but we can't decide whether or notH
will de... (read more)