Turing Machines

This article covers the uncomputable function BB. BB(n,k) is the maximum number of steps taken by any n-state k-symbol halting Turing machine. As a historically-important special case, BB(n,2) is OEIS A60843, also known as S(n).

Some machines require a non-zero initial tape, which can be accounted for by appending the length of the initial tape to the symbol count: we treat them as shorthand for machines which use one state per symbol to write the initial tape before jumping to their main algorithm.

Summary

The following diagram summarizes known values and problems relative to BB. It is hard to read due to relatively high dimensionality; the solid violet barrier from the top to the left gives known values of BB, the blue wall is given by Rogozhin's machines, and the other known implementations are a smattered constellation of dots.

Known Values

BB(1,k) is defined as 1 for all k.

This table is tight in the sense that all unknown cells are bounded by the hardest open problems in mathematics, known as cryptids.

Tables of Values

Goldbach conjecture

Period 32 Laver table

Erdős–Lagarias conjecture

Interp(Tag(2))

Catalan–Mersenne conjecture

Fermat prime conjecture

Weak Goldbach conjecture

Legendre conjecture

Odd perfect number

Pólya's problem

Riemann hypothesis

Con(ZF)