On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
Kojiro Kobayashi, Shigeru Sekiguchi · Journal of the ACM · 1966
The problem of deciding predicates concerned with m -tuples of words by means of 2-way multitape finite automata is considered. In general, more than m tapes are used to decide a predicate concerned with m -tuples of words. In such a way, a necessary and sufficient condition for a predicate to be decidable by a 2-way multitape finite automaton is obtained. The relation between the ability of Turing machines and that of 2-way multitape finite automata is also discussed.