Beyond States and Colors: How a 3x4 Turing Machine Shatters Busy Beaver Records with 10¹⁵⁶⁵ Steps

In the esoteric world of computational theory, the Busy Beaver problem represents a relentless pursuit: find the Turing machine program of a given size that runs the longest before halting. Traditionally, size is measured by states and symbols (or "colors")—like 5-state, 2-color machines. But a paradigm shift is underway. By focusing solely on the total number of instructions, researchers are uncovering surprising insights into the fundamental power of computational primitives. The latest revelation? An 8-instruction program with a 3x4 shape (3 states, 4 symbols) that runs for over 10¹⁵⁶⁵ steps—smashing previous records and reshaping our understanding of efficiency.

Why Instruction-Limited Busy Beaver (BBi) Changes the Game

For decades, the Busy Beaver game categorized programs by states (N) and colors (K), ignoring that an NxK machine has exactly NK - 1 instructions. This led to an apples-to-oranges comparison: a 4x2 program (like Allen Brady's 1964 champion) runs for just 106 steps, while a 2x4 program (Shawn and Terry Ligocki's 2005 find) clocks 3,932,963 steps—suggesting colors are more powerful than states. But when both are viewed as underspecified 4x4 programs with 7 instructions, the disparity becomes stark:

4x2 as 4x4:              2x4 as 4x4:
+---+-----+-----+-----+-----+    +---+-----+-----+-----+-----+
|   |  0  |  1  |  2  |  3  |    |   |  0  |  1  |  2  |  3  |
+---+-----+-----+-----+-----+    +---+-----+-----+-----+-----+
| A | 1RB | 1LB | --- | --- |    | A | 1RB | 2LA | 1RA | 1RA |
+---+-----+-----+-----+-----+    +---+-----+-----+-----+-----+
| B | 1LA | 0LC | --- | --- |    | B | 1LB | 1LA | 3RB | --- |
+---+-----+-----+-----+-----+    +---+-----+-----+-----+-----+
| C | --- | 1LD | --- | --- |    | C | --- | --- | --- | --- |
+---+-----+-----+-----+-----+    +---+-----+-----+-----+-----+
| D | 1RD | 0RA | --- | --- |    | D | --- | --- | --- | --- |
+---+-----+-----+-----+-----+    +---+-----+-----+-----+-----+

This visual highlights the bias: minimizing states maximizes runtime. Early BBi(n) results reinforced this, with 2xK shapes dominating:

The 3x4 Champion: A Computational Masterpiece

Discovered on July 26, 2025, the new BBi(8) champion defies expectations with its 3x4 shape:

    +-----+-----+-----+-----+
    |  0  |  1  |  2  |  3  |
+---+-----+-----+-----+-----+
| A | 1RB | 1LA | --- | --- |
+---+-----+-----+-----+-----+
| B | 1RC | 3LB | 1RB | --- |
+---+-----+-----+-----+-----+
| C | 2LA | 2LC | --- | 0LC |
+---+-----+-----+-----+-----+

Transliterated to C, it showcases intricate control flow:

main() {
A:
  switch (READ) {
    case 0: { PRINT(1); RIGHT; goto B; }
    case 1: { PRINT(1); LEFT;  goto A; }
  }
B:
  switch (READ) {
    case 0: { PRINT(1); RIGHT; goto C; }
    case 1: { PRINT(3); LEFT;  goto B; }
    case 2: { PRINT(1); RIGHT; goto B; }
  }
C:
  switch (READ) {
    case 0: { PRINT(2); LEFT;  goto A; }
    case 1: { PRINT(2); LEFT;  goto C; }
    case 3: { PRINT(0); LEFT;  goto C; }
  }
}

This structure exploits both states and colors harmoniously, achieving a runtime so vast (10¹⁵⁶⁵ steps) that it dwarfs the age of the universe.

alt="Article illustration 1"
loading="lazy">

Implications: Rethinking Computational Efficiency

The 3x4 program's success debunks the myth that colors alone drive longevity. In BBi(n), shape flexibility allows hybrid designs that leverage states for complex jumps and colors for branching, optimizing instruction use. This has ripple effects:
- Algorithm Design: Tools like Brady’s algorithm for Busy Beaver searches must now account for shape-agnostic optimization.
- Spaghetti Code Conjecture: Loosely structured programs might achieve higher runtimes, challenging clean-code paradigms.
- Open Problems: Beating BBi(8) or finding BBi(9) > 10↑↑4 (tetration) could reveal deeper links to uncomputability—SHAPE(n)'s growth rate itself may be non-computable.

As we push boundaries—like mxdys' 6x2 program with >2↑↑↑5 steps—BBi(n) reframes efficiency not by rigid categories, but by the raw economy of instructions. In the quest for computational extremes, sometimes the most powerful shape is the one we least expect.

Source: Nick Drozd, https://nickdrozd.github.io/2025/09/30/shape-of-a-turing-machine.html