You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

Epictetus comments on Open Thread - Aug 24 - Aug 30 - Less Wrong Discussion

7 Post author: Elo 24 August 2015 08:14AM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Article Navigation

Comments (318)
Tags: open_thread

Comments (318)

You are viewing a single comment's thread. Show more comments above.

Comment author: Epictetus 27 August 2015 01:33:05AM 0 points [-]

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.

Comment author: Houshalter 27 August 2015 02:04:40AM *  0 points [-]

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 decide. Because we aren't outside the system, and the same logic applies to us.

Comment author: Epictetus 27 August 2015 02:19:17AM *  0 points [-]

I did overlook the definition of H. Apologies.

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.

More precisely, H will encounter a proof that the question is undecidable. It then runs into the following two if statements:

if check_if_proof_proves_x_halts(proof, x, i)

if check_if_proof_proves_x_doesnt_halt(proof, x, i)

Both return "false", so H moves into the next iteration of the while loop. H will generate undecidability proofs, but as implemented it will merely discard them and continue searching. Since such proofs do not cause H to halt, and since there are no proofs that the program halts or does not, then H will run forever.

Comment author: Houshalter 29 August 2015 08:30:20PM 1 point [-]

If it is undecidable, then that means no proof exists (that H will or will not halt.)

If no proof exists, then H will loop forever searching for one.

Therefore undecidability implies H will run forever. You've just proved this.

Therefore a proof exists that H will run forever (that one), and H will eventually find it.

Paradox...

Comment author: entirelyuseless 30 August 2015 02:44:53PM 2 points [-]

As people have been saying, if H can make this argument it is inconsistent and does not work properly (i.e. it does not return True or False in the correct situations.)

Powered by Reddit Powered by Reddit