News for hackers. Stuff that matters.
Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @11:28AM (#40455914)
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

Re:BB(3, 4) > Ack(14) by nilstycho on Thursday May 23, 2024 @01:04PM (#40457165)
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?

Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @01:36PM (#40457592)
I miscalculated. It should be 3*4*log2(4*2*(3+1))= 60 bits of information.
Re:BB(3, 4) > Ack(14) by im3w1l on Thursday May 23, 2024 @01:49PM (#40457732)
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.

Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @02:16PM (#40457998)
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

Re:BB(3, 4) > Ack(14) by nilstycho on Thursday May 23, 2024 @02:14PM (#40457968)
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?
Re:BB(3, 4) > Ack(14) by LegionMammal978 on Thursday May 23, 2024 @02:25PM (#40458092)
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/

Re:BB(3, 4) > Ack(14) by nilstycho on Thursday May 23, 2024 @03:03PM (#40458582)
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.

Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @03:20PM (#40458813)
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

Re:BB(3, 4) > Ack(14) by sligocki on Thursday May 23, 2024 @09:13PM (#40461863)
Can you clarify what you mean by BBλ being "provably optimal"? IIUC BB functions for any Turing-complete computation model should be equivalent up to a constant. Maybe something like: there exists N, c: forall n >= N: BBλ(n) < BB(n + c) and vice-versa. I am not sure what the exact equation will be off-hand, maybe in this case we will need to replace BB() with a version based on binary encoding of TMs.
Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @09:53PM (#40462118)
As the OEIS entry says:

> for any other busy beaver BB based on self-delimiting programs, there is a constant c such that a(c+n) >= BB(n)

This requires an information theoretic measure of program size, such as bits or bytes, whereas the TM-based BB measures in states. I don't believe there are additively tight bounds on how many states are needed to encode an arbitrary string of n bits.

Re:BB(3, 4) > Ack(14) by Dylan16807 on Thursday May 23, 2024 @09:50PM (#40462094)
Limiting to one halt does easily shave off a few bits.

Looking at the state transitions:

12 * log2(3+1) is 24 bits

log2(12) + 11 * log2(3) is only 21.02 bits

And since the specific output symbol and movement direction of the halting state don't matter, that's another few bits you can throw away.

So that gets you down to 54.02 bits before you even consider factoring out symmetries.

Re:BB(3, 4) > Ack(14) by sligocki on Thursday May 23, 2024 @03:34PM (#40458931)
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) which comes out to <40 bits.
Re:BB(3, 4) > Ack(14) by tromp on Thursday May 23, 2024 @03:46PM (#40459061)
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 the most 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

Re:BB(3, 4) > Ack(14) by jonahx on Thursday May 23, 2024 @11:37PM (#40462571)
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.
Re:BB(3, 4) > Ack(14) by addaon on Friday May 24, 2024 @01:49PM (#40468621)
> 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.

Re:BB(3, 4) > Ack(14) by jonahx on Friday May 24, 2024 @03:40PM (#40469771)
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.
Re:BB(3, 4) > Ack(14) by Aardwolf on Friday May 24, 2024 @10:28AM (#40466633)
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')