On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
The object of the paper is to give a solution of the following problem: Given a predicate \(P(X_1, X_2, \ldots, X_m)\) on \(\{\vartheta(\Sigma)\}^m\), the set of all \(m\)-tuples \((X_1, X_2, \ldots, X_m)\) of words on an alphabet \(\Sigma\), does there exist a finite automaton that decides for an arbitrary element of \(\{\vartheta(\Sigma)\}^m\) whether or not the predicate is true? Two types of 2-way multitape finite automata are defined to consider the above problem. The one is a usual finite automaton with a finite number of internal states and 2-way multitapes. The other is a modified Turing machine with a program composed of a finite number of instructions. It is shown that the ability of finite automata of the first type is equivalent to that of the second type. After preparing several lemmata with rigorous proofs, given by directly constructing the required programs, the authors give a necessary and sufficient condition for a predicate to be decidable by an automaton, and also show examples of predicates decidable by finite automata. By taking a proper Gödel numbering, they show that predicates decidable by finite automata are primitive recursive. Finally, it is shown that any partially computable function can be represented by using two predicates decidable by finite automata and one operation similar to minimization.
- Decision Problems of Finite Automata Design and Related Arithmetics
- scientific article; zbMATH DE number 3131080 (Why is no real title available?)
- scientific article; zbMATH DE number 7354705 (Why is no real title available?)
- scientific article; zbMATH DE number 3254906 (Why is no real title available?)
- Operations Which Preserve Definability in Languages
- Recursive unsolvability of Post's problem of Tag und other topics in theory of Turing machines
- Two Families of Languages Related to ALGOL
- Weak Second‐Order Arithmetic and Finite Automata
This page was built for publication: On the Class of Predicates Decidable by Two-Way Multitape Finite Automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5514601)