zlacker

>>jeremy+(OP)
I don't get why the BB(x) numbers should grow faster than A(x). They're harder to compute - true. They're more difficult to prove right - true. But I cannot find anything in the article that proves it actually grows faster than Ackerman numbers.

Unless you can always program A(x) in less than x steps on a Turing machine?

>>virapt+ot
No, BB is impossible to compute (as a sequence, that is). A(x) is not.

>>j2kun+zt
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.

>>virapt+9u
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.