```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
| 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.
```