Note that it is possible to use the finite control of the multistack machine to do each of the operations that requires counting up to г or less.

1. To pop the stack, we must replace i by i/r, throwing away any remainder, which is Xi. Starting with the third counter at 0, we repeatedly reduce the count i by r, and increase the third counter by 1. When the counter that originally held i reaches 0, we stop. Then, we repeatedly increase the original counter by 1 and decrease the third counter by 1, until the third counter becomes 0 again. At this time, the counter that used to hold i holds i/r.

2. To change X to F on the top of a stack that is represented by count i, we increment or decrement i by a small amount, surely no more than r. If У > X, as digits, increment i by У - X; if У < X then decrement г by

X-y.

3. To push X onto a stack that initially holds i, we need to replace i by ir + X. We first multiply by r. To do so, repeatedly decrement the coimt г by 1 and increase the third counter (which starts from 0, as always), by r. When the original counter becomes 0, we have ir on the tiiird count<;r. Copy the third coimter to tlie orial counter and make the third counter 0 again, as we did in item (1). Finally, we increment the original counter byX.

To complete the construction, we must initialize the counters to simrdate the stacks in theu: initial condition: holding only the start symbol of the two-stack machine. This step is accomplished by incrementing the two counters involved to some small integer, whichever integer from 1 to r -1 corresponds to the start symbol. □

Theorem 8Л5: Every recursively enumerable language is accepted by a two-counter machine.

PROOF: With the previous theorem, we only have to show how to simulate three counters with two counters. The idea is to represent the three counters, say г, j, and k, by a .single integer. The integer we choose is m = 2*35. One counter will hold this number, while the other is used to help multiply or divide m by one of the first three primes: 2, 3, and 5. To sinmlate the three-counter machine, we need to perform the following operations;

1. Increment i, j, and/or k. To increment i by 1, we multiply m by 2. We already saw in the proof of Theorem 8.14 how to multiply a count by any constant r, using a second counter. Likewise, we increment j by multiplying m by 3, and we increment к by multiplying m by 5.

2. Tell which, if any, of i, j, and к are 0. To tell if г = 0, we must determine whether m is divisible by 2. Copy m into the second counter, using the state of the counter machine to remember whether we have decremented

Choice of Constants in the 3-to-2 Counter Construction

Notice how important it is in the proof of Theorem 8.X5 2, 3, and 5 are distinct primes. If we had chosen, say m - 2*3-4, then m = 12 could represent either г = 0, j - 1, and - 1, or it could represent i = 2, j - I, and fc = 0. Thus, we could not tell whether i or fc was 0, and thus could not simulate the 3-counter machine reliahly.

m an even or odd number of times. If we have decremented m an odd number of times when it becomes 0, then f = 0, We then restore m by copying the second counter to the first. Similarly, we test if j = 0 by determining whether m is divisible by 3, and we test if fc - 0 by determining whether m is divisible by 5.

3. Decrement i, j, and/or fc. To do so, we divide m by 2, 3, or 5, respectively. The proof of Theorem 8.14 tells us how to perform the division by any constant, using an extra counter. Since the 3-counter machine cannot decrease a count below 0, it is an error, and the simulating 2-counter machine halts without accepting, if m is not evenly divisible by the constant by which we are dividing.

8.5.5 Exercises for Section 8.5

Exercise 8.5.1: Informally but clearly describe counter machines that accept the following languages. In each case, use as few counters as possible, but not more than two counters.

* a) {0 1 I n >m > 1}.

b) {0 1 \l<m<n}.

*! c) {o&c I i = j or i = fc).

!! d) {oVc* \ i = j от i = к oi j = k}.

!! Exercise 8.5.2: The purpose of this exercise is to show that a one-stack machine with an endmarker on the input has no more power than a deterministic PDA. L$ is the concatenation of language L with the language containing only the one string $; that is, L$ is the set of all strings wt such that w is in L. Show that if L$ is a language accepted by a DPDA, where $ is the endmarker sjTubol, not appearing in any string of L, then L is also accepted by some DPDA. Hint:

This question is really one of showing that the DPDA languages are closed under the operation L/a defined in Exercise 4.2.2. You must modify the DPDA P for L$ by replacing each of its stack symbols X by all possible pairs {X,S), where 5 is a set of states. If P has stack АГ1АГ2 X , then the constructed DPDA for L has stack (Xj, Si){X2, Si)-- {X ,S ), where each 5, is the set of states q such that P, started in ID {q,a,XiXi+i - X ) will accept.

8.6 Turing Machines and Computers

Now, let us compaie the Turing machine and the common sort of computer that we use daily. While these models appear rather different, they can accept exactly the same languages - the recursively enumerable languages. Since the notion of a common computer is not well defined mathematically, the arguments in this section are necessarily informal. We must appeal to your intuition about what computers can do, especially when the numbers involved exceed normal limits that are built into the architecture of these machines (e.g., 32-bit address spaces). The claims of this section can be divided into two parts:

1. A computer can simulate a Turing machine.

2. A Turing machine can simulate a computer, and can do so in an amount of time that is at most some polynomial in the number of steps taken by the computer.

8.6.1 Simulating a Turing Machine by Computer

Let us first examine how a computer can simulate a Turing machine. Given a particular TM M, we must write a program that acts like M. One aspect of M is its finite control. Since there are only a finite number of states and a finite number of transition rules, our program can encode states as character strings and use a table of trEmsitions, which it looks up to determine each move. Likewise, the tape symbols can be encoded as character strings of a fixed length, since there are only a finite number of tape symbols.

A serious question arises when we consider how our program is to simulate the Turing-machine tape. This tape can grow infinitely long, but the computers memory - main memory, disk, and other storage devices - are finite. Can we simulate an infinite tape with a fixed amount of memory?

If there is no opportunity to replace storage devices, then in fact we cannot; a computer would then be a finite automaton, and the only languages it could accept would we regular. However, common computers have swappable storage devices, perhaps a Zip disk, for example. In fact, the typical hard disk is removable and can be replaced by an empty, but otherwise identical disk.

Since there is no obvious limit on how many disks we could use, let us assume that as many disks as the computer needs is available. We can thus arrange that the disks are placed in two stacks, as suggested by Fig. 8.21. One stack