holds the data in cells of the Turing-machine tape that are located significantly to the left of the tape head, and the other stack holds data significantly to the right of the tape head. The further down the stacks, the further away from the tape head the data is.

Tape to leffof the head

Tape to right of the head

Figure 8.21: Simulating a Turing machine with a common computer

If the tape head of the TM moves sufficiently far to the left that it readies cells that are not represented by the disk currently mounted in the computer, then it prints a message swap left. The currently mounted disk is removed by a human operator and placed on the top of the right stack. The disk on top of the left stack is mounted in the computer, and computation resumes.

Similarly, if the TMs tape head reaches cells so far to the right that these cells are not represented by the mounted disk, then a swap right message is printed. The human operator moves the currently mounted disk to the top of the left stack, and mounts the disk on top of the right stack in the computer. If either stack is empty when the computer asks that a disk firom that stack be mounted, then the TM has entered an all-blank region of the tape. In that case, the human operator must go to the store and buy a fresh disk to mount.

8.6.2 Simulating a Computer by a Turing Machine

We also need to consider the opposite comparison: are there things a common computer can do that a Turing machine cannot. An important subordinate question is whether the computer can do certain things much faster than a Turing machine. In this section, we argue that a TM can simulate a computer, and in Section 8.6.3 we argue that the simulation can be done sufficiently fast that only a polynomial separates the running times of the computer and TM

The Problem of Very Large Tape Alphabets

The argument of Section 8.6.1 becomes questionable if the number of tape symbols is so large that the code for one tape symbol doesnt fit on a disk. There would have to be very many tape symbols indeed, since a 30 gigabji;e disk, for instance, can represent any of 2*° symbols. Likewise, the number of states could be so large that we could not represent the state using the entire disk.

One resolution of this problem begins by limiting the number of tape symbols a TM uses. We can always encode an arbitrary tape alphabet in binary. Thus, any TM M can be simulated by another TM M that uses only tape symbols 0, 1, and B. However, M needs many states, since to simulate a move of M, the TM M must scan its tape and remember, in its finite control, all the bits that tell it what symbol M is scanning. In this manner, we are left with very large state sets, and the PC that simulates M may have to mount and dismount several disks when deciding what the state of M is and what the next move of M should be. No one ever thinks about computers performing tasks of this nature, so the typical operating system has no support for a program of this type. However, if we wished, we could program the raw computer and give it this capability.

Fortunately, the question of how to simulate a TM with a huge number of states or tape symbols can be finessed. We shall see in Section 9.2.3 that one can design a TM that is in effect a stored program TM. This TM, called universal, takes the transition function of any TM, encoded in binary on its tape, and simulates that TM. The universal TM has quite reasonable numbers of states and tape symbols. By simulating the universal TM, a common computer can be programmed to accept any recursively enumerable language that we wish, without having to resort to simulation of numbers of states that stress the limits of what can be stored on a disk.

on a given problem. Again, let us remind the reader that there are important reasons to tlihik of all running times that he within a polynomial of one another to be similar, while exponential differences In running time are too much. We take up the theory of polynomial versus exponential ruiming times in Chapter 10,

To begin our study of how a TM sinmlates a computer, let us give a realistic but informal model of how a typical computer operates.

a) First, we shall suppose that the storage of a computer consists of an indefinitely long sequence of words, each with an address. In a real computer, words might be 32 or 64 bits long, but we shall not put a limit on the length of a given word. .Addresses will be assumed to be integers 0, 1,

2, and so on. In a real computer, individual bytes would be numbered by consecutive integers, so words would have addresses that are multiples of 4 or 8, but this difference is unimportant. Also, in a real computer, there would be a limit on the number of words in memory, but since we want to account for the content of an arbitrary number of disks or other storage devices, we shall assume there is no limit to the number of words.

b) We assume that the program of the computer is stored in some of the words of memory. These words each represent a simple instruction, as in the machine or assembly language of a typical computer. Examples are instructions that move data from one word to another or that add one word to another. We assume that indirect addressing is permitted, so one instruction could refer to another word and use the contents of that word as the address of the word to which the operation is applied. This capability, found in all modern computers, is needed to perform array accesses, to follow links in a list, or to do pointer operations in general.

c) \e assume that each instruction involves a limited (finite) number of words, and that each instruction changes the value of at most one word.

d) A typical computer has registers, which are memory words with especially fast access. Often, operations such as addition are restricted to occur in registers. We shall not make any such restrictions, but will allow any operation to be performed on any word. The relative speed of operations on diflferent words will not be taken into account, nor need it be if we are only comparing the language-recognizing abihties of computers and Tiuing machines. Even if we are interested In running time to within a polynomial, the relative speeds of different word accesses is unimportant, since those differences are only a constant factor.

Figure 8.22 suggests how the Turing machine would be designed to simulate a computer. This TM uses several tapes, but it could be converted to a one-tape TM using the construction of Section 8.4.1. The first tape represents the entire memory of the computer. We have used a code in which addresses of memory words, hi numerical order, alternate with the contents of those memory words. Both addresses and contents are written in binary. The marker symbols * and # are used to make it easy to find the ends of addresses and contents, and to tell whether a binary string is an address or contents. Another marker, $, indicates the beghining of the sequence of addresses and contents.

The second tape is the instruction counter. This tape holds one integer in binary, which represents one of the memory locations on tape 1. The value stored in this location will be interpreted as the next computer instruction to be executed.

The third tape holds a memory address or the contents of that address after the address has been located on tape 1. To execute an instruction, the TM must find the contents of one or more memory addresses that hold data