Less Wrong is a community blog devoted to refining the art of human rationality. Please visit our About page for more information.

orthonormal comments on Nonperson Predicates - Less Wrong

29 Post author: Eliezer_Yudkowsky 27 December 2008 01:47AM

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

Comments (175)

Sort By: Old

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

Comment author: orthonormal 13 May 2011 03:19:44PM 3 points [-]

The halting problem doesn't imply that we can never tell whether a particular program halts without actually running it. (You can think of many simple programs which definitely halt, and other simple programs which are definitely infinite loops.)

It means, instead, that there exist relatively short but extremely pathological Turing machines, such that no Turing machine can be built that could solve the halting problem for every Turing machine. (Indeed, the idea of the proof is that a reputed halting-problem-solver is itself pathological, as can be seen by feeding it a modified version of itself as input.)

But these pathological ones are not at all the kind of Turing machines we would create to do any functional task; the only reason I could think for us to seek them out would be to find Busy Beaver numbers.