Turing Machine Model

M = ( Q, Sigma, Gamma, delta, q0, B,  F)

 Q = finite set of states including q0
 Sigma = finite set of input symbols not including B
 Gamma = finite set of tape symbols including Sigma and B
 delta = transitions mapping  Q x Gamma to Q x Gamma x {L,R}
 q0    = initial state
 B     = blank tape symbol, initially on all tape not used for input
 F     = set of final states

 +-------------------------+-----------------  
 | input string            |BBBBB ...  accepts Recursively Enumerable Languages
 +-------------------------+----------------- 
    ^ read and write, move left and right
    |
    |  +-----+
    |  |     |--> accept
    +--+ FSM |
       |     |--> reject
       +-----+


 +-------------------------+-----------------  
 | input and output string |BBBBB ...  computes partial recursive functions
 +-------------------------+----------------- 
    ^ read and write, move left and right
    |
    |  +-----+
    |  |     |
    +--+ FSM |--> done  (a delta [q,a]->[empty], but may never happen )
       |     |
       +-----+

  delta is a table or list of the form:
  [qi, ai] -> [qj, aj, L]   or  [qi, ai] -> [qj, aj, R]
                            (optional [qi, ai] -> [qj, aj, N])    
  qi is the present state
  ai is the symbol under the read/write head

  qj is the next state
  aj is written to the tape at the present position
  L  is move the read/write head left one position after the write
  R  is move the read/write head right one position after the write
  N  is optional no movement of the tape.

  It is generally a pain to "program" a Turing machine. You have to
  convert the algorithm into the list of delta transitions. The fallback
  is to describe in English the steps that should be performed.  The
  amount of detail needed depends on the reader of the algorithm
  accepting that there is an obvious way for the Turing machine to
  perform your steps.

  There are a lot of possible Turing machines and a useful technique
  is to code Turing machines as binary integers. A trivial coding is
  to use the 8 bit ASCII for each character in the written description
  of a Turing machine concatenated into one long bit stream.
  Having encoded a specific Turing machine as a binary integer, we
  can talk about  TMi  as the Turing machine encoded as the number "i".

  It turns out that the set of all Turing machines is countable and
  enumerable.

  Now we can construct a Universal Turing Machine, UTM, that takes
  an encoded Turing machine on its input tape followed by normal
  Turing machine input data on that same input tape. The Universal Turing
  Machine first reads the description of the Turing machine on the
  input tape and uses this description to simulate the Turing machines
  actions on the following input data. Of course a UTM is a TM and can
  thus be encoded as a binary integer, so a UTM can read a UTM from
  the input tape, read a TM from the input tape, then read the input
  data from the input tape and proceed to simulate the UTM that is
  simulating the TM.  Etc. Etc. Etc.

  In a future lecture we will make use of the fact that a UTM can be
  represented as an integer and can thus also be the input data on
  the input tape.

  Basically, any algorithm can be coded in a high order language,
  or coded in assembly language,
  or coded as a Turing Machine program,
  or built out of digital logic.

  A Turing Machine program is a bit-by-bit description of an algorithm.
  Each program step, as in assembly language, is one simple operation.
  But at a much lower level than any assembly language.

  A Turing Machine program step is a 'delta' entry

  [qi, ai] -> [qj, aj, move]

  When in state qi, if the read head sees tape symbol ai,
  then transition to state qj, writing symbol aj to the tape and
  moving one tape position according to 'move' which can be 
  L for left, R for right, N for no move.    

  For computer input to a TM simulator, the five items are just
  written with white space as a separator and an optional sixth
  field that is a comment.

  Special character pairs  #b  are used for one blank.
  ## is used for epsilon, nothing written to tape.
  A sample computer input for an algorithm to add unary strings is:


  // add.tm   add unary strings of zeros
  // input tape  000...00 000..00  blank separated, blank at end
  // output tape  000...000  sum of zeros on input tape

  start s0
  halt  s9 // use halt rather than 'final' when computing a result
  limit 20

  s0 0  s0 ## R   skip over initial 0's  delta 1
  s0 #b s1 0  R   write 0 over blank     delta 2
  s1 0  s1 ## R   keep moving            delta 3
  s1 #b s2 ## L   detect at end          delta 4
  s2 0  s9 #b R   blank extra 0          delta 5

  tape 000#b00#b   should end with five zeros on tape

The simulation starts with the TM in state s0 and read head on
the first character.

    +-----------
    |000 00 ----  tape
    +-----------
     ^
     |
     | read/write head position
       TM in state  s0

Thus, delta 1 applies. The new state is the same s0, nothing is
written to the tape and the head is moved one place right.


    +-----------
    |000 00 ----  tape
    +-----------
      ^
      |
      | read/write head position
        TM in state  s0

Following the steps, delta 2 writes a zero over the blank and
goes to state s1.

When in state s1 and a zero is read from the tape, delta 3,
stay in state s1 and move one space right.

When in state s1 and a blank is read from the tape, delta 4,
go to state s2 and back up one space (now over last zero).

When in state s2 and a zero is read from the tape, delta 5,
go to the final state, s9, and write a blank over the zero.

Machine stops when no delta applies. If in a final state
when machine stops, the algorithm (program) finished
successfully.


    +-----------
    |00000  ----  tape
    +-----------
          ^
          |
          | read/write head position
            TM in state  s9

What would happen if there was a '1' on the tape with the
above TM program? The machine would stop in a non-final state
which indicates no answer was computed (like segfault).

video, LEGO Turing Machine