δ:(Q - W) x (Γ ∪ ) &rarr Q x (Γ ∪ ) x {L,R,S}
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
In class we'll go over this algorithm in detail, including walking it through for the following input JFLAP TM:
δ((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.
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.