Houshalter comments on Open Thread - Aug 24 - Aug 30 - Less Wrong

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: 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