[shwestrick]

Interesting. Is there a good motivation for using maximum normal form size, instead of number of steps (e.g. under left-to-right eager evaluation)? My first impression is that A333479(n) is not immediately comparable to BB(n), because of measuring size instead of steps.

EDIT: Oh, perhaps there's multiple common definitions for Turing machine busy beaver? Doing some searches, I've seen both (1) number of steps, and (2) number of 1s on the tape when it halts. Perhaps the second notion is more directly comparable to maximum normal form sizes of lambda terms?

[tromp]

I wanted to have a definition that's independent of evaluation strategy, and thus somewhat more robust. It also makes it easier to comprehend and verify results, such as a(36) corresponding to Church numeral n=2^2^2^3, of size 5*n+6 bits, where I would have a hard time figuring out how long a left-to-right eager evaluation would take. That is indeed closer to the conventional definition of BB(n) as number of consecutive 1s on output on halting.

[shwestrick]

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?)

[tromp]

> Does it make sense to compare BB(n) against A333479(n)?

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)))).