Turing Machines

A Turing machine M consists of:

• a finite alphabet A

• a finite set of states S

• an infinite tape containing squares for storing symbols

• a tape head that can read the tape and move along it

• a state transition diagram SxA to SxAx{left,right,none} which based on the current state and symbol under the tape head, moves to a new state, writes a new symbol on the tape, and moves the head left or right one square (or stays put).

One of the states is denoted the "start" state, where all computation begins.

Some of the states are called "halting" states; the computation is assumed to halt when those states are entered.

The machine starts in its start state, with the input to the machine written on the tape, the tape head on the leftmost nonblank square. The machine halts when a "halting" state is reached.

Note the similarity with real computers, despite the fact that Turing machines were invented more than a decade before the first digital computer!

Example machine: Palindromes

The transition function for a Turing Machine to recognize palindromes.

  (0,a) = (1,x,R)    /* State 0 (start state) */
  (0,b) = (2,x,R)    /* We have a palindrome */
  (0,x) = (5,x,L)
  
  (1,a) = (1,a,R)    /* Seen an "a"; skip to right
  (1,b) = (1,b,R)       end of the input */
  (1,x) = (3,x,L)
  
  (2,a) = (2,a,R)    /* Seen a "b"; skip to right
  (2,b) = (2,b,R)       end of the input */
  (2,x) = (4,x,L)
  
  (3,a) = (7,x,L)    /* Test right end for "a" */
  (3,b) = (6,b,L)
  (3,x) = (5,x,L)
  
  (4,a) = (6,a,L)    /* Test right end for "b" */
  (4,b) = (7,x,L)
  (4,x) = (5,x,L)
  
  (5,*) = halt       /* Found a palindrome */
  (6,*) = halt       /* Did not find a palindrome */
  
  (7,a) = (7,a,L)    /* Matched palindrome;
  (7,b) = (7,b,L)       return to left end of input */
  (7,x) = (0,x,R)