Before giving the proof that the Turing machine described above can simulate n steps of a computer in O(n) time, we need to confront the issue of multiplication as a computer instruction. The problem is that we have not put a limit on the number of bits that one computer word can hold. If, say, the computer were to start with a word holding integer 2, and were to multiply that word by itself for n consecutive steps, then the word would hold the number 2 . This number requires 2 -- 1 bits to represent, so the time the Turing machine takes to simulate these n instructions would be exponential in n, at least.

One approach is to insist that words retain a fixed maximum length, say 64 bits. Then, multiplications (or other operations) that produced a word too long would cause the computer to halt, and the Turing machine would not have to simulate it any further. We shall take a more liberal stance: the computer may use words that grow to any length, but one computer instruction can only produce a word that is one bit longer than the longer of its arguments.

Example 8,16: Under the above restriction, addition is allowed, since the result can only be one bit longer than the maximum length of the addends. Multiplication is not allowed, since two m-bit words can have a product of length 2m. However, we can simulate a multiplication of m-bit integers by a sequence of m additions, interspersed with shifts of the multiplicand one bit left (which is another operation that only increases the length of the word by 1). Thus, we can still multiply arbitrarily long words, but the time taken by the computer is proportional to the square of the length of the operands. □

Assuming one-bit maximum growth per computer instruction executed, we can prove our polynomial relationship between the two running times. The idea of the proof is to notice that after n instructions have been executed, the number of words mentioned on the memory tape of the TM is 0(n), and each computer word requires 0(n) Ttiring-machine cells to represent it. Thus, the tape is O(n) cells long, and the TM can locate the finite number of words needed by one computer instruction in O(n) time.

There is, however, one additional requirement that must be placed on the instructions. Even if the instruction does not produce a long word as a result, it could take a great deal of time to compute the result. We therefore make the additional assumption that the instruction itself, applied to words of length up to k, can be performed in Oik ] steps by a multitape Turing machine. Surely the typical computer operations, such as addition, shifting, and comparison of values, can be done in 0{k) steps of a multitape TM, so we are being overly liberal in what we allow a computer to do in one instruction.

Theorem 8.17: If a computer:

1. Has only instructions that increase the maximum word length by at most 1, and

8.7. SUMMARY OF CHAPTER 8 363

2. Has only instructions that a multitape TM can perform on words of length к in O(fc) steps or less,

then the Turing machine described in Section 8,6.2 can simulate n steps of the computer in O(n) of its own steps.

PROOF: Begin by noticing that the first (memory) tape of the TM in Fig. 8.22 starts with only the computers program. That program may be long, but it is fixed and of constant length, independent of n, the number of uistruction steps the computer executes. Thus, there is some constant с that is the largest of the computers words and addresses appearing ш the program. There is also a constant d that is the number of words occupied by the program.

Thus, after executing n steps, the computer cannot have created any words longer than c + n, and therefore, it cannot have created or used any addresses that are longer than c+n bits either. Each uistruction creates at most one new address that gets a value, so the total number of addresses after n instructions have been executed is at most d + n. Since each address-word combination requires at most 2{c + n) + 2 bits, including the address, the contents, and two marker symbols to separate them, the total number of TM tape cells occupied after n instructions have been simulated is at most 2{d + n){c + n + 1). As с and d are constants, this number of cefis is O(n).

We now know that each of the fixed number of lookups of addresses involved in one computer instruction can be done in O(n) time. Since words are 0{n) in length, our second assumption tells us that the instructions themselves can each be carried out by a TM in C(n) time. The only significant, remaining cost of an instruction is the time it takes the TM to create more space on its tape to hold a new or expanded word. However, shifting-over involves copying at most O(u) data from tape 1 to the scratch tape and back again. Thus, shifting-over also requires only O(n) time per computer instruction.

We conclude that the TM simulates one step of the computer in O(n) of its own steps. Thus, as we claimed in the theorem statement, n steps of the computer can be simulated in 0{n} steps of the Turing machine. □

As a final observation, we now see that cubing the number of steps lets a multitape TM simulate a computer. We also know from Section S.4.3 that a one-tape TM can simulate a multitape TM by squaring the number of steps, at most. Thus:

Theorem 8.18: A computer of the type described in Theorem 8.17 can be simulated for n steps by a one-tape Turing machine, using at most 0(n) steps of the Turing machine, □

8.7 Summary of Chapter 8

♦ The Turing Machine: The TM is an abstract computing machine with the power of both real computers and of other mathematical definitions

of what can be computed. The TM consists of a finite-state control and an infinite tape divided into cells. Each cell holds one of a finite number of tape symbols, and one cell is the current position of the tape head. The TM makes moves based on its current state and the tape symbol at the cell scanned by the tape head. In one move, it changes state, overwrites the scanned cell with some tape symbol, and moves the head one cell left or right.

f Acceptance by a Turing Machine: The TM starts with its input, a finite-length string of tape symbols, on its tape, and the rest of the tape containing the blank symbol on each cell. The blank is one of the tape symbols, and the input is chosen from a subset of the tape symbols, not including blank, called the input .symbols. The TM accepts its input if it ever enters an accepting state.

Recursively Enumerable Languages: The languages accepted by TMs are called recursively enumerable (RE) languages. Thus, the RE languages are those languages that can be recognized or accepted by any sort of computing device.

> Instantaneous Descriptions of a TM: We can describe the current configuration of a TM by a finite-length string that includes all the tape cells from the leftmost to the rightmost nonblank. The state and the position of the head are shown by placing the state within the sequence of tape symbols, just to the left of the cell scanned,

+ Storage in the Finite Control: Sometimes, it helps to design a TM for a particular language if we imagine that the state has two or more components. One component is the control component, and functions as a state normally does. The other components hold data that the TM needs to remember.

4- Multiple lYacks: It also helps frequently if we think of the tape symbols as vectors with a fixed number of components. We may visualize each component as a separate track of the tape.

4- Multitape Taring Machines: An extended TM model has some fixed number of tapes greater than one. A move of this TM is based on the state and on the vector of symbols scanned by the head on each of the tapes. In a move, the multitape TM changes state, overwrites symbols on the cells scanned by each of its tape heads, and moves any or all of its tape heads one coll in either direction. Although able to recognize certain languages faster than the conventional one-tape TM, the multitape TM cannot recognize any language that is not RE,

> Nondeterministic Turing Machines: The NTM has a finite number of choices of next move (state, new symbol, and head move) for each state and symbol scanned. It accepts an input if any sequence of choices leads