Deterministic single-state 2PDAs are Turing-complete
The well-known simulation of Turing machines by push-down automata
with two stacks is shown to be possible, even if only a single state
is allowed for the push-down automaton and the latter is
deterministic. This sheds new light on the nature of states and the
relationship between different types of abstract machines.
Moreover, further refinements of the Chomsky hierarchy are proposed.