So far we’ve considered idealised machines with up to two stacks and at least one stack has always been restricted to either only push operations or pop operations. What if we remove some of these restrictions.
The next simplest machine we could consider is one with two stacks whose use is unrestricted. One will be the input stack and one will be the output stack, with the output stack initially empty and the input stack finally empty, but in between we are allowed to push symbols onto the input stack or pop symbols off of the output stack if we wish. I’ll call such a machine a Turing machine, although this terminology requires some comments.
Just as every finite state automaton was a pushdown automaton, every pushdown automaton is a Turing machine, so anything which can be done be a pushdown automaton can be done by a Turing machine.
The definition I’ve just given for a Turing machine differs from the standard one in two respects. First, I never specified that the machine is deterministic. The standard definition requires this. Second, I allowed the machine to operate independently on its two stacks. The standard definition of a Turing machine uses a single tape rather than a pair of stacks. At each point the machine is at a given position on the tape, from which it’s allowed to move left or right. It’s allowed to read or change symbols only at this position. We can simulate this with a pair of stacks, one for the symbols to the left of this position and one for the symbols to its right. Any tape operation then corresponds to coordinated operations on the stack. Moving to an adjacent position, for example, involves popping from one stack and pushing to the other. So the standard Turing machine is restricted in two senses compared to what I’ve defined above. It’s deterministic and its permitted stack operations are only those combinations which correspond to tape operations. It turns out that both of these restrictions are more apparent than real though. We saw earlier that any finite state automaton can be simulated by a deterministic finite state automaton, via the power set construction. The corresponding statement for pushdown automata is false but the statement for Turing machines is true. It’s also possible simulate a machine with unrestricted stack operations with one where the stack operations are paired in the way they would be for a standard Turing machine with a tape. So although my definition of a Turing machine isn’t identical to the standard one the set of computations the two types of machines can do are identical.