The Turing machine tape

A Turing machine has a semi-infinite tape. Each cell in the tape contains a single symbol from the tape alphabet. Empty cells contain space characters.

The Turing machine has a tape head that can view one cell at a time.

The Turing machine control

In addition to its tape, a Turing machine has a control made up of states and transitions.

Each transition has three parts: a read, a write, and a move. The read specifies what the tape head should look for in the current cell. If the current cell contains the character listed, the machine can make the transition. When the machine makes the transition it replaces the symbol read with the new symbol, and then moves the tape head one space in the direction indicated.

A transition can leave a cell unaltered by simply reading and writing the same symbol.

This type of transition occurs quite often, so the author uses a more convenient alternative notation for transitions that leave a cell unchanged:

Marking characters

A widely used strategy in Turing machine programs is to replace symbols on the tape with alternative symbols. This strategy is used to mark special locations on the tape. The most common example of this is marking the start of the tape.

This facilitates rewinding the tape head to the start of the tape. The machine simply moves left past regular symbols until it encounters one of the special marking symbols:

Attempting to move the tape head left past the start of the tape results in the tape head staying where it is. Thus state 4 will have the tape head positioned over the start of the tape.

A first example

For our first example we will consider a simple language whose strings use the input alphabet Σ = {0,1}. Our first example language is

L₁ = { w | w has even length }

Here is the first draft for the control for the machine that recognizes this language.

Clearly, here state 1 is the state the machine will be in after having seen an even number of characters and state 2 is the state the machine will be in after having seen an odd number of characters.

The machine is not yet complete, because we haven't added logic to handle the case where the tape head has run past the end of the input, and we also don't have a way for the machine to accept its input.

Turing machines have final states, just as DFAs and PDAs do. Unlike those earlier machines, Turing machines have both accepting final states and rejecting final states. When a Turing machine enters a final state it will stop. If the final state it entered is an accepting state, the machine will accept its original input. If the final state is a rejecting state, the machine rejects its input.

Using one machine as a subroutine in another

Once we have discovered how to solve a problem via a Turing machine program, we will often find that we can reuse that Turing machine to do the same task in the context of a larger Turing machine program.

Here is a typical example. Suppose we wanted to make a Turing machine to recognize the language

L₂ = { ww | w ∈ Σ^* }

A useful first step is to confirm that the length of the input string is even and has length at least two. If we determine it is odd we can immediately stop and rejcct. Here is a Turing machine that can scan its input to determine whether or not the input is of even length and reject any odd length input. To facilitate rewinding to the start in later stages of the program, we use the common strategy of replacing the first character in the input with a marking character.

We can now use this initial machine as a first stage in a larger machine. Instead of ending with the accept state, the machine goes on to the next phase. After completing the first stage, we know that the tape head is over the rightmost character in the input.

In the next phase we make a series of passes across the tape. In each pass we replace a single character on the left side and a single character on the right side. On the left we replaces 0s with cs, 1s with ds. On the right we replace 0s with es and 1s with fs. After each left to right pass we rewind back until we encounter an a, b, c, or d. When we reach the point where the es and fs meet up with the cs and ds we know that we have replaced all of the 0s and 1s in the original, and can then rewind to the start. Here is what the second stage in the machine looks like.

Here I have introduced some condensed notation. The notation (0|1)→(e|f),L means "If you see a 0 replace it with an e and move left. If you see a 1 replace it with an f and move left."

After the second stage all the 0s in the left half of the input have been replaced with cs, and 1s have been replaced with ds. On the right all 0s have been replaced with es and all 1s have been replaced with fs.

The final stage matches characters on the left with characters on the right. Once again, we do this as a series of passes. On each pass we look for a c or d on the left, and move right until will find a matching e or f. Each time we find a matching pair we replace both matching characters with an x to indicate that we done with those characters.

Tracing a run

Turing machines are sufficiently complex that there are ample opportunities make mistakes when setting up a machine. To increase our confidence that the machine we have built is correct, we should do some runs through the machine. Below you will find a complete example of a run.

In this example we will run the machine on the input s = 110110. This is an input the machine should accept.

Here is the start configuration of the machine. We start with the input on the tape, the tape head over the first symbol in the input, and the control at state 1. (This sequence of steps is best viewed as a slide show. To start the slide show select Start Slide Show from the Slides menu. To advance from one slide to the next, press the right arrow key. To exit the slide show press the escape key.)

High level descriptions

If the exercise of constructing the Turing machine for the example above taught you anything, it may be that building one of these machines is a tedious and error prone process. The one bit of good news from the last example is that almost all Turing machines can be decomposed into distinct stages. If we have a clear idea of what each stage has to accomplish, this makes our work easier.

An alternative to building the full machine in all its detail is to instead identify the stages we need and write out a careful description in words for what each stage is meant to do. This can act as a road map for building the stages.

For example, the machine above can be described in this way:

On input x:

1. Mark the start of the tape by replacing 0 with a and 1 with b.
2. Make an initial scan across the tape, moving past two characters at a time.
3. Rewind to the start of the tape.
4. Bounce back and forth between the front of the tape and the back, replacing 0s in the first half with cs and 1s with ds. Replace 0s in the second half with es and 1s with fs.
5. Rewind to the start of the tape, and replace the initial a with a c and the initial b with a d.
6. Make a series of passes across the tape. On each pass locate the first c or d that appears on the tape, then scan right looking for the e or f that matches that character. As you match these characters, mark them out by replacing them with an x.
7. As soon as no characters remaing to be matched, stop and accept.

In this initial description I have only written down what happens when everything goes right. This is the typical sequence when we input an x that is in the language. To complete our description, we have to anticipate everything that can go wrong. A good way to handle these cases is by adding subpoints to our main points that describe what can go wrong at various stages. Here is the more complete description with the error cases added:

On input x:

1. Mark the start of the tape by replacing 0 with a and 1 with b.
1. If the tape is empty, stop and accept.
2. Make an initial scan across the tape, moving past two characters at a time.
1. If you encounter an odd number of characters, stop and reject.
3. Rewind to the start of the tape.
4. Bounce back and forth between the front of the tape and the back, replacing 0s in the first half with cs and 1s with ds. Replace 0s in the second half with es and 1s with fs.
5. Rewind to the start of the tape, and replace the initial a with a c and the initial b with a d.
6. Make a series of passes across the tape. On each pass locate the first c or d that appears on the tape, then scan right looking for the e or f that matches that character. As you match these characters, mark them out by replacing them with an x.
1. If you don't find a matching character on a given pass, stop and reject.
7. As soon as no characters remaing to be matched, stop and accept.

Going forward, we will very rarely be constructing full Turing machines. In almost every case we will settle for a high level description in words that breaks the machine into stages and describes carefully what each stage does. If the descriptions are clear enough and simple enough, we could always go back later and build the submachines for each of the stages if we had to.

A useful trick

In many of the machines we build we will need to do multiple passes across the tape. An annoying technical issue that comes up in this context is rewinding the tape head to the start of the tape. This is difficult to do, since it may be hard to tell that we have reached the left end of the tape. We can mark the first first symbol in the tape in some special way, but this often introduces additional complexity to the machine.

An alternative strategy is to start by running a subroutine that moves every character on the tape one space to the right and places a space at the start of the tape. After doing this, rewinding to the start of the tape is easy, since we just have to move left until we see the space.

Here is a fragment of a Turing machine that moves every symbol on the tape one space to the right and places a blank in the first cell. After moving everything, the fragment rewinds the tape head so it ends up over the first nonblank character in the tape.

The loop on state 4 demonstrates how to rewind to the start of the tape.