Multi-Tape Turing Machines
Introduction
How
to Create an Multi-Tape Turing Machine
It is recommended, if you haven't already, to read the tutorial about creating a one-tape Turing machine. It covers much of the basics about Turing machines and how their displays are different from other automata.
Multi-tape Turing machines as implemented in JFLAP are Turing machines ranging from 2 to 5 tapes. Values on both tapes must match for the automaton to proceed, but other than that, there isn't much difference between the two modes. Multi-tape Turing machines allow for a number of languages to be implemented with greater ease. One such example is the language demonstrated in the one tape tutorial, L = {anbncn}. We will build this example with 3 tapes and test it.
To start a new multi-tape Turing machine, start JFLAP and click the Multi-Tape Turing Machine option from the menu, as shown below:
A pop-up window will come up asking how many tapes to implement, 2 is the default, but from the menu given, we can choose a number in the range of 2 to 5. While we could definitely do this problem with 1 or 2 tapes, choose 3 tapes, because it allows for us to implement an automaton that is very easy to understand visually. After choosing 3 tapes, one will see a screen that is identical to that for one-tape Turing machines. However, there are a few different features that we will soon encounter.
On the blank screen, add 5 states to the screen, so that the screen resembles the one below.
Now its time to add the transitions. Attempt to add a transition between the states q0 and q1. You'll notice that, instead of just one tape that you have to define values for, you must define values for three tapes. Go ahead and enter in (b; b, R) for the first tape, (□; □, S) for the second, and □; b, R) for the third. This transition will check to see if there is a 'b' under the head of the first tape, and if there are blanks under the heads of the other two tapes. If this is true, then it will add a 'b' to the third tape, move the heads of the first and third tapes to the right, and not move the head of the second tape.
|
Three tapes |
The first transition |
|---|---|
|
. |
|
Let's finish up the transitions. Add the transitions in your screen below to your Turing machine. If you would rather not add every transition directly and would prefer to load the file of the screen below, it is available at turingAnBnCnMulti.jff.
Now, let's try out our new multi-tape Turing machine. We could do a “Fast Run”, but since we haven't done a “Step” option yet for Turing machines, let's try that. It is very similar to the “Step with Closure” option for Finite Automata. First, click on “Input” and then “Step”, and when it prompts for the values for the three tapes, enter the string “aabbcc” on the first tape (representing a2b2c2) and nothing on the next two tapes. We now see the screen below...
The box in the lower left is different from that which appears for the Finite Automata's “Step with Closure” option. In this example, each tape is present, and a red highlighted area represents the current position of the tape's head. A similar screen will appear for any number of Turing machine tapes, with one tape for single-tape machines and five for five tape machines (all viewable with the scroll bar at the lower right). At present, the third tape is partially obscured, so we should scroll down until it is more visible or resize the window. Which ever option you choose, make sure you can see all three tapes.
As we press step repeatedly, the following are the steps through which the simulation runs:
|
Start |
Step 1 |
Step 2 |
Step 3 |
Step 4 |
|---|---|---|---|---|
|
|
|
|
|
|
|
Step 5 |
Step 6 |
Step 7 |
Success! |
|---|---|---|---|
|
|
|
|
|
We now see firsthand how the algorithm works and how it is implemented in action. First, the first tape reads all the 'a's and copies them onto the second tape. Then, it reads all the 'b's and copies them onto the third tape. Finally, all three tapes check to see whether the number of 'a's, 'b's, and 'c's are equal, the first tape checking the 'c's, the second the 'a's, and the third the 'b's. We might wonder where state “q4” comes into this, but transitions leading to and from it simply check where n = 0, which cannot be served by the other transitions.
This concludes our brief tutorial on building multi-tape Turing machines. Thanks for reading!