Turing machine

Summary

A Turing machine is an abstract model of computation with a finite set of states and an unbounded tape of symbols. A moving head reads and writes the symbols one cell at a time. Alan Turing introduced it in 1936 to make the notion of an algorithm precise. A function is computable when some Turing machine computes it, and by the Church–Turing thesis this matches the informal idea of an algorithm. Turing machines are the standard model in computability theory and in complexity theory.