October 27

* Neither FSM nor PDA can be regarded as truly general models for computers
  They cannot recognize some simple languages {a^n b^n c^n: n >= 0}.

  Turing machines are more general than FSM and PDA

  Turing machines are very similar in their workings to FSM and PDA

  Although primitive, attempts to strengthen TM do not give any additional
  capabilities
     - many tapes
     - fancier memory (RAM)

  Turing machines form a stable and maximal class of computational devices
  in terms of the types of computations they can perform


* Turing Machines

  A TM is an automata with a one-way infinite input tape


     +--+--+--+---+--+--+--+
     |a1|a2|a3|...|an|  |  |...   INFINITE
     +--+--+--+---+--+--+--+
     \___^__________/ ^  ^
	 |       |    |  |
	 |       |   BLANKS...
	 |       +--------------- INPUT
	 | READ/
	 | WRITE
    +--------------------+
    |   FINITE CONTROL   |
    |                    |
    |     <-------->     |
    +--------------------+
       O             O


   TM M = (K, Sigma, delta, s, H)

      K:  finite set of states
      Sigma:  alpha containing "blank symbol" B and "left end symbol"  $
      s:  s in K is the initial state
      H:  H <= K is the set of halting states
      delta:  delta:(K-H)xSigma -> KxSigmax{<-, ->, S}) is the
	      transition function such that

	      a) forall q in K-H, if delta(q,$) = (p,b,m) then b neq <-
	      b) forall q in K-H and a in Sigma,
		 if delta(q,a) = (p,b,m) then b neq $

      In one step, M can read a symbol, and write a new one in its place,
      change state, and move the read/write head
      (note this is different from the book, where M either writes a new
       symbol or moves, but not both).

      delta(k,a) = (p,b,m) means "From state s scanning "a", replace "a" with
	 "b", change to state p, and move m.

      Note that when "$" is seen we never overwrite the left end symbol but
      simply recognize it and move right.

      Note that delta is not defined on states in H - when the machine reaches
	 a halting state, the operation stops.



   A "configuration" of a TM M = (K, Sigma, delta, s, H) is a member of
   K x (Sigma* union $) x (Sigma*(Sigma - {B}) union {e})

   Configurations represent current state, tape up to and including head,
   tape to the right of the head)

   All configurations start with left end symbol
   No configurations end with a blank unless the blank is being scanned.
   A configuration whose state is in H is a "halted configuration".

   Simplified notation:  (q, wa, u) can be written as (q, w_au)
   (_a is underline a).


*  Example

   M = ({q0, q1, q2, q3, q4}, {0,1}, delta, q0, {q4})

                             Scanning

   State|     0        1        X        Y        B
   -----+---------------------------------------------
    q0  | (q1,X,R)     -        -    (q3,Y,R)     -
    q1  | (q1,0,R) (q2,Y,L)     -    (q1,Y,R)     -
    q2  | (q2,0,L)     -    (q0,X,R) (q2,Y,L)     -
    q3  |    -         -        -    (q3,Y,R) (q4,B,R)
    q4  |    -         -        -        _        -

   This machine ends up in state q4 whenever the input is
   of the form 0^i 1^i, i>= 1.

   (q0, $_000111) |- (q1, $X_00111) |- (q1, $X0_0111) |- (q1, $X00_111) |-
   (q2, $X0_0Y11) |- (q2, $X_00Y11) |- (q2, $_X00Y11) |- (q0, $X_00Y11) |-
   (q1, $XX_0Y11) |- (q1, $XX0_Y11) |- (q1, $XX0Y_11) |- (q2, $XX0_YY1) |-
   (q2, $XX_0YY1) |- (q2, $X_X0YY1) |- (q0, $XX_0YY1) |- (q1, $XXX_YY1) |-
   (q1, $XXXY_Y1) |- (q1, $XXXYY_1) |- (q2, $XXXY_YY) |- (q2, $XXX_YYY) |-
   (q2, $XX_XYYY) |- (q0, $XXX_YYY) |- (q3, $XXXY_YY) |- (q3, $XXXYY_Y) |-
   (q3, $XXXYYY_B) |- (q4, $XXXYYY_B)

   The symbol |- means "yields in one step".

   A "computation" by M is a sequence of configurations C0, C1, ..., Cn, for
   some n >= 0 s.t. C0 |-M C1 |-M C2 |-M ... |-M Cn.
   The computation is of "length" n or equivalently has n "steps", and we can
   say C0 |-nM Cn.


* Acceptance by a TM

   Let M be a TM such that H = {y,n}.  These halting states correspond to
   "yes" and "no".  Any halting configuration containing y is an "accepting
   configuration", and any halting configuration containing n is a "rejecting
   configuration".

   We say M "accepts" input w if (s, $w) yields an accepting configuration.
   M "rejects" input w is (s, $w) yields a rejecting configuration.

   M "decides" a language L if for every w in L M accepts w and for every
   w not in L M rejects w.

   If a TM decides a language L then L is "recursive".


   For our example, let q4 be the "y" state.  Then the input string
   000111 is accepted by M, and M decides {0^i 1^i: i>=1}.


   Note that if M does not accept some w, we may not be able to determine
   this...

   M may reject by never halting....  We may not be able to determine this by
   inspecting M, w, and/or simulating M or w.  Perhaps if M ran longer - it
   would accept?


   Recursively Enumerable Languages (r.e.)
      = {L:  there exists M s.t. L = L(M)}

   M "semidecides" L if for any string w in Sigma* w in L iff M halts
      on input w.

   Recursive Languages (nice ones)
      = {L:  there xists M s.t. L = L(M) and further, for all w in Sigma*,
	    M halts on input w, i.e., there exists alpha1, alpha2 s.t. either
	    iw |-* alpha1 k_accept alph2, or iw |-* alpha1 k_reject alpha2}

   If L is recursively enumerable we can determine if w in L, but not
      necessarily if w not in L.  Thus we do not have an algorithm for
      determining whether or not w in L.

   If L is recursive then there exists an algorithm (TM) for testing membership
      in L.


   Example

      L = {a^n b^n c^n:  n >= 1} is not context-free, but it is recursive.

      Go back and forth "marking" "a"s, "b"s, and "c"s one character at a time.
      A represents marked "a"
      B represents marked "b"
      C represents marked "c"

      At any time, the tape will contain something like
	 AAAaaa...BBBbbb...CCCccc...

      delta(k0,a) = (k1, A, R)  Mark single "a" by changing it to A

      delta(k1,a) = (k1,a,R)
      delta(k1,B) = (k1,B,R)  Find next "b" while moving right
      delta(s1,b) = (s2,B,R)  Mark the "b" by changing it to B

      delta(k2,b) = (k2,b,R)
      delta(s2,C) = (s2,C,R)  Find next "c" while moving right
      delta(k2,c) = (k3,C,L)  Make the "c"

      delta(k3,X) = (k3,X,L)  For X in {C,B,b,a}...go back to first unmarked "a"
      delta(k3,A) = (k0,A,R)  We moved one cell too far to the left.  Move one
			      cell right; start at k0 to begin another round.


      Show graph notation


      +--+ a/A,R  +--+
      |k0|------->|k1|   etc.
      +--+        +--+

      Lack of transition means error state


   How does the computation end?

   Most errors are handled by lack of transitions.
   Thus, if "c" is found while looking for a "b" (in state k1) it means that
   there are too few "b"s and the machine rejects the nput by having no
   applicable transition.

   To make the machine recursive, add transitions for each error case
   that lead to a reject state.

   How do we accept the strings?

   delta(k0,B) = (k_check,B,R)  Last "a" has been marked so a "b" is found in k0

   where k_check is a state responsible for verifying that all "b"s and "c"s
   have been marked.

   If not - go to k_reject
   If so  - go to k_accept

   k_check transitions left as an exercise.


* Relationships between classes of languages

   Regular < CFL < CSL < Recursive < Recursively Enumerable

   Note that {a^n b^n c^n:  n>=1} is in Recursive - CFL.