Publication Details
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.
@article{BUT41080,
author="Alexandr {Meduna}",
title="Simultaneously One-Turn Two-Pushdown Automata",
journal="International Journal of Computer Mathematics",
year="2003",
volume="2003",
number="80",
pages="679--687",
issn="0020-7160"
}