Turing Machines and Recursive Functions
Arto K. Salomaa · Cambridge University Press eBooks · 1985
A GENERAL MODEL OF COMPUTATION As is true for all our models of computation, a Turing machine also operates in discrete time. At each moment of time it is in a specific internal (memory) state, the number of all possible states being finite. A read-write head scans letters written on a tape one at a time. A pair ( q, a ) determines a triple ( q ′, a ′, m ) where the q's are states, a's are letters, and m (“move”) assumes one of the three values l (left), r (right), or 0 (no move). This means that, after scanning the letter a in the state q , the machine goes to the state q ′ writes a ′ in place of a (possibly a ′ = a , meaning that the tape is left unaltered), and moves the read-write head according to m . If the read-write head is about to “fall off” the tape, that is, a left (resp. right) move is instructed when the machine is scanning the leftmost (resp. rightmost) square of the tape, then a new blank square is automatically added to the tape. This capability of indefinitely extending the external memory can be viewed as a built-in hardware feature of every Turing machine. The situation is depicted in Figure 4.1.