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

Tim_Tyler comments on Complex Novelty - Less Wrong

26 Post author: Eliezer_Yudkowsky 20 December 2008 12:31AM

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

Comments (65)

Sort By: Old

You are viewing a single comment's thread.

Comment author: Tim_Tyler 20 December 2008 01:39:01AM 0 points [-]

The Busy Beaver problem is uncomputable - there is no fixed Turing machine that computes it for all N - because if you knew all the Busy Beaver numbers, you would have an infallible way of telling whether a Turing machine halts; just run it up for as long as the longest-running Turing machine of that size.

Hmm. The Busy Beaver functions only deal with the case of a TM with a blank tape. Have an arbitrary starting configuration on the tape, and TMs can run for much longer.

The halting problem normally deals with arbitrary input configurations: "Alan Turing proved in 1936 that a general algorithm to solve the halting problem for all possible program-input pairs cannot exist".