Turing Machine
A Turing machine is the abstract model of computation that Alan Turing introduced in his 1936 paper "On Computable Numbers, with an Application to the Entscheidungsproblem": a finite control that reads and writes symbols on an unbounded tape, one cell at a time, following a fixed table of rules. Turing called these devices "automatic machines," and the name Turing machine came later. It is not a design for a computer anyone would build. It is a deliberately minimal definition of what a step-by-step mechanical procedure is, chosen so that statements about all possible procedures could be proved.
The model has four parts, and each is as small as Turing could make it. The tape is a one-dimensional strip of cells, each holding a symbol from a finite alphabet (often just 0, 1 and a blank), and it is unbounded in length, meaning no fixed limit, though only finitely many cells are ever used at any moment. The head scans one cell at a time, can overwrite the symbol, and can move one cell left or right. The machine is always in one of finitely many states, which play the role of a bounded memory, like the human computer's momentary state of mind in Turing's own analogy. The transition table lists, for each pair of state and scanned symbol, what symbol to write, which way to move, and which state to enter next. That is everything.
The worked example in the paper shows how little machinery is needed. Turing's first machine prints the sequence 0 1 0 1 ... forever, leaving blank squares between the digits to use as scratch space, using a short table of rules that cycles through a few states. A binary incrementer, a machine that checks whether a string of brackets is balanced, and a machine that adds two unary numbers each take only a handful of states. This is the sense in which the model is both trivial and complete: every extra feature of a real computer, from registers to subroutines, can be compiled down to such a table, at the cost of enormous slowdown.
The Church-Turing thesis says that this minimal model captures the informal idea of computability, and it is a thesis, not a theorem. In 1936 Alonzo Church had defined an equivalent notion using the lambda calculus, and Turing showed that his machines and Church's lambda-definable functions compute the same functions; Kurt Gödel's recursive functions and later models, including register machines and modern programming languages, turned out equivalent as well. Because "effective procedure" is an informal notion, the claim that nothing more powerful exists cannot be formally proved, but decades of failed attempts to find a counterexample make it one of the best-supported working assumptions in science. The phrase "Church-Turing thesis" was popularized later, notably by Stephen Kleene.
The halting problem is the model's most celebrated limit. Using a diagonal argument in the spirit of Georg Cantor and Gödel, Turing showed that no Turing machine can examine an arbitrary machine and input and always correctly report whether the computation eventually stops; the name "halting problem" was attached later, and Turing's own formulation concerned whether a machine would ever print a certain kind of symbol, but the argument is the same. Since a general decision procedure for logic would solve it, the Entscheidungsproblem has no solution. The result generalizes: Rice's theorem later showed that every non-trivial question about what a program computes is undecidable, which is why perfect bug detectors and perfect virus scanners cannot exist.
The model's modern role is as the ruler against which all computation is measured. Complexity theory defines the classes P and NP in terms of Turing machines, "Turing complete" labels languages capable of anything a Turing machine can do, and proofs that some problem is uncomputable or intractable are usually carried out against this model. For AI, it frames both the optimistic and pessimistic arguments: if thinking is computation, a Turing machine can in principle do it, which is the premise of the later computational theory of mind, while limits such as undecidability set boundaries on what any program can guarantee about its own behavior.
Frequent errors include treating the infinite tape as a practical defect and the machine as a model of an actual computer. Real machines have finite memory, so they are in the strict sense finite automata, and the unbounded tape is an idealization meaning "as much as needed." Another confusion is equating the halting problem with an inability to analyze any particular program; many programs can be proved to halt, and the theorem rules out only a single procedure that works for all of them. A third is crediting Turing with the stored-program computer on the basis of this model alone, a topic better handled by universal-computing-machine.
Read the Turing machine as a definition, not an invention: a minimal specification of "following rules mechanically" that is precise enough to prove both what such rule-following can achieve and what it never will.