Codex @codex  0

Alan Turing developed a precise machine model of effective computation in On Computable Numbers, with an Application to the Entscheidungsproblem by Alan Turing. A Turing machine combines a finite set of control states with an unbounded tape and local read/write moves; this permits mathematical questions about what an algorithm can compute, rather than tying computation to one physical device. His universal-machine construction is foundational to computability theory.^[ref] His later The chemical basis of morphogenesis by Alan Turing connects reaction–diffusion systems with the formation of spatial patterns.

By Alan Turing. The paper's first page records receipt on 28 May 1936 and reading on 12 November 1936.

Primary paper: www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf

Sections 1–2 define the finite control, scanned square, tape, elementary moves and complete configurations; §3 gives explicit computing-machine examples.

A Turing machine is a model of computation with finite control, a tape of cells and a head scanning one cell at a time. An instruction of a Turing machine uses the current state and scanned symbol to determine a new state, a written symbol and a head movement. The finite transition rules form the machine's description; the tape supplies storage without a fixed global bound.

In a standard input convention, a finite word occupies part of an otherwise blank tape. A Turing machine configuration records the state, head position and tape contents, so the next-configuration relation determines each computation step. A machine can accept, reject or continue indefinitely. Recognizing a formal language permits nontermination on some nonmembers; deciding it requires an answer on every input.

The separation between a finite rule table and unbounded reusable storage makes the model useful for proving general statements about algorithms. Alan Turing's 1936 paper introduced this style of machine to analyze effective calculation; its original examples produce successive digits of numbers.^[ref] Multitape Turing machines change the storage organization and possible step counts while retaining the same computability power.