Multitape Turing machines
| See the Grafstate guide to creating a Turing machine for the general syntax of creating a single-tape Turing machine. |
Syntax
To create a Turing machine with 2 or more tapes, the Grafstate code must contain the line
tapes=n ,where n is the number of tapes. For example, the code for a 2-tape Turing machine must contain the line
tapes=2 .If n tapes are requested, then each transition must define the tape instructions for all n tapes. Within a transition, tape instructions are separated by a semicolon (
; ). For example, the following Grafstate code defines a transition from state q1 to state q2 that read a, writes X, and moves right on tape1 and reads ␣, writes b, and stays put on tape 2∶q1->q2:a->X,R; \_->b,S Examples
 | An example of a multitape Turing machine is an enumerating Turing machine whose task is to list all strings in a language. |
| Let Σ={a,b}. The following Turing machine Mcopy copies the contents of tape 1 to tape 2 and marks the beginning of tape 2 for the purpose of rewinding later∶ |
 |
The Grafstate code for Mcopy is below∶
Code |
|---|
:+ tm Mcopy Q={q1,q2} S={a,b} T={a,b,\_} q0=q1 tapes=2 q1->q2:{a,b},S; \_,R /* mark the start of t2 q2:a,R; \_->a,R /* copy symbol a from t1 to t2 q2:b,R; \_->b,R /* copy symbol b from t1 to t2 done. |
We can test Mcopy on the input string abab. Follow the computation history to watch the input string get copied to tape 2.
 | The simulation indicates that the input string is REJECTED. This Turing machine is not attempting to solve a decision problem (deciding whether a string is in a language). This Turing machine is computing a function (namely the copy function). |
Simulation | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Input aabbab | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Result REJECTED | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
 Explanation The following computation history shows the steps of the computation∶ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Turing machine∶ Mcopy
| The Turing machine mab2 decides the language L={anbn∣n≥0}. In other words, Mab2 accepts each string in L and rejects each string in L . |
| Mab2 using the Mcopy routine to copy the a's from tape 1 to tape 2. Then, Mab2 matches the a's that have been copied to tape 2 with the b's that are on tape 1. |
 |
The Grafstate code for Mab2 is below∶
Code |
|---|
:+ tm Mab2 Q={q1,q2,qa,qr,q3,q4} S={a,b} T={a,b,\_} q0=q1 tapes=2 q1->qa:\_,S; \_,S q1->q2:a,S; \_,R /* mark the start of t2 so we can rewind it q1->qr:b,S; \_,S /* starts with b q2:a,R; \_->a,R /* copy a's from t1 to t2 q2->q3:b,S; \_,L /* prepare to rewind t2 q3:b,S; a,L /* rewind t2 q3->q4:b,S; \_,R /* align t2's tape head to be on first a q4:b,R; a,R /* match b's on t1 with a's on t2 q4->qa:\_,S; \_,S /* a's and b's finished at the same time q4->qr:\_,S; a,S /* more a's than b's q4->qr:a,S; a,S /* a after b q4->qr:a,S; \_,S /* a after b q4->qr:b,S; \_,S /* more b's than a's done. |
Let's test Mab2 with a string that is accepted and also with some strings that are rejected.
Simulation | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Input aaabbb | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Result ACCEPTED | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Explanation The following computation history shows the steps of the computation∶ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Turing machine∶ Mab2
Simulation | |||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Input baabb | |||||||||||||||||||||||||||
Result REJECTED | |||||||||||||||||||||||||||
| Explanation The following computation history shows the steps of the computation∶ | |||||||||||||||||||||||||||
|
Turing machine∶ Mab2
Simulation | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Input aabbab | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Result REJECTED | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Explanation The following computation history shows the steps of the computation∶ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Turing machine∶ Mab2
Simulation | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Input aaabb | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Result REJECTED | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Explanation The following computation history shows the steps of the computation∶ | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Turing machine∶ Mab2
Simulation | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Input aabbb | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
Result REJECTED | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
| Explanation The following computation history shows the steps of the computation∶ | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Turing machine∶ Mab2