A Turing machine is a mathematical model of computation consisting of a finite controller, an unbounded tape divided into cells, and a head that reads and writes symbols. Introduced by Alan Turing in 1936, it gives a precise framework for studying what an algorithm can compute. Despite its elementary operations, the model can simulate general-purpose computation when sufficient time and storage are available. It is foundational to computer science, computability theory, and computational complexity. (theory.stanford.edu)
Historical origin
Turing developed the model in On Computable Numbers, with an Application to the Entscheidungsproblem. His starting point was a person performing a calculation through explicit rules, using written symbols and a limited number of distinguishable mental states. The machine abstracts this activity rather than describing a particular electronic device. Turing initially emphasized machines producing digit sequences, including representations of computable real numbers. (theory.stanford.edu)
The work addressed the Entscheidungsproblem, associated with David Hilbert: whether a general effective procedure could determine the validity of arbitrary formulas in first-order logic. Turing established a negative result. His paper also connected machine computability with Alonzo Church’s independently developed account of effective calculability. (theory.stanford.edu)
Structure and operation
The tape supplies storage. Each cell contains one symbol from a finite alphabet, including a distinguished blank symbol. An input is normally a finite string written on an otherwise blank tape. The head scans one cell at a time; the controller’s state and the scanned symbol determine the next action. Each transition writes a symbol, changes state, and moves the head one cell left or right. (people.csail.mit.edu)
A common deterministic definition specifies seven components:
[ M=(Q,\Sigma,\Gamma,\delta,q_0,q_{\mathrm{accept}},q_{\mathrm{reject}}). ]
Here (Q) is the finite state set; (\Sigma) is the input alphabet; (\Gamma) is the tape alphabet, containing (\Sigma) and the blank; (\delta) is the transition rule; and the remaining components designate the initial, accepting, and rejecting states. Entering either terminal state ends the computation. For nonterminal states, the rule has the form
[ \delta(q,a)=(q',b,D),\qquad D\in{L,R}. ]
This means: in state (q), reading (a), write (b), enter (q'), and move in direction (D). (people.csail.mit.edu)
A configuration records the current state, head position, and tape contents. The tape is unbounded, but only finitely many cells can be visited during any finite computation. Unlimited capacity therefore does not imply that a machine performs infinitely many operations in one step. (ocw.mit.edu)
Computing functions and recognizing languages
A machine can compute a function by taking an encoded argument as input and leaving an encoded result when it halts. If it fails to halt for some arguments, it computes a partial rather than a total function. Numbers and other structured objects must first receive finite symbolic representations. (live.ocw.mit.edu)
For decision problems, inputs are strings belonging or not belonging to a formal language. A decider halts on every input, accepting members and rejecting nonmembers. A recognizer must accept every member, but may reject or run indefinitely on nonmembers. Thus recognizing a language is weaker than deciding it: the absence of acceptance need not provide a terminating negative answer. (mitp-content-server.mit.edu)
Universality and the Church–Turing thesis
A universal Turing machine takes an encoded machine description together with that machine’s input and simulates its execution. A single fixed transition table can consequently carry out many different computations: the program becomes data supplied on the tape. This provides a mathematical paradigm for a general-purpose computer. (theory.stanford.edu)
The Church–Turing thesis states that every effectively calculable function is Turing-computable. It connects an informal notion of rule-governed calculation with a formal model, rather than being an ordinary theorem proved from mathematical definitions. Independently defined models, including lambda calculus and recursive-function formalisms, have equivalent computational power. (ocw.mit.edu)
A programming language or computational system is Turing-complete if it can simulate arbitrary Turing-machine computations under appropriate unbounded-resource assumptions. Physical computers have finite memory, so this characterization concerns their idealized computational capabilities, not unlimited actual storage. (live.ocw.mit.edu)
Limits of computation
The halting problem asks whether a given machine eventually stops on a given input. No Turing machine decides this question correctly for every machine–input pair. A standard proof by contradiction supposes that such a decider exists, then constructs a program that does the opposite of its prediction when applied to its own description. The resulting self-reference makes either prediction inconsistent. (ocw.mit.edu)
Undecidability is different from excessive running time. An undecidable problem lacks a universally correct terminating algorithm in this model; a decidable problem may nevertheless require impractical resources. (ocw.mit.edu)
Variants and resource measurement
Multitape machines have several tapes and independently moving heads. A nondeterministic Turing machine permits several possible transitions and accepts when some computation branch accepts. These variants do not enlarge the class of computable problems, although they can change resource requirements. (math.mit.edu)
Time complexity counts computational steps as a function of input length, while space complexity measures storage used. Exact bounds depend on machine conventions. A standard simulation converts a multitape computation taking (t(n)) steps into a single-tape computation taking (O(t(n)^2)) steps, assuming (t(n)\geq n). Such comparisons distinguish computational power from computational efficiency and explain why resource analyses must specify their model. (ocw.mit.edu)