From the link:
That means that we can’t actually prove that a proof doesn’t exist, or it creates a paradox. But we did prove it! And the reasoning is sound! Either H returns true, or false, or loops forever. The first two options can’t be true, on pain of paradox. Leaving only the last possibility. But if we can prove that, so can H. And that itself creates a paradox.
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 proves that it can't decide the question one way or the other.
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 not H.
The point is that the behavior of H is paradoxical. We can prove that it can't return true or false without contradiction. But if that's provable, that also creates a contradiction, since H can prove it to.
Not only can H not decide, but we can't decide whether or not H will de...
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.