|
|
|
|
|
|
by shwestrick
1393 days ago
|
|
|
Follow-up question, assuming we define BB(n) = max number of 1s written to tape for a halting machine of n states. Does it make sense to compare BB(n) against A333479(n)? It seems like A333479(n) grows much faster... my mind is jumping to the classic "problem" of being able to construct a lambda term of size O(2^n) using only O(n) steps. For a Turing machine, writing a symbol requires at least one step. But for lambda, you can generate large terms very quickly. (Of course, this isn't a fundamental issue with lambda calculus, and there are other notions of size that are more "realistic". But focusing on just lambda calculus normal form sizes, how do we resolve this?) |
|
|
No, for proper comparison both should measure the argument size in bits. That's why my top comment talks about the number of bits needed to encode an n-state TM in a straightforward manner.
So compare BB(n) with A333479(n*2*(2+ceil(log(n+1)))).