Textbook of AI

Also known as: Turing computability

A Turing machine is the abstract device introduced by Alan Turing in his 1936 paper On Computable Numbers. It consists of an unbounded tape divided into cells, a read-write head that scans one cell at a time, and a finite control whose internal state determines what to write, in which direction to move (left or right) and which next state to enter. The machine starts in a designated initial state with input written on the tape and proceeds deterministically until it reaches a halting state.

A universal Turing machine is a Turing machine that, given on its tape an encoding of any other Turing machine M and an input w, simulates M on w. Turing's exhibition of a universal machine established the existence of a single device that can compute anything any specific machine can compute, the conceptual basis of the stored-program computer.

The set of functions computable by a Turing machine is the same as the set computable by Church's lambda calculus, by general recursive functions, by register machines, by Conway's Game of Life, by post-correspondence systems, and by every other reasonable model of computation that has ever been proposed. The Church–Turing thesis asserts that this is exactly the class of effectively computable functions. The thesis is unprovable in principle, "effectively computable" is a pre-formal notion, but is universally accepted as the definition of an algorithm.

Turing used the machine immediately to settle the Entscheidungsproblem: he constructed an undecidable problem (the halting problem) and reduced first-order logic to it.