3 ms·

Ooh, let’s do this with the Busy Beaver function too. BB(5) is only 12,289 binary digits to say out loud. BB(6) and BB(7) can’t possibly take that much longer t

Ooh, let’s do this with the Busy Beaver function too. BB(5) is only 12,289 binary digits to say out loud. BB(6) and BB(7) can’t possibly take that much longer to say.

leononame 2y ago
For context, because I had to look it up: For BB(6), Σ(6) is known to be least 10 ↑↑ 15 for in Knuth's up-arrow notation. You can read this as 10^(10 ↑↑ 14) = 10^(10^(10 ↑↑ 13)) and so on. It's much more than just a lot. Anyone know how many digits this is?
- dullcrisp 2y ago
  10 ↑↑ 14
- wruza 2y ago
  That’s why it requires notation in the first place.
aphantastic 2y ago
BB(5) is known to be 47,176,870, or 10110011111101110010100110 in base 2. https://wiki.bbchallenge.org/wiki/BB(5) https://wiki.bbchallenge.org/wiki/BB(5)
- Xcelerate 2y ago
  Yeah, that’s the shift function / number of steps. I’m talking about the length of the contents on the tape when the machine enters a halt state. The notation “BB” is a bit overloaded in the literature.
  - aphantastic 2y ago
    The length of the contents of the tape of any halting TM will be less than or equal to the number of steps it takes to run. Quite trivially: you can’t consume tape without taking a step. For BB(5), 4098 1’s are written to the tape (this is referred to as Σ(5)). As for the length of the contents, I’m not sure, but again you can’t so sume tape without a step, and anecdotally the BBs are generally “back and forth”, at least the Collatz-like ones (which BB(5) is).
    - Xcelerate 2y ago
      Sure, I’m just referring to the fact that there doesn’t seem to be a widespread standard on what “Busy Beaver” refers to in the literature. Scott Aaronson tends to reference the shift function, but older papers consider Σ as the “Busy Beaver function” or the “ones function” as you point out. My number came from running the machine itself and considering the largest contiguous section of output (since you typically start with a tape consisting of infinite zeros). If we think of the nth prime as the output of a Turing machine that computes the prime numbers where n is on the input tape, then if people are saying the output aloud of such a machine, it would make sense to do so similarly here as well. Ultimately, it doesn’t really matter. All these functions basically grow at the same rate asymptotically.

Ooh, let’s do this with the Busy Beaver function too. BB(5) is only 12,289 binary digits to say out loud. BB(6) and BB(7) can’t possibly take that much longer to say.

leononame 2y ago

For context, because I had to look it up: For BB(6), Σ(6) is known to be least 10 ↑↑ 15 for in Knuth's up-arrow notation. You can read this as 10^(10 ↑↑ 14) = 10^(10^(10 ↑↑ 13)) and so on. It's much more than just a lot. Anyone know how many digits this is?

dullcrisp 2y ago
10 ↑↑ 14
wruza 2y ago
That’s why it requires notation in the first place.

aphantastic 2y ago

BB(5) is known to be 47,176,870, or 10110011111101110010100110 in base 2. https://wiki.bbchallenge.org/wiki/BB(5) https://wiki.bbchallenge.org/wiki/BB(5)

Xcelerate 2y ago
Yeah, that’s the shift function / number of steps. I’m talking about the length of the contents on the tape when the machine enters a halt state. The notation “BB” is a bit overloaded in the literature.
- aphantastic 2y ago
  The length of the contents of the tape of any halting TM will be less than or equal to the number of steps it takes to run. Quite trivially: you can’t consume tape without taking a step. For BB(5), 4098 1’s are written to the tape (this is referred to as Σ(5)). As for the length of the contents, I’m not sure, but again you can’t so sume tape without a step, and anecdotally the BBs are generally “back and forth”, at least the Collatz-like ones (which BB(5) is).
  - Xcelerate 2y ago
    Sure, I’m just referring to the fact that there doesn’t seem to be a widespread standard on what “Busy Beaver” refers to in the literature. Scott Aaronson tends to reference the shift function, but older papers consider Σ as the “Busy Beaver function” or the “ones function” as you point out. My number came from running the machine itself and considering the largest contiguous section of output (since you typically start with a tape consisting of infinite zeros). If we think of the nth prime as the output of a Turing machine that computes the prime numbers where n is on the input tape, then if people are saying the output aloud of such a machine, it would make sense to do so similarly here as well. Ultimately, it doesn’t really matter. All these functions basically grow at the same rate asymptotically.