4 ms·

BB(n) involves the class of all n-state 2-symbol Turing machines. Encoding such a machine in binary amounts to encoding each of its n*2 transitions that depend

by tromp 4y ago

BB(n) involves the class of all n-state 2-symbol Turing machines. Encoding such a machine in binary amounts to encoding each of its n*2 transitions that depend on the current state and symbol read. A transition specifies a new symbol to write, a direction to move in (left or right) and a new state to move to, or halt. That takes 1 + 1 + ceil (log (n+1)) bits per transition. So BB(6) machines are described by 12*(2+3) = 60 bits. Instead of Turing machines, one can also take the lambda calculus as model of computation. Sequence A333479 in the Online Encyclopedia of Integer Sequences [1] shows the Busy Beaver for binary lambda calculus as the maximum normal form size of any closed lambda term of size n bits. Using bits instead of states gives a more fine-grained scale of un-computability. The latest BB(6) result suggests a challenge for functional programmers: what's the smallest n for which A333479(n) can be shown at least 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 ? I'm hoping it can be under 60 bits... [1] https://oeis.org/A333479 https://oeis.org/A333479

codeflo 4y ago
I'm interested in that as well. On the other hand, all of that can only account for constant factors (in the limit, I can use some extra states to encode a lambda calculus interpreter in my Turing machine). Even for Turing machines, two symbols tapes might not be the most efficient in terms of BB steps per encoded machine bit. Having said all that, your encoding is a bit wasteful, so let's optimize. ;) First, there's really no need for the encoded states to end on bit boundaries. To give an example, to encode 9 numbers between 0 and 9 (inclusive), you don't need 9*ceil(log2(10))=36 bits, you only need ceil(9*log2(10))=30 bits by treating the digits as a large decimal number and converting that to binary. Second, if you're going to halt anyway, there's no need (at least for the BB problem) to write a symbol and move the tape on the last transition, so we can simply treat that as an alternative to encoding a transition. Armed with both of those, the size of an encoded machine goes down to ceil(2 * 6 * log2(2 * 2 * 6 + 1)) = 56 bits. (In general for n states and k symbols, ceil(k * n * log2(2 * k * n + 1)). The 2 is for the directions, the + 1 is the halting transition.)
- tromp 4y ago
  Yes, it's a bit wasteful. But importantly, it's straightforward, and it's what efficient universal Turing Machines would use in their input, so it makes sense for a comparison. Even the binary lambda coding allows for some optimization, like coding for variable 2 at depth 2 as 111 rather than 1110 since an occurrence of variable >= 3 would not make the term closed. > so we can simply treat that as an alternative to encoding a transition That's fine for the shift number but a lot of BB research concerns the number of 1s written rather than the number of steps taken, and there it matters. They prefer to use a single model for all variants.
shwestrick 4y ago
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?
- shwestrick 4y 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?)
  - tromp 4y ago
    > 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)))).
- tromp 4y ago
  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.
tromp 4y ago
Actually it is well under 60 bits! We have A333479(53) exceeding an exponential tower of 256 2s [1]. We also have A333479(114) exceeding Graham's number, which would require a 10-state TM to remain competitive. [1] https://mathoverflow.net/questions/353514/whats-the-smallest-lambda-calculus-term-not-known-to-have-a-normal-form https://mathoverflow.net/questions/353514/whats-the-smallest...

by tromp 4y ago

codeflo 4y ago

I'm interested in that as well. On the other hand, all of that can only account for constant factors (in the limit, I can use some extra states to encode a lambda calculus interpreter in my Turing machine). Even for Turing machines, two symbols tapes might not be the most efficient in terms of BB steps per encoded machine bit. Having said all that, your encoding is a bit wasteful, so let's optimize. ;) First, there's really no need for the encoded states to end on bit boundaries. To give an example, to encode 9 numbers between 0 and 9 (inclusive), you don't need 9*ceil(log2(10))=36 bits, you only need ceil(9*log2(10))=30 bits by treating the digits as a large decimal number and converting that to binary. Second, if you're going to halt anyway, there's no need (at least for the BB problem) to write a symbol and move the tape on the last transition, so we can simply treat that as an alternative to encoding a transition. Armed with both of those, the size of an encoded machine goes down to ceil(2 * 6 * log2(2 * 2 * 6 + 1)) = 56 bits. (In general for n states and k symbols, ceil(k * n * log2(2 * k * n + 1)). The 2 is for the directions, the + 1 is the halting transition.)

tromp 4y ago
Yes, it's a bit wasteful. But importantly, it's straightforward, and it's what efficient universal Turing Machines would use in their input, so it makes sense for a comparison. Even the binary lambda coding allows for some optimization, like coding for variable 2 at depth 2 as 111 rather than 1110 since an occurrence of variable >= 3 would not make the term closed. > so we can simply treat that as an alternative to encoding a transition That's fine for the shift number but a lot of BB research concerns the number of 1s written rather than the number of steps taken, and there it matters. They prefer to use a single model for all variants.

shwestrick 4y ago

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?

shwestrick 4y 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?)
- tromp 4y ago
  > 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)))).
tromp 4y ago
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.

tromp 4y ago

Actually it is well under 60 bits! We have A333479(53) exceeding an exponential tower of 256 2s [1]. We also have A333479(114) exceeding Graham's number, which would require a 10-state TM to remain competitive. [1] https://mathoverflow.net/questions/353514/whats-the-smallest-lambda-calculus-term-not-known-to-have-a-normal-form https://mathoverflow.net/questions/353514/whats-the-smallest...