EVOPEDIA

← 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.

aliasesTuring machine
born at28 May 1936 (received; read 12 November 1936); idea summer 1935
born precisionday (contested between 28 and 31 May, C-2318)
boundaryInside: 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 levelA 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.
scaletechnological

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 machine4,098 symbols
S(2,4): 2-state 4-symbol busy beaver steps3,932,964 steps
S(6) lower boundmore 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 consistency748 (bbchallenge, with 636 and 432 pending verification); 745 (encyclopedia) states
machine encoding the Riemann hypothesis744 (bbchallenge); 120 (encyclopedia) states
machine encoding Goldbach's conjecture25 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 Society28 May 1936 (paper's own header); 31 May 1936 (encyclopedia, after Hodges) date
date: Church's paper published15 April 1936 date

Open contentions (7) open contention

Where sources or readings disagree. Both stay on the map.

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.

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.

Partners and parts published science

Built from / builds (7)

Sits inside / holds (3)

expressed by (12)

floor filled by (16)

represents (1)

Kinds (15)

Notes published science

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)

  1. 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.
  2. 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.
  3. 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.
  4. L4: The table of instructions (transition function): for each configuration, what to write, which way to move, which state next; no entry means halt.
  5. 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.
  6. 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.
  7. 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)

  1. 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.
  2. L4: The table of instructions: each configuration selects write, move and next state; one symbol altered at most per simple operation; no entry, halt.
  3. 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.
  4. 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.
  5. 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)

  1. L1: An external operator, outside the machine.
  2. 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)

  1. L1: The oracle: an entity Turing left unspecified 'apart from saying that it cannot be a machine'.
  2. L2: State o: the machine pauses and awaits the oracle's decision.

way in: Another machine's description (the universal machine's channel)

  1. 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.
  2. L2: Read square by square through the universal machine's head.
  3. 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.
  4. L4: Matched against the simulated machine's current complete configuration to find the instruction that applies.
  5. 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

  1. L1: The initial tape: a finite string of input symbols, blanks everywhere else (only the blank may appear infinitely often).
  2. 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)

  1. L1: The state register: one of finitely many m-configurations, in the place of a person's state of mind.
  2. 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)

  1. 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.
  2. 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)

  1. L1: A square of the tape bearing a symbol (or blank); the tape is the analogue of squared paper.
  2. 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

  1. L1: A physical machine in the world; bounded, error-prone, paying heat.
  2. L6: A design embodying a Turing machine: relay switches (1937), molecular parts, DNA rewriting, Lego and mechanical models.
  3. 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

  1. L1: The final tape: the output, read by whoever runs the machine (for a busy beaver, the count of 1s is its score).
  2. 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)

  1. L1: At least kT ln 2 of heat per erased bit released into the environment.
  2. L4: A logically irreversible step (an erasure, two paths merged).

way out: Move one square left or right (or stay); change state

  1. L1: A new square under the head: the next scanned symbol.
  2. L3: The next state set in the register.
  3. L4: The instruction selected: L, R or N, and the next m-configuration.

way out: Write or erase the scanned symbol

  1. L1: The square changed: the tape now carries the new symbol for later steps.
  2. L2: The head writes into the scanned square, at most one symbol per simple operation.
  3. L4: The instruction selected: print a symbol, erase, or leave it.

Sources (18) published science

Turing machine (Wikipedia, rev 1380238390, 2026-10-14, via Wikimedia Enterprise snapshot 2026-11-01)
Turing, On computable numbers, with an application to the Entscheidungsproblem, Proc. London Math. Soc. 2-42 (1936-37), doi:10.1112/plms/s2-42.1.230 (open copy, OCR text) (behind its links)
The bbchallenge Collaboration (2025, v2 2026) Determination of the fifth Busy Beaver value. arXiv:2509.12337 (behind its links)
De Mol, L. Turing Machines. Stanford Encyclopedia of Philosophy (first published 24 Sep 2018; substantive revision 21 May 2025) (behind its links)
Kolchinsky, A. & Wolpert, D. H. (2020) Thermodynamic costs of Turing machines. Physical Review Research (arXiv:1912.04685) (behind its links)
Busy beaver (Wikipedia, rev 1382799805, 2026-10-30, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Universal Turing machine (Wikipedia, rev 1377070305, 2026-09-27, via Wikimedia Enterprise) (behind its links)
Neary, T. & Woods, D. (2011) The complexity of small universal Turing machines: a survey. arXiv:1110.2230 (behind its links)
Yedidia, A. & Aaronson, S. (2016) A relatively small Turing machine whose behavior is independent of set theory. arXiv:1605.04343 (behind its links)
Shapiro, E. (2012) A mechanical Turing machine: blueprint for a biomolecular computer. Interface Focus 2, 497-503, doi:10.1098/rsfs.2011.0118 (CC BY; PMC3363030) (behind its links)
Zylberberg, A., Dehaene, S., Roelfsema, P. R. & Sigman, M. (2011) The human Turing machine: a neural framework for mental programs. Trends Cogn. Sci., doi:10.1016/j.tics.2011.05.007 (PMID 21696998; abstract via Europe PMC) (behind its links)
Miranda, E. & Ramos, I. (2026) Two-dimensional billiards are Turing complete. PNAS 123, e2614500123, doi:10.1073/pnas.2614500123 (CC BY; PMC13578349) (behind its links)
Recursion (computer science) (Wikipedia, via Wikimedia Enterprise snapshot 2026-10-01) (behind its links)
Zach R (2025) Sets, Logic, Computation: An Open Introduction to Metalogic (Open Logic Project, Fall 2025, revision 6178f32; CC BY 4.0). Chapters 1 (Sets), 3 (Functions), 4 (The Size of Sets), 14 (Turing Machine Computations) (behind its links)
Currin, A., Korovin, K., Ababi, M., Roper, K., Kell, D. B., Day, P. J. & King, R. D. (2017) Computing exponentially faster: implementing a non-deterministic universal Turing machine using DNA. J. R. Soc. Interface 14, 20160990, doi:10.1098/rsif.2016.0990 (CC BY; PMC5378132) (behind its links)
Bennett CH (2003) Notes on Landauer's principle, reversible computation, and Maxwell's Demon. Stud Hist Philos Mod Phys 34:501-510. arXiv:physics/0210005 (behind its links)
Mathematical logic (Wikipedia, via Wikimedia Enterprise snapshot 2026-11-01) (behind its links)
Draper, T. C., Poros-Tarcali, E. & Pérez-Mercader, J. (2022) pH oscillating system for molecular computation as a chemical Turing machine. ACS Omega 7, 6099-6103, doi:10.1021/acsomega.1c06505 (CC BY-NC-ND; PMC8867811) (behind its links)