wedrifid comments on Rationality Quotes: October 2009 - Less Wrong

7 Post author: Eliezer_Yudkowsky 22 October 2009 04:06PM

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

Article Navigation

Comments (276)
Tags: quotes

Comments (276)

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

Comment author: wedrifid 02 November 2009 10:54:56AM 0 points [-]

It can only be solved in that a correct answer can be given; there are some Turing machines that do not halt for which there is no proof that they do not halt.

Prove it.

Comment author: [deleted] 02 November 2009 11:16:40AM 1 point [-]

Suppose that for every Turing machine that does not halt, there is a proof that it does not halt. It is pretty obvious that if a Turing machine does halt, there is a proof that it does. Therefore, for every Turing machine, either it halts or it doesn't, and there is a proof of this. Therefore, the following method constitutes a halting oracle: Go through every possible proof. For each proof P, if P is a proof that the machine in question halts, finish and return YES; if P is a proof that the machine in question does not halt, finish and return NO; otherwise, go on to the next proof. This is contradicts the fact that there are no halting oracles, so the supposition is false.

Comment author: wedrifid 02 November 2009 11:49:18AM 0 points [-]

This is contradicts the fact that there are no halting oracles, so the supposition is false.

What is it about this algorithm that makes calling it an oracle prove it doesn't halt? Oracles (as I understand them, at least) can be created (or assumed) to solve all sorts of problems, from trivial to unsolvable.

Comment author: [deleted] 02 November 2009 12:26:19PM 4 points [-]

Uh, let me try that again.

  • (1) Suppose that for every Turing machine that does not halt, there is a proof that it does not halt.
  • (2) We know that for every Turing machine that halts, there is a proof that it halts.
  • (3) For every Turing machine, there is either a proof that it halts or a proof that it does not halt. (by (1) and (2))
  • (4) We know that the set of all proofs is recursively enumerable, i.e. there is a program that outputs all proofs.
  • (5) We know that, given a proof, it is possible to determine whether it proves that a Turing machine halts, and whether it proves that a Turing machine does not halt.
  • (6) The set of all proofs that a Turing machine halts, and the set of all proofs that a Turing machine does not halt, are both recursively enumerable. (by (4) and (5))
  • (7) The set of all Turing machines that halt, and the set of all Turing machines that do not halt, are both recursively enumerable. (by (3) and (6))
  • (8) There is a program that determines, given a Turing machine, whether it halts or not. (by (7))

(8) contradicts what we already know, so our supposition, (1), must be false.

Comment author: wedrifid 02 November 2009 12:36:57PM *  0 points [-]

I follow (1) and grant (2). (3) Follows from (1) and (2).

(4) We know that the set of all proofs is recursively enumerable, i.e. there is a program that outputs all proofs.

Are you asserting that the set of proofs is finite? This would surprise me but seems to be required for (8) to contradict what I know.

Comment author: [deleted] 02 November 2009 12:43:07PM 0 points [-]

No, the set of proofs is infinite. There is a program that outputs all proofs; it's just that it takes forever to do so.

Comment author: RobinZ 02 November 2009 03:04:36PM 1 point [-]

...but a finite amount of time to output any specific proof off the list.

Powered by Reddit Powered by Reddit