Tim_Tyler comments on Complex Novelty - Less Wrong
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (65)
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".