Turing machine
a hypothetical machine designed in the 1930s to determine whether an algorithm could be described and used to prove any mathematical problem that was provable. The Turing machine consisted of four components: an alphabet of tokens, a finite-state machine, an infinite tape, and a read–write head that was used for reading and recording information produced by the finite-state machine from and onto the tape. The tape was infinite only in that it was expected that the read–write head would always be supplied with data as well as have space to write new data. There are multiple ways of describing the state of the Turing machine. One approach is with a set of five values, supplied by the alphabet of tokens: (a) the state of the finite-state machine, (b) the token read from the tape, (c) the token written to the tape, (d) the instruction for moving the read–write head, and (e) the next state of the finite-state machine. Sets of these patterns of five tokens
make up the program for the machine. When the program is able to be located on the tape of the machine, it is called a universal Turing machine. It was later demonstrated that the Turing machine was an example of a class of maximally powerful machines that could compute any function that was computable. See also Gödel’s proof. [Alan Mathison Turing (1912–1954), British mathematician]