zlacker

>>jeremy+(OP)
1) My submission: modifying Ackermann's function to describe a sequence of Busy Beaver numbers of sequential hypercomputation systems. E.g. ABB(n+1) = BB_n(n) Of course it's the same problem, you could just as easily do AABB(n+1) = ABB_n(n), but still grows faster than a Busy Beaver sequence for any single level of the hypercomputation hierarchy.

2) Question: I understand the argument for noncomputability of Busy Beavers given, but couldn't you just argue that BB(n) is finite, therefore BB(n) is a computable sum of 1+1+...+1, therefore BB(n) is computable given a finite amount of time, so any given number in the sequence is itself computable, therefore by mathematical induction all elements in the sequence are computable? Clearly not, but I don't understand why this doesn't work.

>>qrende+y01
To say that the sequence is computable means that you must present a Turing machine, call it T, that will produce BB(n) in finitely many steps after taking input n. Our specific Turing machine T will have a fixed number of rules call it N rules, then by the definition of the Busy Beaver T(N+1) <= BB(N) = T(N) but BB(N+1) > BB(N) so T(N+1) does not compute BB(N+1). The flaw in your inductive proof is that you have shown there is a Turing machine that can compute BB(N) for each N, but you haven't shown that the same Turing machine can compute all numbers in the sequence.