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
1) If you're aware of the BB_n hierarchy, you've outgrown the need for recursion tricks. Instead, talk about halting times of programs that can make calls to the oracle F(n,m)=BB_n(m). That leaves any Ackermann-like approach in the dust. I leave it to you to come up with an even better approach (yes, it exists, and then there's one or two levels after that). Please don't say "I'll just use Ackermann on top of your idea", at that level it's the moral equivalent of "your number plus one".

2) For each individual BB number, there's a program that prints it. But there's no program that prints the whole infinite sequence of BB numbers one by one. All finite sequences are computable, but not all infinite sequences are.