Comment by mstoehr
11 years ago
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.
And just to be clear here, this isn't just because it can't recognize which numbers are the Busy Beavers as it arrives at them while summing ones indefinitely? If T(N) tries to compute BB(N) by summing ones then, since BB(N) is finite, then it just fails to halt? But then there would be finite numbers that can't be described as the sum of one from 0 to BB(N)? It's just hard to reconcile the concept of indefinite-but-finite running time, all numbers being able to be expressed as a sum of ones, and the BB sequence still not being computable.
Edit: Ah wait, I get it now. Misunderstanding was in confusing "Turing machine" with "universal Turing machine." Any given T(N) will have a finite number of steps it can complete before halting, and since a universal Turing machine or equivalent (e.g. rule 110) can emulate any arbitrary Turing machine, I was modeling it as just letting an arbitrary UTM run forever. But the UTM is just emulating a specific T(N) each time, and you'd have to keep going up emulating different machines for each N to get to each next BB without running out of steps. So you can write programs to calculate arbitrary BBs indefinitely, but no single program to calculate them all. Hence the infinite sequence is noncomputable despite any finite length of it being computable. Thanks for the point in the right direction.