Comment by qrendel

11 years ago

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.