It is sometimes thought that extremely long-running Turing machine programs must be deeply complicated, or "spaghetti code". This new reigning champion program is a counterexample. All things considered, it is relatively simple.

There are three states: A, B, C. (States are just like goto targets in C.) State B passes control to A and C, but states A and C don't "know about" each other; they only pass control back to B. This is a sort of modular construction, whereas in true spaghetti code each state would be able to pass to all the others.

This program has some other interesting features. It never prints a blank (that is, whenever it scans a 0, it prints 1, 2, or 3). Additionally, every instruction changes either the state or the color -- there are no "lazy instructions" like B1 -> 1LB that just move position without changing anything else.

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

I was curious as to how it works, so I implemented here: turingmachine.io/?import-gist=c862f28918f3d889f964797694d28fcc

If you run it for a bit you see what's going on, State B turns 0's into 2's and 1's into 1's transitioning to C and state C turns 3 -> 2's and transitions to A. So you just iteratively lengthen your run of 3's exponentially since it requires a full pass through all the 3's to fix a 2->1.

This all sounds like extreme Code Golf to me.

Here's a tangent to explore:

A BitGrid[1] (my personal hobby horse) only has 4 bits of state per cell, so a 4x4 grid of cells can't count more than 2^64, no matter what. Finding the highest it could count would be interesting. For small grids, the edge connections would dominate the outcome.

[1] https://esolangs.org/wiki/Bitgrid

[2] https://github.com/mikewarot/Bitgrid

Can someone point me to some resources as to how to interpret the table, which I assume is some sort of description for a Turing machine?

Discord links! As citations for major results in foundational computer science!

There are only so many Turing machines that we can possibly describe with a not too large amount of symbols such as 1RB3LB1RZ2RA_2LC3RB1LC2RA_3RB1LB3LC2RC. The fact that some of these can make such a crazy large number of steps before halting to me is mind blowing.

I don’t know why, but these probably-useless-results (which frankly I don’t 100% understand) intrigue me more than the incredibly-useful LLM advances. I guess because I’m naturally drawn to “simple” mathematical truths more than “messy” engineering results.

Nice that the author provides some context...

Is it not true that BB(5) > BB(3,4)? On the https://bbchallenge.org site it said they're trying to prove or disprove the conjecture that BB(5) is about 47 million but BB(3,4) is apparently much bigger than that.

If you know, you know I guess. I certainly have no idea.

Can someone give a quick description of why this one is special? I'm familiar with turing machines (sort of), but I can't deduce why this specific instruction set is impressive. Whats an Ackerman-level function? Whats it actually computing?

And you thought your for-loops were too deeply nested!

[flagged]