PROOF: The essential idea is that two stacks can simulate one Turing-machine tape, with one stack holding what is to the left of the head and the other stack holding what is to the right of the head, except for the infinite strings of blanks beyond the leftmost and rightmost nonblanks. In more detail, let L be L(M) for some (one-tape) TM M. Our two-stack machine S will do the following;

1. S begins with a bottom-of-stack marker on each stack. This marker can be the start symbol for the stacks, and must not appear elsewhere on the stacks, In what follows, we shall say that a stack is empty when it contains only the bottom-of-stack marker.

2. Suppose that w$ is on the input of 5. S copies w onto its first stack, ceasing to copy when it reads the endmarker on the input,

3. S pops each symbol in turn from its first stack and pushes it onto its second stack. Now, the first stack is empty, and the second stack holds Ш, with the left end of w at the top.

4. S enters the (simulated) start state of M. It has an empty first stack, representing the fact that M has nothing but blanks to the left of the cell scanned by its tape head, S has a second stack holding w, representing the fact that w appears at and to the right of the cell scanned by Ms head.

5. S simulates a move of M as follows,

(a) S knows the state of M. say q, because S simulates the state of M in its own finite control.

(b) 5 knows the symbol X scanned by Ms tape head; it is the top of 5s second stack. As an exception, if the second stack has only the bottom-of-stack marker, then M has just moved to a blank; S interprets the symbol scanned by M as the blank.

(c) Thus, S knows the next move of M.

(d) The next state of M is recorded in a component of 5s finite control, in place of the previous state.

(e) If M replaces X by У and moves right, then 5 pushes Y onto its first stack, representing the fact that Y is now to the left of Ms head. X is popped off the second stack of 5. However, there are two exceptions:

i. If the second stack has only a bottom-of-stack marker (and therefore, X is the blank), then the second stack is not changed; M has moved to yet another blank further to the right.

ii. If У is blank, and the first stack is empty, then that stack remains empty. The reason is that there are still only blanks to the left of Ms head.

(f) If M replaces X by Y and moves left, S pops the top of the first stack, say Z, then replaces X by ZY on the second stack. This change reflects the fact that what used to be one position left of the head is now at the head. As an exception, if Z is the bottom-of-stack marker, then M must push BY onto the second stack and not pop the first stack.

6. S accepts if the new state of M is accepting. Otherwise, S simulates another move of M in the same way.

□

8.5.3 Counter Machines

A counter machine may be thought of in one of two ways:

1. The counter machine has the same structure as the multistack machine (Fig. 8.20), but in place of each stack is a counter. Counters hold any nonnegative integer, but we can only distinguish between zero and nonzero counters. That is, the move of the counter machine depends on its state, input symbol, said which, if any, of the counters are zero. In one move, the counter machine can:

(a) Change state.

(b) Add or subtract 1 from any of its counters, independently. However, a counter is not allowed to become negative, so it cannot subtract 1 from a counter that is currently 0.

2. A counter machine may also be regarded as a restricted multistack machine. The restrictions are as follows:

(a) There are only two stack symbols, which we shall refer to as Zo (tlie bottom-of-stack marker), and A.

(b) Zo is initially on each stack.

(c) We may replace Zq only by a string of the form XZo, for some i > 0.

(d) We may replace X only by x* for some г > 0. That is, Zq appears only on the bottom of each stack, and all other stack symbols, if any, are X.

We shall use definition (1) for counter machines, but the two definitions clearly define machines of equivalent power. The reason is that stack XZq can be identified with the count i. In definition (2), we can tell count 0 from other counts, because for count 0 we see Zo on top of the stack, and otherwise we see x. However, we cannot distinguish two positive counts, since both have X on top of the stack.

8.5.4 The Power of Counter Machines

There are a few observations about the languages accepted by counter machines that are obvious but worth stating:

Every language accepted by a counter machine is recursively enumerable. The reason is that a counter machine is a special case of a stack machine, and a stack machine is a special case of a multitape Turing machine, which accepts only recursiely enumerable languages by Theorem 8.9.

Every language accepted by a one-counter machine is a CFL. Note that a counter, in point-of-view (2), is a stack, so a one-counter machine is a special case of a one-stack machine, i.e., a PDA. In fact, the languages of one-counter machines are accepted by deterministic PDAs, although the proof is surprisingly complex. The difficulty in the proof stems from the fact that the nmltistack and counter machines have an endmarker S at the end of their input. A nondeterministic PDA can guess that it has seen the last input symbol and is about to see the $; thus it is clear that a nondeterministic PDA without the endraarker can siraulate a DPDA with the endmarker. However, the hard proof, which we shall not attack, is to show that a DPD.A without the endmarker can siraulate a DPDA with the endmarker.

The sinprising result about counter machines is that two counters are enough to simulate a Turing machine and therefore to accept every recursively enumerable language. It is this result we address now, first showing that three counters are enough, and then simulating three counters by two counters.

Theorem 8.14; Every recursively enumerable language is accepted by a three-counter machine.

PROOF: Begin with Theorem 8.13, which says that every recursively enumerable language is accepted by a two-stack machine. We then need to show how to siraulate a stack with counters. Suppose there are г - 1 tape symbols used by the stack machine. We may identify the symbols with the digits 1 through г - 1, and think of a stack X1X2 - Xn as an integer in base r. That is, this stack (whose top is at the left end, as usual) is represented by the integer Xnr - + Xn-ir - + --- + Х2Г+Хг.

We use two counters to hold the integers that represent each of the two stacks. The third counter is used to adjust the other two counters. In particular, we need the third counter when we either divide or multiply a count by r.

The operations on a stack can be broken into three kinds: pop the top symbol, change the top symbol, and push a symbol onto the stack. A move of the two-stack machine may involve several of these operations; in particular, replacing the top stack symbol A by a string of symbols must be broken down into replacing X and then pushing additional symbols onto the stack. We perform these operations on a stack that is represented by a count г, as follows.