Turing machines

Turing machines are abstract computing devices, named after Alan Mathison Turing. A Turing machine operates on a potentially infinite tape uniformly divided into squares, and is capable of entering only a finite number of distinct internal configurations. Each square may contain a symbol from a finite alphabet. The machine can scan one square at a time and perform, depending on the content of the scanned square and its own internal configuration, one of the following operations: print or erase a symbol on the scanned square or move on to scan either one of the immediately adjacent squares. These elementary operations are possibly accompanied by a change of internal configuration. Turing argued that the class of functions calculable by means of an algorithmic procedure (a mechanical, stepwise, deterministic procedure) is to be identified with the class of functions computable by Turing machines. The epistemological significance of Turing machines and related mathematical results hinges upon this identification, which later became known as Turing’s thesis; an equivalent claim, Church’s thesis, had been advanced independently by Alonzo Church. Most crucially, mathematical results stating that certain functions cannot be computed by any Turing machine are interpreted, by Turing’s thesis, as establishing absolute limitations of computing agents.