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.