4 ms·

The new BB(3,4) record holder is 0 1 2 3 A 1RB 3LB 1RZ 2RA B 2LC 3RB 1LC 2RA C 3RB 1LB 3LC 2RC with the triple (t',d, s') in

by tromp 2y ago

The new BB(3,4) record holder is 0 1 2 3 A 1RB 3LB 1RZ 2RA B 2LC 3RB 1LC 2RA C 3RB 1LB 3LC 2RC with the triple (t',d, s') in row s column t specifying the transition from state s with symbol t under the tape head. the machine overwrites symbol t with t', moves the tape Left/Right according to direction d, and changes state from s to s', halting if s'==Z. This is 3*4*log2(4*2*log2(4+1)) or about 64 bits of information. Meanwhile, in only 49 bits, BBλ(49) far exceeds Graham's number [1]. [1] https://oeis.org/A333479 https://oeis.org/A333479

nilstycho 2y ago
Can you help me understand the log2(4+1) term? I calculate 3*4*log2(4*2*log2(4+1)) ≈ 51. I (a layperson) would have thought the calculation would be 3*4*log2(4*2*4) = 60. Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?
- tromp 2y ago
  I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.
  - im3w1l 2y ago
    You also need to subtract some bits from symmetries right? Like you can mirror the tape. You can relabel states B and C. And you can relabel symbols 1, 2, 3. Though the analysis is complicated a little bit by the fact that some (combinations) of those operations may yield the exact same machine.
    - nilstycho 2y ago
      Also, is there any sense in restricting the universe of machines to those that include one and only one halting symbol? Machines with more or fewer than one halting symbol are possible, but they're less interesting, right?
      - LegionMammal978 2y ago
        If you mean multiple halting transitions, then it doesn't really help for BB purposes. If the machine does halt, then only one of the halting transitions will ever be taken, and the others will be 'dead code'. If you mean multiple halting states, then that is possible, and it can be used as a model of computation for, e.g., computable functions returning a single bit as output. But you still don't gain any additional running time before the machine halts. As for no halting transitions, the problem is choosing what point to measure the tape at. One thing you can do is to put a mark on one of the transitions, then see whether the machine only runs that transition a finite number of times, or if it keeps running it forever. This yields the "Beeping Busy Beaver" numbers [0], which are uncomputable even if you have an oracle for the halting problem. [0] https://www.sligocki.com/2021/03/06/beeping-busy-beaver/ https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
        nilstycho 2y ago
        What I mean is that instead of measuring the bits of a particular program BB(n,k), we could instead define a function BBWOHT(n,k) ("Busy Beaver With One Halting Transition"), and measure the bits of a particular BBWOHT(n,k) program, which would be fewer bits than in the equivalent BB(n,k) program. Perhaps this is semantic games, but I'm trying to get at the idea that while there may be 60 bits of information in the BB(3,4) program, there are fewer in the BBWOHT(3,4) program, because we can prima facie exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BBWOHT(n,k), in the same way that we can exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BB(n,k) programs that aren't symmetries of other BB(n,k) programs.
        tromp 2y ago
        There are many inefficiencies in Turing Machines which you could try to work around with increasingly complicated encodings. But that will never yield a provably optimal machine encoding such as you can obtain with BBλ2 [1]. [1] https://oeis.org/A361211 https://oeis.org/A361211
    - tromp 2y ago
      Only if you want to count the number of different possible TM behaviours. The official count of BB TMs as given in OEIS sequence A052200 ignores such symmetries. [1] https://oeis.org/A052200 https://oeis.org/A052200
sligocki 2y ago
Counting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of the bits needed to describe an arbitrary TM. for the BB(3, 4) case, there are only about 600B distinct TMs using the Tree Normal Form aka Brady's algorithm (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) which comes out to <40 bits.
- tromp 2y ago
  Similarly, 2^n would be a huge overcount of the number of n-bit closed terms, which is given by OEIS sequence A114852 [1]. There are 36140122614 ~ 2^35 closed terms of size 49 bits (length of a straightforward self-delimiting encoding). So in that sense it's still a smaller lambda term computing an incomprehensibly larger output. [1] https://oeis.org/A114852 https://oeis.org/A114852
- jonahx 2y ago
  Do you know of any (hand-wavy is ok) intuitive explanation for why this machine will halt, beyond the inductive proof's given in your article? Just watching the machine run, I would guess at some kind of infinite behavior. It is remarkable that this is not the case.
  - addaon 2y ago
    > Do you know of any (hand-wavy is ok) intuitive explanation for why this machine will halt, beyond the inductive proof's given in your article? If the Halting problem could be solved by intuition, it wouldn't be much of a problem.
    - jonahx 2y ago
      Yet in this case there is a proof that it halts, and that proof contains an argument. I was asking for an explanation of the essence of that argument, if simplifying it is possible.
Aardwolf 2y ago
Hmm, so I think the 1R in 1RZ don't matter then for this program and are arbitrarily chosen, since it halts there so it doesn't matter what's still written on the tape or where the tape head moves? (Even writing of the 1 doesn't matter, though a 0 would have been suboptimal I guess. A 2 was already written on the tape there, it's being replaced by a 1 but the 2 counted just as much for 'number of symbols on the tape')

by tromp 2y ago

nilstycho 2y ago

Can you help me understand the log2(4+1) term? I calculate 3*4*log2(4*2*log2(4+1)) ≈ 51. I (a layperson) would have thought the calculation would be 3*4*log2(4*2*4) = 60. Is it perhaps 3*4*log2(4*2*log2(3*3*4-1)) ≈ 64?

tromp 2y ago
I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.
- im3w1l 2y ago
  You also need to subtract some bits from symmetries right? Like you can mirror the tape. You can relabel states B and C. And you can relabel symbols 1, 2, 3. Though the analysis is complicated a little bit by the fact that some (combinations) of those operations may yield the exact same machine.
  - nilstycho 2y ago
    Also, is there any sense in restricting the universe of machines to those that include one and only one halting symbol? Machines with more or fewer than one halting symbol are possible, but they're less interesting, right?
    - LegionMammal978 2y ago
      If you mean multiple halting transitions, then it doesn't really help for BB purposes. If the machine does halt, then only one of the halting transitions will ever be taken, and the others will be 'dead code'. If you mean multiple halting states, then that is possible, and it can be used as a model of computation for, e.g., computable functions returning a single bit as output. But you still don't gain any additional running time before the machine halts. As for no halting transitions, the problem is choosing what point to measure the tape at. One thing you can do is to put a mark on one of the transitions, then see whether the machine only runs that transition a finite number of times, or if it keeps running it forever. This yields the "Beeping Busy Beaver" numbers [0], which are uncomputable even if you have an oracle for the halting problem. [0] https://www.sligocki.com/2021/03/06/beeping-busy-beaver/ https://www.sligocki.com/2021/03/06/beeping-busy-beaver/
      - nilstycho 2y ago
        What I mean is that instead of measuring the bits of a particular program BB(n,k), we could instead define a function BBWOHT(n,k) ("Busy Beaver With One Halting Transition"), and measure the bits of a particular BBWOHT(n,k) program, which would be fewer bits than in the equivalent BB(n,k) program. Perhaps this is semantic games, but I'm trying to get at the idea that while there may be 60 bits of information in the BB(3,4) program, there are fewer in the BBWOHT(3,4) program, because we can prima facie exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BBWOHT(n,k), in the same way that we can exclude a bunch of "uninteresting" BB(n,k) programs from consideration if we restrict ourselves to BB(n,k) programs that aren't symmetries of other BB(n,k) programs.
        tromp 2y ago
        There are many inefficiencies in Turing Machines which you could try to work around with increasingly complicated encodings. But that will never yield a provably optimal machine encoding such as you can obtain with BBλ2 [1]. [1] https://oeis.org/A361211 https://oeis.org/A361211
  - tromp 2y ago
    Only if you want to count the number of different possible TM behaviours. The official count of BB TMs as given in OEIS sequence A052200 ignores such symmetries. [1] https://oeis.org/A052200 https://oeis.org/A052200

sligocki 2y ago

Counting the number of distinct TMs is not a simple task. The way you count it is the most broad (the count of all tables of values where each cell can have any (symbol, direction, state) combination). But this is a significant overcount of the bits needed to describe an arbitrary TM. for the BB(3, 4) case, there are only about 600B distinct TMs using the Tree Normal Form aka Brady's algorithm (https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html https://nickdrozd.github.io/2022/01/14/bradys-algorithm.html) which comes out to <40 bits.

tromp 2y ago
Similarly, 2^n would be a huge overcount of the number of n-bit closed terms, which is given by OEIS sequence A114852 [1]. There are 36140122614 ~ 2^35 closed terms of size 49 bits (length of a straightforward self-delimiting encoding). So in that sense it's still a smaller lambda term computing an incomprehensibly larger output. [1] https://oeis.org/A114852 https://oeis.org/A114852
jonahx 2y ago
Do you know of any (hand-wavy is ok) intuitive explanation for why this machine will halt, beyond the inductive proof's given in your article? Just watching the machine run, I would guess at some kind of infinite behavior. It is remarkable that this is not the case.
- addaon 2y ago
  > Do you know of any (hand-wavy is ok) intuitive explanation for why this machine will halt, beyond the inductive proof's given in your article? If the Halting problem could be solved by intuition, it wouldn't be much of a problem.
  - jonahx 2y ago
    Yet in this case there is a proof that it halts, and that proof contains an argument. I was asking for an explanation of the essence of that argument, if simplifying it is possible.

Aardwolf 2y ago

Hmm, so I think the 1R in 1RZ don't matter then for this program and are arbitrarily chosen, since it halts there so it doesn't matter what's still written on the tape or where the tape head moves? (Even writing of the 1 doesn't matter, though a 0 would have been suboptimal I guess. A 2 was already written on the tape there, it's being replaced by a 1 but the 2 counted just as much for 'number of symbols on the tape')