ways, for example, in the two-dimensional fashion indicated in Figure 10.12.
The two-track tape of the simulating machine will use one track to store cell
contents and the other one to keep the associated address. In the scheme of
Figure 10.12, the configuration in which cell (1, 2) contains a and cell (10, – 3)
contains b is shown in Figure 10.13. Note one complication: The cell address
can involve arbitrarily large integers, so the address track cannot use a fixed-size
field to store addresses. Instead, we must use a variable field-size arrangement,
using some special symbols to delimit the fields, as shown in the picture.
Let us assume that, at the start of the simulation of each move, the read-write
head of the two-dimensional machine M and the read-write head of the
simulating machine are always on corresponding cells. To simulate a move,
the simulating machine first computes the address of the cell to which M is to
move. Using the two-dimensional address scheme, this is a simple computation.
Once the address is computed, finds the cell with this address on track 2 and
then changes the cell contents to account for the move of M. Again, given M,
there is a straightforward construction for
Figure10.13
EXERCISES
The purpose of much of our discussion of Turing machines is to lend credence to
Turing's thesis by showing how seemingly more complex situations can be
simulated on a standard Turing machine. Unfortunately, detailed simulations are
very tedious and conceptually uninteresting. In the exercises below, describe the
simulations in just enough depth to show that the details can be worked out.
1. Define what one might call a multitape offline Turing machine and describe
how it can be simulated by a standard Turing machine.
2. A multihead Turing machine can be visualized as a Turing machine with a
single tape and a single control unit but with multiple, independent readwrite heads. Give a formal definition of a multihead Turing machine, and
The two-track tape of the simulating machine will use one track to store cell
contents and the other one to keep the associated address. In the scheme of
Figure 10.12, the configuration in which cell (1, 2) contains a and cell (10, – 3)
contains b is shown in Figure 10.13. Note one complication: The cell address
can involve arbitrarily large integers, so the address track cannot use a fixed-size
field to store addresses. Instead, we must use a variable field-size arrangement,
using some special symbols to delimit the fields, as shown in the picture.
Let us assume that, at the start of the simulation of each move, the read-write
head of the two-dimensional machine M and the read-write head of the
simulating machine are always on corresponding cells. To simulate a move,
the simulating machine first computes the address of the cell to which M is to
move. Using the two-dimensional address scheme, this is a simple computation.
Once the address is computed, finds the cell with this address on track 2 and
then changes the cell contents to account for the move of M. Again, given M,
there is a straightforward construction for
Figure10.13
EXERCISES
The purpose of much of our discussion of Turing machines is to lend credence to
Turing's thesis by showing how seemingly more complex situations can be
simulated on a standard Turing machine. Unfortunately, detailed simulations are
very tedious and conceptually uninteresting. In the exercises below, describe the
simulations in just enough depth to show that the details can be worked out.
1. Define what one might call a multitape offline Turing machine and describe
how it can be simulated by a standard Turing machine.
2. A multihead Turing machine can be visualized as a Turing machine with a
single tape and a single control unit but with multiple, independent readwrite heads. Give a formal definition of a multihead Turing machine, and