Comment by viraptor
11 years ago
It's impossible to compute them - sure. But the claim was that: "The sequence of Busy Beaver numbers, BB(1), BB(2), and so on, grows faster than any computable sequence."
The explanation was that: "Because if a Turing machine could compute a sequence that grows faster than Busy Beaver, then it could use that sequence to obtain the D‘s—the beaver dams." But these goals seem different to me.
Another sequence you cannot compute is "foo(x)" - the number of integers lower than x for which algorithm "bar(x)" doesn't halt. It's impossible to compute if "bar(x)" doesn't always halt. But the sequence cannot grow faster than "x" itself.
Also, it doesn't matter that you cannot compute them if every TM of a given size can be analysed and proven halting. It doesn't have to be computed (as in, automatically checked).
The fact you can compute A(x) would only be an issue if you could compute A(x) with a machine of size smaller than x.
I think you are missing some basic concepts here. There is a single Turing machine (of constant size) which, when given any integer n, outputs A(n). This is the statement that A(n) is computable. One can prove that there is no such Turing machine for the function BB(n) or any function f(n) that bounds BB(n). Such a function would be used to solve the Halting problem as follows: given a TM M and a string x, compute k = f(|M|) and run the TM on x for k steps. If the simulation halts within k steps, output "halt" and otherwise output "loops forever."
Your example of foo/bar(x) is not quite correct. If you fix a program bar, then it is not necessarily impossible to characterize (and hence compute) the set of strings for which bar(x) halts. This is not the statement of the Halting problem, and as far as I know there is no theorem that says such a function "bar" exists.
Sure it does, just let "bar" be a UTM.
Good point. My stupid mistake.
Here's a proof I came up with a few days ago (and it became relevant so quickly!)
Assume by contradiction that there is a computable function f that grows faster than the busy beaver problem. We can then make a Turing Machine that takes input n, calculates f(n), and then constructs and simulates every n-state Turing Machine for f(n) steps. Since f grows faster than the number of steps the most productive TM would take, any simulated machine in not in the halt state would never halt, and we could select the busiest beaver out of the remaining Turing Machines. We have constructed a TM that computes the busy beaver problem, which is a contradiction. Thus, there can be no computable function that grows faster than the busy beaver function.