Turing machine

A Turing machine is an abstract model of computation that reads and writes symbols on an unbounded tape according to finite rules. It provides a precise framework for defining algorithms and computability.

Turing machine configuration: A snapshot of a Turing machine’s state, tape contents, and head position. A computation advances by changing one configuration at a time.
Algorithm: A finite, precisely specified procedure for solving a problem or carrying out a computation. Turing machines give a formal model for algorithmic procedures.
Alan Turing: A British mathematician and computer scientist whose work founded theoretical computer science. Turing introduced the machine model in his 1936 analysis of effective calculation.
Halting problem: The problem of deciding, for any program and input, whether the program eventually stops. Turing machines make the impossibility of a general halting test precise.
Lambda calculus: A formal system for expressing computation through function abstraction and application. It defines computability differently yet matches Turing machines in computational power.
Transition function: A rule mapping a machine’s current state and scanned symbol to a new state, symbol, and head movement. It specifies each permitted step of the machine.
Formal language: A set of finite strings over a specified alphabet. Machines can recognize languages by accepting or rejecting input strings.
On Computable Numbers, with an Application to the Entscheidungsproblem: Alan Turing’s 1936 paper introducing machines that manipulate symbols to formalize computation. This paper presented the model while addressing the decision problem.
Decidable problem: A decision problem for which an algorithm always terminates with the correct yes-or-no answer. A machine decides a problem when it halts with the correct answer on every input.
Finite-state machine: A computational model with finitely many states and no unbounded memory. Its limited storage makes it less powerful than a Turing machine.

Linked from 53 pages