A busy beaver is an -state, 2-symbol Turing machine that leaves the maximum number of 1s on an initially all-zero tape when it halts (Rado 1962, Lin and Rado 1965, Shallit 1998). Alternatively, some authors define a busy beaver as a Turing machine that performs the maximum number of steps before halting from the same initial tape (Wolfram 2002, p. 889). Here is a positive integer counting the nonhalting states, the tape is infinite in both directions, and each transition writes 0 or 1 and moves one cell left or right. The final transition into a separate halting state counts as a step.

The process leading to the solution of the three-state problem is discussed by Lin and Rado (1965), and the process leading to the solution of the four-state problem is discussed by Brady (1983) and Machlin and Stout (1990).

For , 2, ..., (also known as Rado's sigma function) is given by 1, 4, 6, 13, 4098, ... (OEIS A028444; Rado 1962; Wolfram 2002, p. 889). The equality is proved by The bbchallenge Collaboration et al. (2026, p. 37). An earlier construction gives the lower bound (Marxen). The illustration above shows a 3-state Turing machine with maximal (Lin and Rado 1965, Shallit 1998).

The maximum number of steps which an -state 2-symbol Turing machine (not necessarily the same Turing machine producing a maximum number of 1s) can perform before halting is . Its first few terms are 1, 6, 21, 107, 47176870, ... (OEIS A060843; Wolfram 2002, p. 889). Turing machines giving maximal for , 3, and 4 are illustrated above. The equality is proved using the Coq proof assistant (The bbchallenge Collaboration et al. 2026, p. 2).

A set of 5-state rules found by Marxen and Buntrock (1990) that attains both proved maxima and is illustrated above (Wolfram 2002, p. 889; The bbchallenge Collaboration et al. 2026, pp. 9, 37).

Pavel Kropitz constructed a 6-state, 2-symbol Turing machine in May 2022 (Ligocki 2022). Goucher (2022) reports that it takes approximately

timesteps to halt, and Ligocki (2022) proves that it takes more than steps in Knuth up-arrow notation. In the preceding display, exponentiation is right-associative, so the rightmost exponentiation is applied first. The machine leaves

1s when the machine halts (Goucher 2022, Ligocki 2022).

Brady found a 3-state, 3-symbol Turing machine in December 2004 giving the lower bound for (Michel 2022). Here is the analogous maximum step count for nonhalting states and tape symbols, one of which is the initial blank symbol.

Historical results and analyses of the machines are collected by Michel (2022).