Simultaneously One-Turn Two-Pushdown Automata

recursively enumerable languages, one-turn two-pushdown automata

It is proved that simultaneously one-turn two-pushdown automata are equivalent to the Turing machines.

Consider two consecutive moves m_1 and m_2, made by a two-pushdown automaton, M, whose pushdowns are denoted by \pi_1 and \pi_2. If during m_1 M does no shorten \pi_1, for some i=1, 2, while during m_2 it shortens \pi_1, then M makes a turn in \pi_1 during m_2. If M makes turn in both \pi_1 and \pi_2 during m_2, this turn is simultaneous. A two-pushdown automaton is one-turn if it makes no more than one turn in either of its pushdowns during any computation. A two-pushdown automaton is simultaneous one-turn if it makes either no turn or one simultaneous turn in its pushdowns during any computation. This paper demonstrates that every recursively enumerable language is accepted by a simultaneously one-turn two-pushdown automaton. Conesequently, every recursively enumerable language is accepted by a one-turn two-pushdown automaton.