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 problemnormally 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”.
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”.