Turing Machines

A Turing machine M consists of:

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)