1/1 0/0

Start

0/X-

X/ X

<§)

Start

-45)

Figure 8.14; The subroutine Copy

0/B-

0/0 /:г\ 1/1

s/B-

0/B-

Figure 8.15: The complete multiplication program uses the subroutine Copy

* Exercise 8.3.3: Design a subroutine to move a TM head from its current position to the right, skipping over all Os, until reaching a 1 or a blank. If the current position does not hold 0, then the TM should halt. You may assume that there are no tape symbols other than 0, 1, and В (blank). Then, use this subroutine to design a TM that accepts all strings of Os and Is that do not have two Is in a row.

8.4 Extensions to the Basic Turing Machine

In this section we shall see certain computer models that are related to Turing machines and have the same language-recognizing power as the basic model of a TM with which we have been working. One of these, the multitape Turing machine, is important because it is much easier to see how a multitape TM can simulate real computers (or other kinds of Turing machines), compared with the single-tape model we have been studying. Yet the extra tapes add no power to the model, as far as the ability to accept languages is concerned.

We then consider the nondeterministic Turing machine, an extension of the basic model that is allowed to make any of a finite set of choices of move in a given situation. This extension also makes programming Turing machine easier in some circumstances, but adds no language-defining power to the basic model.

8.4.1 Multitape Turing Machines

A multitape TM is as suggested by Fig, 8,16, The device has a finite control (state), and some finite number of tapes. Each tape is divided into cells, and each cell can hold any symbol of the finite tape alphabet. As in the single-tape TM, the set of tape symbols includes a blank, and has a subset called the input symbols, of which the blank is not a member. The set of states includes an initial state and some accepting states. Initially:

1. The input, a finite sequence of input symbols, is placed on the first tape.

2. All other cells of all the tapes hold the blank.

3. The finite control is in the initial state.

4. The head of the first tape is at the left end of the input,

5. AU other tape heads are at some arbitrary cell. Since tapes other than the first tape are completely blank, it does not matter where the head is placed initially; all cells of these tapes look the same.

A move of the multitape TM depends on the state and the symbol scanned by each of the tape heads. In one move, the multitape TM does the following:

Figure 8.16: A multitape Turing machine

1. The control enters a new state, which could be the same as the previous state.

2. On each tape, a new tape symbol is written on the cell scanned. Any of these symbols may be the same as the symbol previously there.

3. Each of the tape heads makes a move, which can be either left, right, or stationary. The heads move independently, so different heads may move in different directions, and some may not move at all.

We shall not give the formal notation of transition rules, whose form is a straightforward generalization of the notation for the one-tape TM, except that directions are now indicated by a choice of L, R or S. For the one-tape machine, we did not allow the head to remain stationary, so the S option was not present. You should be able to imagine an appropriate notation for instantaneous descriptions of the corrfiguration of a multitape TM; we shall not give this notation formally. Multitape Turing machines, like one-tape TMs, accept by entering an accepting state.

8.4.2 Equivalence of One-Tape and Multitape TMs

Recall that the recursively enumerable languages are defined to be those accepted by a one-tape TM. Surely, multitape TMs accept all the recursively enumerable languages, since a one-tape TM is a multitape TM. However, are there languages that are not recursively enumerable, yet are accepted by multitape TMs? The answer is no, and we prove this fact by showing how to simulate a multitape TM by a one-tape TM.