 A Turing machine then, or a computing machine as Turing called it, in Turing’s original definition is a machine capable of a finite set of configurations \(q_{1},\ldots,q_{n}\) (the states of the machine, called m-configurations by Turing). It is supplied with a one-way infinite and one-dimensional tape divided into squares each capable of carrying exactly one symbol. At any moment, the machine is scanning the content of one square r which is either blank (symbolized by \(S_0\)) or contains a symbol \(S_{1},\ldots ,S_{m}\) with \(S_1 = 0\) and \(S_2 = 1\).