Universal Machine Transformer (UMT)

The busy beaver

The busy beaver

Of every Turing machine with four states and two symbols that halts when started on a blank tape, this one runs the longest: 107 steps, leaving 13 ones. No four-state machine does better; that was proved in 1983. Here the same small trained transformer runs it, one forward pass at a time, without ever having seen it.

Champion
1

The champion

Its tape, its head, and its state, read off the universal machine's tape after every step.

Steps0of the record 107
Ones on the tape0of the record 13
Forward passes0

 

Its rules

State w is a prelude, not part of the champion: the universal machine's tape for the machine it runs is one-way, so w walks right over a strip of 0s, erasing them, and hands over to A with exactly as much room on its left as the champion ever uses.

Steps that match the champion run directly0
Universal-machine steps0
Different steps it needed0
Never seen in training0
Disagreed with the exact rule0
2

The whole run

Time runs left to right: each column is the tape after one step, filled where it holds a 1. The marked cell is the head.

Why this is a hard test

A busy beaver is the halting machine of a given size that runs longest from a blank tape (Radó, 1962). Whether a given machine ever halts cannot be decided in general, so these numbers are found one size at a time, by ruling out every other machine. Two states: 6 steps. Four: 107 steps, 13 ones (Brady, 1983). Five: 47,176,870 steps, settled only in 2024 by a collaborative, computer-checked proof.

The champion sweeps back and forth across a growing block of 1s, as the picture above shows, and then halts. The network never saw it: it trained on random machines, with tapes of up to six cells. With its prelude the champion has five states, and its tape reaches 14 cells.

The network is the one from the first page: one transformer layer, two attention heads, 211,270 parameters, trained only on the steps of a universal Turing machine while it ran random machines. The champion is written on the universal machine's tape as data:


        

Every configuration above is read from the universal machine's own tape after each step, and is checked against the champion run directly. The same check runs in plain Python in machines/lag5.