**Reading**-
Sections 4.2 of
*Theory of Computing, A Gentle Introduction*. **Homework**- Printout the homework and answer the questions on that paper.

**A formal definition of JFLAP's TM model**-
A JFLAP TM is 6-tuple

*M = (Q,Σ,Γ,δ,s,W)*where*Q*is the set of states*Σ*is the input alphabet*Γ*is the tape alphabet ( ∉ Γ)-
*δ*is the transition function*δ:(Q - W) x (Γ ∪ ) &rarr Q x (Γ ∪ ) x {L,R,S}* *s*the start state,*s ∈ Q**W*the set of halt states

Of course the important feature of the model is its 2-way infinite rather than 1-way infinite tape. The tuple representing the JFLAP TM doesn't seem to say anything about that. Well, that's because the actual

*operation*of the machine, including such details as 2-way tapes, is captured by the notions of*configuration*and*yields in one step*(i.e. ⇒), and they are different for JFLAP TMs than for our TMs.The notion of configuration for JFLAP TMs is really the same as for our TMs. The only technical difference is that for our TMs we kept track of all characters from the first tape square up to the tape head. For a JFLAP TM that doesn't make any sense because there is no "first tape square". Therefore, we simply track from the tape head left up to the leftmost non-blank character.

A

*configuration*of a JFLAP Turing Machine*M = (Q,Σ,Γ,δ,s,W)*is a 4-tuple (q,u,x,v) ∈ Q x (Γ ∪ { })* x (Γ ∪ { }) x (Γ ∪ { })* where*q*is the current state,*u*is the string of all characters to the left of the tape head up to and including the first non-blank cell on the tape (note that*u*is the empty string if every cell to the left of the tape head is blank),*x*is the symbol in the cell pointed to by the tape head, and*v*is the string of all symbols to the right of the tape head up to and including the symbol in the last non-blank cell (note that*v*is the empty string if every cell to the right of the tape head is blank).

The "yields in one step" relation is where the rules of a machine are defined - and where JFLAPs 2-way infinite tape enters the picture.

For JFLAP Turing Machine M = (Q,Σ,Γ,δ,s,W) configuration (q,u,x,v)

The 2-way infinite tape is reflected by the fact that a left move is allowed even if u=λ. If you go back to the definition of yields-in-one-step for our Turing Machines, you'll notice that there is no "next configuration" defined for a left move with u=λ.*yields*(q',u',x',v')*in one step*if, letting δ(q,x) = (p,y,d):(q',u',x',v') = (p,u,y,v) if d = S (p,uy,v _{1},v_{2}...v_{k}) if d = R and v = v_{1}v_{2}...v_{k}(Note: if u = λ and y = , replace uy with λ)(p,uy, ,λ) if d = R and v = λ (Note: if u = λ and y = , replace uy with λ) (p,u _{1}...u_{m-1},u_{m},yv) if d = L and u = u_{1}u_{2}...u_{m}(Note: if v = λ and y = , replace yv with λ)(p,λ, ,yv) if d = L and v = λ (Note: if v = λ and y = , replace yv with λ) **Our TM is as powerful as JFLAP's TM: i.e. a 2-way infinite tape doesn't buy you anything**-
The basic difference between JFLAP's Turing Machine model and
ours is the 2-way infinite tape. When you think about it,
it seems like a TM with a 2-way infinite tape should be more
powerful. After all, it's got more options. What we're going
to do is show that, in fact, JFLAP's model is not more
powerful. Given a JFLAP TM, we can construct one of our TM's
that is equivalent, i.e. decides or semi-decides the
same language. We'll do this by
*simulating*a 2-way infinite tape on our 1-way infinte tape.Imagine dividing your tape horizontally, so each cell has an upper and lower part. This allows us to simulate a 2-way infinite tape, because characters in the upper part will be interpreted as belonging to the right half of the simulated 2-way tape, and characters in the lower part will be interpreted as belonging to the left half of the simulated 2-way tape. Now, we'll need to know where the left end of our 1-way tape is, so as not to fall off and crash the machine, so we'll assume the first square has some distinct, unique symbol (like $) that doesn't appear anywhere else. The following figure shows how we simulate a 2-way tape with our 1-way tape:

So here's an algorithm that takes a JFLAP TM and constructs one of our TM's to simulate it. We're assuming that the input is given to us with a $-prefixed to the front. Ultimately we'll simply run the prefix machine from above to do that for us before we run our simulating machine. Since we can't literally split each of our machine's cell's in two, we instead add new "symbols" that are really ordered pairs of symbols from the JFLAP TM. The left symbol of the ordered pair represents the "upper" symbol, and the right represents the lower symbol.

**Input:**JFLAP TM*M = (Q,Σ,Γ,δ,s,W)*

**Output:**TM*M' = (Q x {+1,-1}, Σ∪{$}, Γ∪{$}∪(Γ∪{ })*, where^{2}, δ',(s,+1))*δ((q,d),x) =**((q,-d),$,R)*if *x = $**((q,d),(x, ),S)*if *x ∈ Γ ∪ { }**((q',d),(x'*_{1},x_{2}),M)if *d = +1*, where*x = (x*and_{1},x_{2})*δ(q,x*_{1}) = (q',x'_{1},M)*((q',d),(x*_{1},x'_{2}),M')if *d = -1*, where*x = (x*,_{1},x_{2})*δ(q,x*, and_{2}) = (q',x'_{2},M)*M' is S if M=S, R if M=L, L if M=R*.*(h,x*_{1},S)if *q ∈ W*and*d = 1*, where*x = (x*_{1},x_{2})*(h,x*_{2},S)if *q ∈ W*and*d = -1*, where*x = (x*_{1},x_{2})**Theorem:**JFLAP's TM model and our TM model have the same computational power.

**Proof:**The above algorithm shows that our model can be used to decide/semi-decide any language that can be decided/semi-decided by JFLAP's model. It's easy use JFLAP's TM model to simulate a machine of our TM model, so our JFLAP's model can be used to decide/semi-decide any language that can be decided/semi-decided by our model.Now, to really prove that the above algorithm works we need to consider the sequence of configurations that the JFLAP TM M goes through in a computation versus the sequence of computations that TM M' goes through. What we saw in class was that M' goes through a longer sequence of configurations, but that its sequence of configurations includes configurations that map to each configuration in the sequence of configurations M goes through. Thus, M halts on input w if and only if M' halts on input w (with the $ prefixed), and M halts with a (or non- ) where the tape head is pointing if and only if M' halts with a (or non- ) where the tape head is pointing.

Christopher W Brown Last modified: Fri Dec 4 11:37:07 EST 2009