Extended pushdown automata
Pushdown automata are a class of automata which consist of a finite state machine and a last-in-first-out stack. Pushdown automata have instructions to traverse its finite state graph, optionally interact with input and output, and to interact with its stack.
Pushdown automata can do more things than FSMs, thanks to this stack. An example is recognizing balanced nested parentheses. However, they are not as powerful as Turing machines. Therefore, they constitute an intermediate class of machines.
Some pushdown automata have additional instructions or data structures available, termed extended pushdown automata or extended PDAs, and some have restrictions placed on what the stack can store. These extended PDAs, as well as their potential restrictions, have implications that can change which computational class they belong to.
Terminology and assumptions
A bounded stack is a stack which can only have a finite number of elements pushed onto it, contrasted with unbounded stack which has no such restriction.
A stack of bounded elements or a stack consisting of bounded cells is a stack in which each element/cell has a finite amount of possible states. Unbounded elements can have infinitely many different states.
The top of stack or TOS is the element on the very top of a stack, the element that was most recently pushed and will be popped next. The next of stack or NOS is the element immediately beneath the TOS. The bottom of stack or BOS is the element that was first pushed to the stack, and will be the last popped.
For simplicity, the following instructions, in addition to the standard PDA instructions, are assumed to exist:
- Increment TOS (modulo if bounded elements)
- Decrement TOS (modulo if bounded elements, cannot create negative results)
- Transition depending on TOS state
These instructions can be created using a variety of methods depending on platform/language, but they are generally accessible via an add and a sub instruction, which add or subtract the TOS and NOS.
| Turing complete | |||
|---|---|---|---|
| Addition | Unbounded stack | Unbounded elements | Both unbounded |
dup |
No | No | No |
swap |
No | Yes | Yes |
rot |
No | Yes | Yes |
over |
No | No | Yes |
| A box | No | Yes | Yes |
roll |
No (BSM) | Yes | Yes |
| Another stack | Yes | Yes | Yes |
mul and div |
No | Yes | Yes |
reverse |
Yes | Yes | Yes |
A stack with duplicate
Duplicate (dup) is a very common instruction in stack-based languages. The instruction effectively pushes the TOS without popping anything. The result is an exact duplicate of the prior TOS being the new TOS, with the NOS also being a copy of the prior TOS.
While dup is useful, it does not change the computational class of a PDA. This is because dup does not allow for the machine to recoverably access any more than the TOS, which is already the case for a PDA without a duplicate instruction.
A stack with swap
Consider a stack machine with an added command: swap. This command swaps the top two elements on the stack, such that the top of stack is now the next of stack and vice versa. A swap instruction allows for the machine to recoverably access two elements on the stack.
It seems trivial to then construct a Minsky machine using our standard additional instructions, with a notable difference. If a jump occurs the TOS and NOS will not automatically swap to some canonical state. Instead, the program must be made such that each jump will only happen on a known arrangement of the TOS and NOS. That is, a target must not be jumped to by a state where counter 0 is TOS and counter 1 is NOS, as well as a state where counter 1 is TOS and counter 0 is NOS, lest the identity of the counters be irrecoverable.
While this may seem restricting to the point that a counter machine would be impossible to construct, Minsky's proof of the two counter machine's Turing completeness uses only algorithms which satisfy the known state jump rule.
Therefore, a machine with a stack of at least 2 unbounded elements, a swap instruction, increment, and fused conditional decrement, is Turing complete.
A similar swap instruction which instead swaps TOS and BOS instead of TOS and NOS, can be proven Turing complete for a stack of unbounded elements for the same reasons. Further, an instruction which instead rotates the top three elements of the stack allows for the same amount of computational complexity with the same requirements.
A stack with over
A similar instruction to dup is over which duplicates NOS instead of TOS. While this does allow the machine to access two elements, NOS cannot be changed. Despite this limitation, it is nonetheless possible to construct a two counter machine.
Instead of swapping TOS and NOS or some other arrangement, we instead "leapfrog" our two counters. To increment the counter at TOS we simply increment, to do the same for NOS we perform an over and then increment. Assuming elements and the stack are unbounded, we can use the same argument for swap to show that this machine is Turing complete. The stack must be unbounded otherwise only a finite number of these leapfrogs can occur.
A stack with a box
Suppose we have a stack machine with an additional place to put a single element. This small storage place will be referred to as the box. To interact with the box the pop instruction is changed to a pop to box (popb) instruction, and a push from box (pushb) instruction is added.
The additional box allows us to store two recoverable elements at once. We can also use the box to interact with NOS arbitrarily, allowing us to not only have two recoverable elements, but two elements which we can access at any time. Such a machine is Turing complete for the same reason that the PDA with swap is.
However, if an additional instruction is added, which could be any of push true if box is full, jump if box is full, push box if box is full else no-op, pop to box if box is empty else no-op, or something similar, then arbitrary algorithms for two counter machines can be implemented, not just the universal one described by Minsky. This is possible as all of these instructions allow us to determine which of the counters is TOS, and correct the stack to some canonical ordering.
A stack with roll
Piet has an interesting instruction that very few other languages have: roll. This instruction rolls the elements of the stack according to the TOS and NOS. The instruction rolls around the top NOS values up TOS many entries. This can be pictured as popping off NOS many values into a circular array, then moving the start pointer forward TOS many times, and finally pushing the results in order.
The roll instruction is a generalized form of swap (roll 2 items 1 times is swap), and thus forms a Turing complete system.
While roll seems like it should be more capable than swap, its ability to roll is limited by the element determining how many elements to roll in total. If that number is bounded, then only a finite number of elements are accessible, constituting a bounded-storage machine. If it is unbounded, then the swap method already proves Turing completeness, albeit in a more roundabout way than using the stack as a tape directly, which is possible with an unbounded roll.
Two stacks
A PDA with two stacks is Turing complete. This can be visualized as two stacks with their tops pointing at each other. The opposing stacks can be used as a tape, a pop from the right one moves the tape rightwards, and vice versa for the left. The space in between the two stacks represents the currently viewed cell, and is stored in the state of the machine.
Assuming the stacks are unbounded the machine is Turing complete. To access the infinite tape from emptied stacks, simply push a 0 to the opposing stack whenever a pop from an empty stack occurs. Whether or not the elements are bounded is irrelevant, as Turing machines can operate with both bounded and unbounded cells.
If the stacks are bounded then the system is still Turing complete, but not via the opposing stacks method. Instead, the box method is used, as a stack is simply a generalized box with more capacity.
A stack with mul and div
If the PDA has mul and div instructions, with some method of determining the divisibility of the TOS (potentially using the rest of the stack, or a specific instruction), then only the TOS must be accessible. Unconditional mul with divisibility testing div describes the multiplicative counter machine, which is Turing complete for at least one counter.
A stack with reverse
The reverse command reverses the stack completely, such that the BOS is now the TOS and vice versa, through the entire stack. Reverse for a stack of two elements is equivalent to swap and is thus Turing complete for unbounded elements. For unbounded stacks, reverse permits the use of the stack as a double-ended queue. To push or pop from the front (the output side) simply perform a regular push or pop. To push or pop from the back (input side) first perform a reverse and then perform the push or pop, and perform another reverse to return to a canonical state.
Unbounded deques are Turing-complete, as they are generalized queues, which are also Turing-complete.