Turing Machine

A Turing machine is a mathematical model of computation described by Alan Turing in his 1936 paper On Computable Numbers, consisting of an infinite tape divided into cells, a read write head that moves along the tape, and a finite table of rules the head follows based on the symbol it reads and its own current state. Despite its extreme simplicity, the model is powerful enough to describe any computation a modern computer can perform, a claim known as the Church Turing thesis after Turing and Alonzo Church, who independently reached an equivalent result the same year using a different formalism, the lambda calculus.