Simulation

Turing machines are more powerful than other machines we have studied, and are capable of performing a wide variety of tasks. One of the more useful tricks a Turing machine program is simulating the operation of another machine.

In the following example I am going to demonstrate how to construct a Turing machine program that can faithfully replicate the behavior of a PDA. The techniques I am going use in this example are fairly generic, and can be applied to other situations where we need to build a Turing machine to simulate the behavior of the another machine.

To simulate both the input and the stack of the PDA the Turing machine is going to use a specially configured tape. The tape will record both the current state of the input and the current state of the stack.

Suppose we wanted to feed a particular input string s to the PDA. In the Turing machine simulation we would start with the input string s on the tape. As the machine runs, the Turing machine will want to keep track of the PDA's progress in reading through the input. A natural way to do this would be to use a marking system. At each step along the way, the Turing machine would place a mark on the next character to be read by the PDA. To record the state of the stack, the Turing machine would place a special separator character, #, after the input, and then place the contents of the stack after the #. The character that appears right after the # represents the bottom of the stack, while the last character on the tape represents the top of the stack.

The picture below shows a typical configuration of the Turing machine's tape.

This corresponds to the situation where the PDA that the Turing machine is simulating is about to read the third character of its input (note the dot over the 0 - this is how the machine marks the current location in the input), while the stack currently contains the symbols 1 and 1.

Next, we work on building the Turing machine's control. Here are some guidelines for how we will do this.

1. Each state in the PDA will have a corresponding state in the Turing machine. The Turing machine will add additional states on top of those to run the simulation.
2. Before the state that corresponds to the start state of the PDA we will add additional states that do some initialization, including marking the first character of the input and putting the # character on the tape.
3. For each transition in the PDA we will add transitions and additional states to the Turing machine that connect the two states that the PDA transition connects.
4. We will add extra states and transitions that allow us to faithfully simulate the behavior of final states in the PDA.

Here is an example to demonstrate how we will map a PDA transition to a fragment of the Turing machine.

Here is a typical transition in the PDA

The simulating Turing machine would have control states labeled a and b that correspond to these two PDA states. Connecting states a to b the Turing machine would have a fragment that replicates the behavior of the original transition. The Turing machine will make it possible to get from a to b in the simulation if and only if the current PDA configuration makes it possible to take the corresponding transition in the PDA.

Here now is the Turing machine fragment corresponding to this PDA transition.

Here is what that fragment does.

1. The fragment assumes that when the Turing machine is in state a the tape head will be over the dotted character on the tape, ready to read the next character in the simulated input.
2. The fragment starts by confirming that the symbol under that tape head is a dotted 1. The original PDA would only be able to get from state a to state b if the next character in the input was a 1.
3. The fragment then moves right to the cell corresponding to the top of the stack and confirms that there is a 0 there.
1. If there is not a 0 at the top of the stack, the fragment rewinds back to the dotted 1 and returns to state a: the transition attempt has failed.
4. If there is a 0 at the top of the stack, the fragment removes it and rewinds back to the dotted 1.
5. The fragment replaces the dotted 1 with a normal 1, dots the character to the right, and positions the tape head over the newly dotted character. If the next character after the original dotted 1 is the #, the fragment leaves that character unchanged and ends with the tape head over the #.

A more complete simulation example

A very common trick we perform with a Turing machine is to show how it can simulate other machines. This also works in reverse: in some cases we may want to show that some machine can simulate a Turing machine.

In this next example we are going to show that a machine with two stacks can simulate a Turing machine.

The first step in showing how this simulation works is explaining how we can use two stacks to simulate the state of the tape in a Turing machine. The picture below shows how this works.

The stack on the left holds all of the symbols that appear on the tape either under the tape head or to the left of the tape head. The very first symbol on the tape appears near the bottom of the stack, and the symbol under the tape head appears at the top of the left stack. In addition to these symbols, the left stack also contains a marker symbol, $, at the bottom. This marks the left end of the tape. The stack on the right holds the tape symbols that appear to the right of the tape head. The symbol immediately to the right of the tape head appears at the top of the right stack, and the first blank on the tape appears at the bottom of the second tape.

The first thing to take care of is handling the input. A Turing machine is expected to start with its input on the tape with the tape head over the first symbol in the input, while a PDA reads its input. We can handle this by inserting a subfragment before the start state of the Turing machine that pushes a $ onto the first stack, pushes a blank onto the second stack, and then reads the input and pushes each symbol read onto the first stack. This then has to be followed up by a second subfragment that shuttles symbols from the left stack to the right until we see the $ on the left. We then move one symbol from the top of the second stack to the top of the first stack. We also need this fragment to do the right thing in the special case where the input is empty.

This pre-start fragment is the only part of the machine that will read the input. All of the instructions for the two stack machine shown after this point will simply ignore the input.

Next, we show how to simulate a typical Turing machine instruction. A Turing machine instruction has three parts: reading a symbol, writing a symbol, and moving the tape head. To check that a particular symbol appears under the tape head, the simulation simply has to try to pop that symbol from the top of the first stack. If that symbol does not appear at the top of the first stack the pop attempt fails and we do nothing. This matches what the Turing machine instruction would do in the case where the desired symbol does not appear under the tape head. To write a symbol, we simply push that symbol on the top of the first stack. To simulate a move to the left, we pop a symbol from the first stack and push that same symbol onto the second stack. To simulate a move to the right, we pop a symbol from the second stack and push it onto the first stack.

Finally, we have make sure that we are handling special cases properly. There are two special cases to consider.

The first special case is attempting to move the tape head to the left from the left end of the tape. To handle this, we add an extra transition to the end of each fragment that simulates a Turing machine instruction. This fragment checks to see whether or not the symbol at the top of the first stack is the $ marker. The only way to reach this state in the simulation is by having done a left move off the left end of the stack, so we simply have to undo that previous left move. We do this by popping the symbol off the top of the second stack and pushing it back on top of the first stack. This effectively undoes the previous left move.

The second special case is moving right onto a blank. To handle this, we add some additional logic to the part of the fragment that handles moves to the right. As we pop the symbol off the second stack, we check to see if the symbol we just popped is a blank. If it is, we insert an instruction that pushes another blank onto the top of the second stack. After that we push the original blank onto the top of the first stack.

Here now are a couple of illustrations of complete simulations of instructions. The first example is an instruction that features a left move, including the check for trying to move left past the left end of the tape. If the original Turing machine instruction looks like

the simulating fragment would look like

The second example is an instruction with a right move, including the check for moving right onto a blank.

The simulating fragment is

There is only final special case to consider, the case of an empty input. Most Turing machines have a special case instruction to handle this case, transitioning immediately to an accepting state or rejecting state. I leave it as an exercise for you to determine whether our simulation needs any further special handling for this case, or whether the existing measures are sufficient to handle this kind of case automatically.

Multitape Turing machines

In section 3.2 of the text the author discusses a couple of important variants of the basic Turing machine. The first of these is the multitape Turing machine, which has several tapes, each with its own independent tape head. A typical transition in a multitape machine specifies what symbols should appear under each of the tape heads, what symbols to write in the current cells, and how to move each of the tape heads. In addition to the usual L and R moves, a multitape Turing machine also allows the 'stay put' command, S.

Here is a diagram showing a typical multitape machine configuration along with a typical transition.

In some cases we may want to do something with a subset of the tapes while leaving the remaining tapes unchanged. We can make it easier to specify these kinds of transitions by introducing a wild-card character, *, that matches any symbol on a tape and using the transition *→S for any tape that we want to leave unchanged.

In much the same way that we could use a single tape Turing machine to simulate a PDA, we can use a single tape Turing machine to simulate a multitape Turing machine. We simply concatenate the contents of the various tapes onto a single tape with # characters to separate the contents of the individual tapes, and use a marking system to indicate where the tape heads are in the various tapes. That looks something like this:

Just as we did in the PDA example, we would make a new control with the same states as the original multi-tape machine. We would replace all of the transitions in the original machine with fragments that do the following things:

1. Scan the tape from left to right to confirm that the correct characters are dotted on each subsegment.
2. Scan the tape a second time making replacements and moving the individual tape heads.
3. Rewind back to the start of the single tape.

One additional complication we have to contend with in this case is the fact that individual segments can grow as we write more characters to a particular tape. In cases like this, the fragments will also have to be equipped to move groups of characters to the right to create space for the characters we want to write. This is a pain, but can be done.

Going forward, we will feel free to use multiple tapes in a solution, since we now know that any multitape Turing machine can be simulated by a single tape machine.

An example

Allowing multiple tapes considerably expands the range and the power of Turing machine programs. To demonstrate how having multiple tapes can make our life easier, here is a description of a two tape Turing machine that accepts the language from exercise 2.48b.

L = {xyz | |x| = |z|, |y| ≤ |x|, and y contains at least two 1s }

1. Start with the input on tape 1, a blank tape 2, and the tape heads of both tapes at the start of their tapes.
2. Scan tape one to confirm that the input contains at least six symbols. If there are fewer than six symbols, stop and reject. Otherwise, rewind the tape head on tape one back to the first cell.
3. Scan tape one from left to right. Starting with the first character, write a 1 onto the second tape and move the tape head on the first tape ahead three cells. Repeat this until a space appears under the first tape head. Rewind the tapes heads on both tapes to the start.



4. Repeat the following until a space appears under the second tape head: replace the current character on tape one with an x and move the first tape head to the right, and move the second tape head to the right.



5. Move the tape head on the first tape to the last character on the tape. Rewind the tape head on the second tape to the start of the tape.



6. Repeat the following until a space appears under the second tape head: replace the current character on tape one with an x and move the first tape head to the left, and move the second tape head to the right.



7. Move the tape head on the first tape left and make note of any 1s you encounter. As soon as you see two ones, stop and accept. If you make it back to the first group of xs without having seen two 1s, stop and reject.

Other variants

Read section 3.2 for a discussion of two other variants: the nondeterministic Turing machine, or NTM, and the enumerator. Both of these can also be simulated by a deterministic, single tape Turing machine.

The Church-Turing thesis

Once we have the ability to set up multitape Turing machines we can design a Turing machine to do anything we can imagine. This extends up to and including building a Turing machine that can replicate the behavior of a Von Neumann computer. A Von Neumann computer consists of a memory, and a CPU with a set of registers. A Turing machine that simulates the computer would have a tape to represent the computer's memory, and a separate tape to represent the contents of each register, including a program counter and address registers. With enough work we can get the Turing machine to emulate the Von Neumann machine's fetch-interpret-evaluate cycle in which the Von Neumann machine fetches the next instruction in the program, interprets the machine language instruction, and carries out the instruction by manipulating the contents of the registers. This includes being able to carry out arithmetic operations on registers.

The Church-Turing thesis formalizes our intuition that Turing machines are as powerful as conventional computers by saying that anything that can be done by a conventional computer program can also be done by a sufficiently powerful Turing machine program.

The universal Turing machine

A conventional computer program can simulate the operation of a Turing machine. In particular, it is not too hard to imagine building a Turing machine simulation program that can load a description of a Turing machine along with an input for the Turing machine and then simulate the behavior of the Turing machine as it processes that input.

We have just seen that Turing machines can simulate anything, so we can extend this to imagining a Turing machine that simulates the computer program that simulates any Turing machine running on any input. The result of this is a particulary famous Turing the machine, called the universal Turing machine. This is a Turing machine that can start with the description of any other Turing machine along with an input string on its tape and then simulate the behavior of the other machine running on that input.