← all systems · see it in The System
Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules.
Properties published scienceour proposal
Sourced fields, and our own readings.
| aliases | Turing machine |
| born at | 28 May 1936 (received; read 12 November 1936); idea summer 1935 |
| born precision | day (contested between 28 and 31 May, C-2318) |
| boundary | Inside: the tape of squares with its symbols, the head over one scanned square, the state register holding one of finitely many m-configurations, the finite table of instructions, and the run they make together (the sequence of complete configurations, halting or not). Outside: whoever writes the input and the table (a person or another machine), the oracle or external operator in Turing's o- and c-machines, the physical carrier when the model is built, and what the computed result is used for. |
| nested level | A model of computation (an automaton) in computability theory, the theory of computation and complexity theory; the strongest member of the automata ladder (finite-state machines, pushdown automata, linear bounded automata). It runs on people (Turing's human 'computer', logicians, students) and on machines that simulate it; real computers are bounded instances of it. |
| scale | technological |
Measures (20) published science
| characteristic clock: one move per step (one symbol altered at most) | 1 symbol per step |
| characteristic clock: S(5), the longest run of a halting 5-state 2-symbol machine from the blank tape (a settling time) | 47,176,870 steps |
| characteristic clock: from Turing's paper (received 28 May 1936) to the formal S(5) proof (2024) | about 88 years (derived from two dates the sources give) |
| busy beaver step values S(1)..S(4) | 1, 6, 21, 107 steps |
| Σ(5): most 1s left by a halting 5-state machine | 4,098 symbols |
| S(2,4): 2-state 4-symbol busy beaver steps | 3,932,964 steps |
| S(6) lower bound | more than 2↑↑↑5 steps |
| 5-state machines enumerated in tree normal form (from 16,679,880,978,201 before reduction) | 181,385,789 machines |
| 1983 Dortmund competition winner (Uwe Schult) | 134,467 steps |
| smallest standard universal Turing machine known (Rogozhin, 4 states 6 symbols) | 22 instructions |
| smallest weakly universal machines (Rule 110 simulators) | (2, 4), (3, 3), (6, 2) (states, symbols) |
| machine whose running forever is unprovable in ZFC (2016) | 7,910 states |
| machine encoding ZF's consistency | 748 (bbchallenge, with 636 and 432 pending verification); 745 (encyclopedia) states |
| machine encoding the Riemann hypothesis | 744 (bbchallenge); 120 (encyclopedia) states |
| machine encoding Goldbach's conjecture | 25 states |
| minimum heat per erased bit (Landauer) | kT ln 2 energy per bit |
| expected heat of a universal Turing machine (both realizations studied) | infinite heat |
| slowdown of a multi-tape universal machine against the machine simulated (Hennie and Stearns 1966) | logarithmic factor time |
| date: paper received by the London Mathematical Society | 28 May 1936 (paper's own header); 31 May 1936 (encyclopedia, after Hodges) date |
| date: Church's paper published | 15 April 1936 date |
Open contentions (7) open contention
Where sources or readings disagree. Both stay on the map.
- C-557 Can every computation be done by a Turing machine?
booked: The map follows the near-universal acceptance of the Church-Turing thesis and notes that it can't be proven, keeping the challenges alongside.
the other reading: a definition (Church); a hypothesis and ultimately a natural law (Post); derivable from axioms (Dershowitz and Gurevich; Sieg); physical versions: the universe equivalent to a Turing machine, or not but not harnessable, or hypercomputation possible (open) - C-2276 Who first posed the halting problem?
booked: The map keeps both attributions.
the other reading: commonly attributed to Turing 1936 (e.g. Miranda and Ramos 2026: 'originally established by Turing'); the term 'halting problem' is Davis's (1952 lectures; Davis 1958), and Kleene 1952 first framed it as 'eventually stops' (encyclopedia); Hamkins and Nenu: 'a nuanced conclusion' - C-2283 How small a machine can't be proved to halt?
booked: The map keeps the published sizes.
the other reading: 745 states for ZF (Riebel, July 2023) and 120 states for the Riemann hypothesis (encyclopedia); 636 and 432 states for ZF, pending verification (bbchallenge); 7,910 states for a machine independent of ZFC (2016), the first explicit bound - C-2289 Is the mind a Turing machine?
booked: The map keeps it open.
the other reading: a 'human Turing machine': parallel steps feeding a slow serial production system (Zylberberg, Dehaene, Roelfsema, Sigman 2011); the Conscious Turing Machine: a substrate-independent model of consciousness, explicitly 'not a model of the brain' (Blum and Blum 2022); an open empirical question whether non-Turing-simulable processes are involved in the working of the brain (Copeland, via the encyclopedia) - C-2316 Did the modern computer come from the Turing machine?
booked: The map keeps the historians' debate open.
the other reading: the stored-program concept originates in the universal machine (Davis; Copeland and Proudfoot; Minsky: 'in essence, the invention of the modern computer'); historians of computing (Haigh, Daylight, Mounier-Kuhn): the inventor story gives 'a distorted and biased picture' - C-2317 Is the Turing machine an idea or a technology?
booked: The map books it as an idea and keeps the alternatives beside it.
the other reading: rung 12: 'an idealised model of a central processing unit', built physically from 1937 (relay multiplier); rung 0: the structure it defines (the Turing-computable functions) as the algorithm walk's rung-0 role; the strong physical Church-Turing thesis reads the universe as equivalent to a Turing machine - C-2318 When was Turing's 1936 paper received?
booked: The map keeps both dates.
the other reading: submitted 31 May 1936 (encyclopedia lead, after Hodges 1983 p. 112); publication: 1936 (volume dated 1936-1937) or January/early 1937, offprints February 1937
Cross-scale patterns seen here (21) our proposal
Shapes that recur when the same kind of problem is solved at different scales, and how each shows in Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science. Each links to every other system that shows it.
- borrowed-then-held (structural)
Turing's choice machine waits for an external operator to settle ambiguous configurations (borrowed); his automatic machine instead runs through the choices itself, 'proof 1, proof 2, proof 3' (held). Both phases in the 1936 paper. - causal ceiling (structural)
No machine can decide for every machine whether it is satisfactory (halts, prints a symbol); no algorithm decides whether a billiard trajectory is periodic or whether a quantum lattice is gapped; S(748) cannot be proved in ZF. A limit set by the structure of computation, not by speed or memory. - nested ladder (structural)
The automata ladder: read-only right-moving machines equal finite automata, a tape proportional to the input gives a linear bounded automaton, the unbounded tape the full Turing machine, each stronger than the last; above it oracle machines climb degrees of unsolvability. - same role, different builds (structural)
One job, computing the computable functions, built as Turing machines, lambda calculus, recursive functions, Post systems, register machines, Rule 110 and the Game of Life, two-dimensional billiards, oscillating chemistry, DNA string rewriting, Lego and relays. - same toolkit, independent builds (structural)
Church (lambda calculus, published 15 April 1936), Turing (machines, received 28 May 1936) and Post (a worker moving room to room, fall 1936) built the same notion of computability independently, each with a formalism, a universal process and diagonalization: 'Church, Post and Turing each used more - seed (structural)
A table of 22 instructions (Rogozhin's universal machine) or Turing's U unpacks every computable sequence: any machine, written in seven letters, becomes data the universal machine runs; every string of a given kind names some machine. - templating (structural)
One description format reused unchanged for every machine (the standard description; the 5-tuple convention) and one machine reused across models: counter, register and random-access machines are 'basically all just multi-tape Turing machines with an arithmetic-like instruction set'. In Shapiro's mo - The Payment to Entropy (structural)
Thermal form: a built machine pays at least kT ln 2 per erased bit, and a universal machine's expected heat is infinite; logically reversible steps can in principle avoid it, which is why Shapiro's molecular design keeps a trace polymer of every step instead of erasing. - trade one property for another (structural)
Shannon: two symbols suffice with enough states, and states can always be exchanged for symbols; the smallest universal machines sit along that trade ((15, 2) to (2, 18)); Turing trades states of mind for symbols on the tape; a built machine trades heat against the Kolmogorov complexity of its heat - Umwelt: each system carves its own slice of one shared medium (structural)
The machine's whole Umwelt is one scanned symbol: 'the only one of which the machine is, so to speak, directly aware'; the rest of the tape exists for it only by moving. Turing cut it from a person's sensory and mental limits (bound B on a glance). - coordination-before-mapping (partial)
The machine computes anything computable while aware only of the scanned symbol and its state: no map of its tape, which it learns only by moving and remembering by state. The tape itself does the remembering. - holding / entrainment (partial)
The universal machine sets the clock of the machine it simulates: each simulated move happens only when U's own steps carry it out, at most a logarithmic factor slower for multi-tape machines. - lightning (partial)
Turing told Gandy that the 'main idea' came to him lying in Grantchester meadows in summer 1935 (a firing of intuition), and the 1936 paper settled the Entscheidungsproblem in the negative, after which computability had a definition. The discharge is reported; whether it was sudden rests on Turing's - namespace completeness (the map predicts its gaps) (partial)
Every machine is a description number and the computable sequences are enumerated by them; bbchallenge's map of small busy beaver values marks which cells are solved and which hold 'Cryptids' whose halting is believed hard, and tree normal form fixes exactly which machines must be decided. - outside-to-inside (partial)
Outside first: 'Computing is normally done by writing certain symbols on paper', squared like a child's arithmetic book; then the paper became part of the machine, a tape 'running through it'. The reverse also shows: a person's state of mind is moved out onto the paper as a note of instructions. - same shape, opposite sign (partial)
One register operation run with its sign reversed: y := y + x copies x into an empty y, y := y − x erases it when y equals x; 'each exactly undoes the effect of the other', the basis of reversible computation that avoids the erasing toll. - The carry (partial)
The wait: on a tape the machine must walk to the square it needs, so running times carry a false lower bound that random access avoids (binary search is faster on the RASP model: a lookahead past the wait). The busy beaver numbers are the longest settling times n states can have: S(5) = 47,176,870 s - who opens the door (partial)
At each crossing from tape to machine the receiver's own table, written ahead of time, decides what passes: no entry and the machine halts; in the c-machine an outside operator opens the door, in the o-machine an oracle. - cephalization (surface)
Sensing and processing gather at one point, the head, where the machine meets each new symbol; but the head moves both ways and there is no front end, so the input-first reason is missing: surface. - partner-becomes-part (surface)
Another machine's whole table becomes data on the universal machine's tape and runs as part of it (program and behaviour on one level); no gain/gain loop or inheritance is shown, so surface. - the whole sets the local reference (surface)
Each step is fixed locally by the configuration and reads true locally, yet whether the run as a whole halts cannot in general be read from the local rules; a loose fit to the frame-closure shape: surface.
Valence: what it trades, and with whom (18) published science
Each exchange with a neighbour, read from both sides: who gains, who pays, and what carries it.
- Real number (the practice of measuring the continuum, and the complete ordered field) via sys:sensory-environment · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Recursion: defining or computing a thing in terms of smaller versions of itself, as computer science and mathematics describe it, with its base cases, call stack, recursive data, induction, and its sightings in language and nature via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- DNA and genes via sys:aqueous-solution · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Human (Homo sapiens) via sys:sensory-environment · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Stored-program principle (instructions held in the same memory as data) via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Entropy via sys:thermal-energy · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science loss
- Human brain via sys:mental-representation · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Number and counting (the number sense, the practice of counting, and the structure it works on) via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Computer via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Algorithm (the practice of step-by-step procedures and the structure they compute) via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Programming language via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Lambda calculus via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Classical mechanics (Newtonian mechanics: bodies, forces and motion, and the practice of describing them) via sys:sensory-environment · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Set theory: the study of sets (collections taken as single objects), membership, Cantor's infinities and the axioms, and the practice of the people and machines who work with them via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science mixed
- Proof assistant (Metamath, Lean, Isabelle and the like) via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Computer science (the field: the practice and the computation it studies) via sys:sensory-environment · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science even
- Mathematical proof: the practice of showing that a statement follows from axioms and earlier theorems, how it is written, checked (by people and machines) and accepted, and the derivations it works on via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
- Mathematical logic: the field that studies logic within mathematics (model theory, proof theory, set theory, computability theory) and the formal systems, structures and limit results it works on via sys:written-record · Turing machine: the abstract machine that reads and writes one symbol at a time on an unbounded tape by a finite table of rules, the model of computation of logic and computer science gain
Partners and parts published science
Built from / builds (7)
- Tape (an unbounded row of squares, each bearing one symbol)
- Head (reads and writes the scanned square)
- State register (one of finitely many m-configurations)
- Table of instructions (the transition function)
- Computer science (the field: the practice and the computation it studies)
- The busy beaver game (Radó, 1962): n-state machines compete for the longest run or the most 1s
- The 1936 race to settle Hilbert's Entscheidungsproblem (Church, Turing, Post)
Sits inside / holds (3)
- Human (Homo sapiens)
- Computer science (the field: the practice and the computation it studies)
- Computability theory
expressed by (12)
- Generation/Synthesis
- Recombination/Composition
- Scaffolding/Enablement (Meta-Tooling)
- Templating / Standardization
- Interoperability/Transduction (Bridging)
- Encapsulation & Modularity (Abstraction)
- Internal Coordination/Regulation
- Sensing/Scanning
- Search/Foraging
- Trail-Marking / Externalized Memory (Stigmergy)
- Self-Monitoring
- Redundancy & Diversity
floor filled by (16)
- Algorithm (the practice of step-by-step procedures and the structure they compute)
- Human (Homo sapiens)
- Written record (durable external marks: texts, archives, canon)
- Universal Turing machine (the rule's first statement)
- Church-Turing thesis
- Halting problem
- Computer science (the field: the practice and the computation it studies)
- Tape (an unbounded row of squares, each bearing one symbol)
- Head (reads and writes the scanned square)
- State register (one of finitely many m-configurations)
- Table of instructions (the transition function)
- Busy beaver (the longest-running or highest-scoring halting n-state machine)
- Computability theory
- Computable number
- Physical carrier of computation
- Mathematical logic: the field that studies logic within mathematics (model theory, proof theory, set theory, computability theory) and the formal systems, structures and limit results it works on
represents (1)
Kinds (15)
- Universal Turing machine (the rule's first statement)
- Model of computation
- Choice machine (c-machine)
- Oracle machine (o-machine)
- Non-deterministic Turing machine
- Multi-tape Turing machine
- Linear bounded automaton
- Finite-state machine (read-only, right-moving)
- Quantum Turing machine
- Turmites and Langton's ant (two-dimensional tape)
- Reversible Turing machine
- Non-deterministic universal Turing machine in DNA (a physical design)
- Chemical Turing machine (oscillating reactions)
- Busy beaver (the longest-running or highest-scoring halting n-state machine)
- Counter, register and random-access machines
Notes published science
- The Turing machine is a portrait of a person doing sums. Turing built it from a clerk with squared paper: you can only take in a few symbols at a glance ('We cannot tell at a glance whether 9999999999999999 and 999999999999999 are the same'), you have finitely many states of mind, and you write one symbol at a time. The machine's single scanned square is a human glance shrunk to one square. Sources: src:turing-1936, src:demol-sep-2025.
- In 2024 an online group of mostly amateur mathematicians settled a 60-year-old question: the longest any 5-state machine can run before stopping is exactly 47,176,870 steps. They had to check 181,385,789 machines, and the whole proof was checked by computer. With one more state, a machine called Antihydra stops only if a Collatz-like puzzle about odd and even numbers is false, so nobody knows. Sources: src:bbchallenge-2025, src:wp:busy-beaver.
- The same limit turns up far from computers: a single ball bouncing around a flat billiard table can act as any Turing machine, so some questions about where the ball will go can never be answered by any method, not even in principle. Source: src:miranda-ramos-2026-billiards-turing.
Layers
The ways it takes in its world, where they meet, and how it acts back, each from L1 (where it meets the world) up.
a Turing machine as logicians and computer scientists describe it: a finite table of rules reading and writing one symbol at a time on an unbounded tape (reader's view)
- L1: The tape: an unbounded row of squares, each bearing at most one symbol from a finite alphabet, blank where nothing has been written; the analogue of a page of squared paper.
- L2: The head over one square: the scanned symbol, the only one the machine is directly aware of; read, then overwritten or erased, then the head moves one square.
- L3: The configuration: the current m-configuration (state) paired with the scanned symbol; it determines what the machine may do next. The state is how the machine remembers.
- L4: The table of instructions (transition function): for each configuration, what to write, which way to move, which state next; no entry means halt.
- L5: The run: the succession of complete configurations (Turing's state formula), one move at a time, ending in a halt or going on for ever; circular and circle-free machines.
- L6: What the run computes: a computable sequence or number, a function on encoded inputs, a recognised language; and the universal machine, which computes what any machine computes from its standard description.
- L7: The model of computation: computability identified with what Turing machines compute (the Church-Turing thesis, not provable), the limits it proves (no general process for the Entscheidungsproblem or for halting), and its use as the standard model of computability and complexity theory.
the boardroom (shared floors)
- L3: The configuration: the m-configuration together with the scanned symbol (or the oracle's answer, or the operator's choice) fixes the machine's possible behaviour.
- L4: The table of instructions: each configuration selects write, move and next state; one symbol altered at most per simple operation; no entry, halt.
- L5: The run: complete configurations one after another (Turing's state formula: the tape followed by the note of instructions); it halts or runs for ever, and which one is in general undecidable.
- L6: What is computed: computable sequences and numbers, functions on encoded inputs, recognised languages; every machine itself a number; the universal machine computing what any machine computes.
- L7: The model: Turing computability as the meaning of 'effectively calculable' (a thesis, not provable; definition for Church, natural law for Post), the limits it proves (no general process for the Entscheidungsproblem, for satisfactory numbers, for halting; Rice), its hierarchy above weaker automata, and its role as the standard model of computability and complexity theory.
way in: An external operator's choice (Turing's choice machine)
- L1: An external operator, outside the machine.
- L2: The ambiguous configuration: the machine waits until the choice is made (Turing's example: dealing with axiomatic systems); a deterministic machine can instead run through the choices in turn.
way in: An oracle's answer (Turing's o-machine, 1939)
- L1: The oracle: an entity Turing left unspecified 'apart from saying that it cannot be a machine'.
- L2: State o: the machine pauses and awaits the oracle's decision.
way in: Another machine's description (the universal machine's channel)
- L1: Marks on the tape: the standard description of a machine M, its quintuples separated by semicolons, at the beginning of the universal machine's tape.
- L2: Read square by square through the universal machine's head.
- L3: Decoded as a machine: the letters name states (D followed by A's) and symbols (D followed by C's); the whole is also a number, the description number.
- L4: Matched against the simulated machine's current complete configuration to find the instruction that applies.
- L5: The simulated machine's next complete configuration written down; a multi-tape universal machine is only a logarithmic factor slower than the machine it simulates.
way in: The input: what is written on the tape before the run
- L1: The initial tape: a finite string of input symbols, blanks everywhere else (only the blank may appear infinitely often).
- L2: The input as code: numbers and questions written as strings of symbols, read one square at a time through the head.
way in: The m-configuration (the inner channel: what the machine carries from step to step)
- L1: The state register: one of finitely many m-configurations, in the place of a person's state of mind.
- L2: Memory by state: the machine remembers some of what it has scanned only by changing its m-configuration; a finite number suffices, since more symbols on the tape can stand in for more states of mind.
way in: The physical carrier (when the model is built: relays, molecules, chemistry, billiard balls)
- L1: A physical build: Turing's relay multiplier (1937), mechanical and molecular blueprints, DNA string rewriting, oscillating chemistry, billiard trajectories; bounded in memory and time, and error-prone.
- L2: The physical read: molecular recognition of a symbol and state (Shapiro), an oscillating reaction's response (Draper et al.); in Shapiro's design every step is kept in a trace polymer.
way in: The scanned symbol (the head reading the tape)
- L1: A square of the tape bearing a symbol (or blank); the tape is the analogue of squared paper.
- L2: The head over that square: one scanned symbol taken in, the machine's whole view of its world. In the human computer this is the bounded glance (at most B squares at once).
way out: Built as hardware and used as the yardstick of computing
- L1: A physical machine in the world; bounded, error-prone, paying heat.
- L6: A design embodying a Turing machine: relay switches (1937), molecular parts, DNA rewriting, Lego and mechanical models.
- L7: The universal machine used as a mathematical basis for general-purpose machine design (and contested as their origin).
way out: Halt: the run ends and the tape is read as output
- L1: The final tape: the output, read by whoever runs the machine (for a busy beaver, the count of 1s is its score).
- L5: No instruction for the configuration: the machine halts (accepting the input if in a final state).
way out: Heat to the surroundings (a built machine erasing)
- L1: At least kT ln 2 of heat per erased bit released into the environment.
- L4: A logically irreversible step (an erasure, two paths merged).
way out: Move one square left or right (or stay); change state
- L1: A new square under the head: the next scanned symbol.
- L3: The next state set in the register.
- L4: The instruction selected: L, R or N, and the next m-configuration.
way out: Write or erase the scanned symbol
- L1: The square changed: the tape now carries the new symbol for later steps.
- L2: The head writes into the scanned square, at most one symbol per simple operation.
- L4: The instruction selected: print a symbol, erase, or leave it.