Theory of Computation

5.1   ADDING A SECOND STACK; TURING MACHINES

We introduced the PDA as a special case (albeit nondeterministic) of the URM, with a single number-type read/write variable—the stack variable. Actually, we viewed this variable as a string-type variable suppressing a detailed look into how a URM can effect string operations such as “pop” and “push”, until now. As in Section 2.11, we can identify strings over a finite alphabet of m symbols with natural numbers—the latter written in notation base-(m + 1). The correct way to do this (cf. 2.11.0.32, III) is to fix an order of the alphabet and identify its members {a₁, a₂, . . . ,a_m} with the “digits” 1, 2, ... , m (i.e., a_i with i). Thus a non-empty string

is uniquely represented by (and represents) the number

j_r(m + 1)^r + j_r−1(m + 1)^r−1 + ... j₁(m + 1) + j₀

0 corresponds to the string ∊.

Assume now that the stack variable is x, and that its contents is the string γ, which, in detail, is the string in (1). Moreover, let us have the stack top located at the right end of γ rather than the left end.

Pause. Why is this not an about face of any significance vis à vis our earlier conventions?

Then we can do a pop—and assign the popped symbol in the variable z, if we wish—as follows

The stack (contents) change corresponds to the effect of

Both ...