Alan Turing (1936) • Tibor Radó's On Non-Computable Functions (Bell System Tech. J., May 1962)
In May 1962, Hungarian mathematician Tibor Radó published “On Non-Computable Functions” in the Bell System Technical Journal (Vol. 41, pp. 877–884). To construct the simplest possible well-defined uncomputable function, Radó standardized the binary Turing Machine under five strict axioms:
0 or 1).L) or Right (R)—stationary head moves are forbidden.1s left on the tape when halting () and the maximum shifts before halting ().| States n | Σ(n) (Max 1s) | S(n) (Max Shifts) | Status / Year |
|---|---|---|---|
| n = 1 | 1 | 1 | Radó (1962) |
| n = 2 | 4 | 6 | Radó (1962) |
| n = 3 | 6 | 21 | Lin & Radó (1965) |
| n = 4 | 13 | 107 | Brady (1966) |
| n = 5 | 4,098 | 47,176,870 | Coq Proven (2024) |
| n = 6 | ≥ 10↑↑15 | ≥ 10↑↑15 | Open (Pavel Kropitz) |