Deterministic single-state 2PDAs are Turing-complete

Jürgen Koslowski


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.