Class 37: Eqivalence of JFLAP's TMs and our TMs


Reading
Sections 4.2 of Theory of Computing, A Gentle Introduction.
Homework
We have seen formal definitions of 3 different models of Turing Machines: the class's, the book's and JFLAP's. Give a formal definition of a Turing machine that has two 1-way infinite tapes, and a separate read/write head for both of them. The trick is going to be to figure out what the transition function will look like for one of these.

A formal definition of JFLAP's TM model
A JFLAP TM is 6-tuple M = (Q,Σ,Γ,δ,s,W) where Of course the important feature of the model is its 2-way infinite rather than 1-way infinite tape.

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:

Now, one problem is this: When the tape head is pointing to a cell on the tape, we have no way of knowing whether it's supposed to be referring to the upper symbol in that cell or the lower symbol. We'll have to use states to keep track of whether we're looking at the "right half" of our 2-way tape or the "left half". So each state will have a +1 or -1 tag, indicating that we're currently "in" the right half or left half, respectively, of the 2-way tape. This is handy not just for figuring out which symbol you're reading, but also because an L-move in the left half of the 2-way tape corresponds to an R-move on our 1-way tape, and an R-move in the left half of the 2-way tape corresponds to an L-move on 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)
Output: TM M' = (Q x {+1,-1}, Σ∪{$}, Σ∪{$}∪(Σ∪{  })2, δ',(s,+1)), where

δ((q,d),x) = {
(h,x,S) if q ∈ W
((q,-d),$,R) if x = $
((q,d),(x,  ),S) if x ∈ Σ ∪ {  }
((q',d),(x'1,x2),M) if d = +1, where x = (x1,x2) and δ(q,x1) = (q',x'1,M)
((q',d),(x1,x'2),M') if d = +1, where x = (x1,x2), δ(q,x2) = (q',x'2,M), and M' = S if M=S, R if M=L, L if M=R.
In class we'll go over this algorithm in detail, including walking it through for the following input JFLAP TM:
This machine swaps all the a's and b's in a string, using the 2-way nature of the tape to move the tape head back to the beginning of the string. This isn't interesting in terms of a language decided or semi-decided, but shows how the 1-way tape simulates the 2-way tape, which is the important point here.

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.


Christopher W Brown
Last modified: Mon Nov 24 19:52:46 EST 2003