**Reading**-
Finish off section 4.1 of
*Theory of Computing, A Gentle Introduction*. **Homework**- Printout the homework and answer the questions on that paper.

**A prefix machine**-
**Problem:**Write an algorithm*P*that takes a symbol*x*and alphabet Σ, and produces a turing machine that prefixes the input string with*x*, leaving the tape head at the first square after the prefixed character.**Algorithm:***P(x,Σ)*

**Input:**symbol*x*, alphabet Σ

**Output:**Machine*M*

M = (Σ ∪ {q0,q1} ,Σ,Σ ∪ {x,$},δ,q0), where $ ∉ Σ, and

δ is given by δ(q0,z) = (z,$,R), for all z ∈ Σ

δ(q0, ) = (h,x,R)

δ(y,z) = (z,y,R), for all y,z ∈ Σ

δ(y, ) = (q1,y,L), for y ∈ Σ

δ(q1,z) = (q1,z,L), for all z ∈ Σ

δ(q1,$) = (h,x,R)

&delta(q,y) = (q,y,S) in all other cases **Roadmap**-
We're going to prove that there are some languages that cannot
be decided by Turing Machines. In order for that result to
pack any punch, however, I need to convince you that if a
Turing Machine can't do it, it can't be "computed" in any
reasonable sense. This assertion is known as the
Church-Turing thesis.
If you think about it, our definition of a TM is pretty arbitrary. For instance, I choose to say it has a 1-way infinite tape with no special way to mark the left-most square on the tape as being "the end". The book chose a 1-way infinite tape with a special marker for the first square that could never be overwritten, and from which one could never move left. On the other hand, JFLAP chose a 2-way infinite tape, which avoids the whole marking-the-first-square problem. Now, if I prove that a language can't be decided by any machine conforming to our TM model, what's to say that a JFLAP-style or Book-style machine couldn't decide it? What about machines with multiple tapes? Random access memory? An infinite 2-dimensional grid of memory cells? Higher-dimensional lattices of squares? In short, with so many possible models of what it means to "compute", who cares if our little model has limitations?

The remarkable thing is that all of these fancy models of what it might mean to compute have exactly the same "computational power" as our simple Turing Machine model. So if we prove something is impossible in our model, it's impossible in any of those models!

**"Computational Power"**-
To even begin to compare different models of what a Turing
Machine might be,
we need to come up
with a definition of "computational power", preferrably one
that we can acutally use to compare different models of
computers. Certainly we felt comfortable saying that a PDA
is more powerful than a DFA, but that an NDFA is not more
powerful than a DFA. What was our yardstick for
"computational power" when we made these claims? It was the
languages that could be accepted by a given model of computation.
DFAs and NDFAs are capable of accepting all the same
languages. PDAs, on the other hand, can accept anything a
DFA/NDFA can, but can accept other languages as well.
Now, TMs can both decide languages and semi-decide languages
so:
**Defintion**Two Turing machine models have the same computational power if the set of languages they can decide is the same, and the set of languages they can semi-decide is the same. **The book's model**-
Let's say that a "Bookish TM" conforms exactly to our model,
except that there is a special symbol $ in the first sqare of
the tape, which is not an element of Σ, which can't
be written on any other square, and which cannot be
overwritten. Formally,
A

*Bookish Turing Machine*is a 5-tuple*(Q,Σ,Γ,δ,s)*where*Q*is the set of states,*h ∉ Q*- Σ is the input alphabet, $ ∉ Σ
- Γ is the alphabet of symbols that may appear on the tape at any point in the computation, exluding the blank character and $
- δ is the transition function
*δ: Qx(Γ∪{ ,$}) → (Q∪{h})x((Γ∪{ ,$})x{L,R,S}**δ(q,$) ∈ Qx{$}x{R,S}*and*δ(q,x) ∉ (Q∪{h})x{$}x{L,R,S}*if*x ≠ $*. (i.e. you can't move left from $, and $ gets written to the first cell and only the first cell.) *s*is the start state

*(Q,Σ,Γ,δ,s)*on input*w = w1w2...wk*is (q,$,w1,w2...wk).Just to understand what's going on, here's a JFLAP rendition of a Bookish Turing Machine that decides the language of all strings over {a,b} whose length is odd, along with its formal defintion as a tuple.

( {q0,q1,q2,q3},{a,b},{a,b}, a b $ q0 (q1, ,R) (q1, ,R) (q0, ,L) (q2,$,R) q1 (q0, ,R) (q0, ,R) (q0, ,L) (q3,$,R) q2 (q2,a,S) (q2,b,S) (h,0,S) (q2,$,S) q3 (q3,a,S) (q3, ,S) (h,1,S) (q3,$,S) ,q0 ) *abb*as input. Its computation is then:(q0,$,a,bb) ⇒ (q1,$ ,b,b) ⇒ (q0,$ ,b,λ) ⇒ (q1,$ , ,λ) ⇒ (q1,$ , ,λ) ⇒ (q1,$ , ,λ) ⇒ (q1,$, ,λ) ⇒ (q1,λ,$,λ) ⇒ (q3,$, ,λ) ⇒ (h,$,1,λ)

Notice that if

*M = (Q,Σ,Γ,δ,s)*is a Bookish TM,*M' = (Q,Σ∪{$},Γ∪{$},δ,s)*satisfies our definition of a a TM. So we could run our TM*M'*and get the same result as running the Bookish TM*M*, provided our input had an extra $ prefixed to it. Intuitively, we could run the machine*P($,Σ)*from above to do the prefixing, then run*M'*, and we'd get exactly what the the Bookish TM got. But we have no way of chaining together two Turing Machines to act as a single machine. Let's make it up! A diagram like*machine schema*, and the meaning is that after machine*M1*halts, you run machine*M2*with the tape contents and tape head exactly as*M1*left it.**The important point**is that we can write down an algorithm that takes a machine schema as input and produces a single Turing Machine that does exactly what the schema does. Thus, machine schema are just a notational convenience, not a new model. By analogy to introductory programming, a single TM is like writing a program with everything in`main`

, and machine schemas are like allowing function definitions. (Can you come up with an algorithm that creates a single machine from this schema? Think about it!)**To continue:**Thus, given the Bookish Turing machine*M*above, we use the machines*P($,Σ)*and*M'*in the following schema:>

The machine realizing this schema*P($,Σ)*→*M'**simulates**M*; i.e. it halts on input*w*if and only if*M*halts on input*w*, and if it halts, the contents of the tape upon halting and the position of the tape head are exactly what they are for*M*when it halts. Thus, the machine realizing this schema decides/semi-decides exactly what*M*does, proving that Bookish TM's are no more powerful than our TM's.The other direction - i.e. that a Bookish TM can simulate one of our TM's - is even easier. So we have a new theorem:

**Theorem:**Bookish Turing machines and our class's Turing machines are computationally equivalent.

**Proof:**We have an algorithm that takes a Bookish Turing Machine*M*and converts it into one of our Turing Machines as described above. Now, suppose for some input string w = w1w2...wk, we have(s,$,w1,w2...wk) ⇒*

This means that the initial configuration for the Bookish TM_{M}(q,u,x,v)*M*eventually leads to configuration (q,u,x,v). Clearly, it's also true that(s,$,w1,w2...wk) ⇒*

i.e. that the machine_{M'}(q,u,x,v)*M'*goes through the same sequence of configurations if you start at configuration (s,$,w1,w2...wk). However, that's not the initial configuration for*M'*on input*w*. To prove that there is a TM of our type that is*equivalent*to*M*, we need a machine lands in configuration (q,u,x,v) from its own initial configuration, not from the initial configuration of*M*. Now, let*H*be the TM of our type that realizes the schema >*P($,Σ)*→*M'*. Where does*H = (Q',Σ',Γ',δ',s')*go from its initial configuration on input w = w1...wk, i.e. (s',λ,w1,w2...wk)? Well, running*H*is the same as running*P($,Σ)*and then running*M'*from the configuraiton*P($,Σ)*halted in, except with the halt state replaced with the start state for*M'*. Let's call the start state of*P($,Σ)*s1, and of course the start state of*M'*is s, as above.(s1,λ,w1,w2...wk) ⇒*

This means that the machine_{P($,Σ)}(h,$,w1,w2...wk), (s,$,w1,w2...wk) ⇒*_{M'}(q,u,x,v)*H*realizing our schema must give us(s,λ,w1,w2...wk) ⇒*

So starting with the same input_{H}(q,u,x,v)*w*,*H*goes through every configuration the Bookish Machine*M*goes through during its computation. So they are computationally equivalent.

Christopher W Brown Last modified: Mon Nov 30 12:24:11 EST 2009