# zbMATH — the first resource for mathematics

Undecidability of the completeness and $$A$$-completeness problems for some systems of automaton functions. (English. Russian original) Zbl 0851.03009
Discrete Math. Appl. 5, No. 1, 31-42 (1995); translation from Diskretn. Mat. 7, No. 1, 52-65 (1995).
In this paper, an automaton function $$(a$$-function) means a function determined by a (finite) automaton and its initial state which transforms input superwords to output superwords. For any set $$M$$ of $$a$$-functions, $$M$$ is called complete if the set of all $$a$$-functions can be obtained from $$M$$ by superposition and feedback operations. The so-called completeness problem means to describe all complete sets. Restricting $$a$$-functions to the set of all words of fixed length, the concept of an $$A$$-complete set is defined. The $$A$$-completeness problem means to describe all $$A$$-complete sets.
Let $$P^{(1)}$$ be the set of all truth functions. It is known that for the systems of automata of the form $$P^{(1)} \cup N$$, where $$N$$ is a finite set, the completeness problem [the author, Diskretn. Mat. 4, No. 4, 41-55 (1992; Zbl 0815.94025)] and the $$A$$-completeness problem [V. A. Buevich, Conditions of the $$A$$-completeness for finite automata (Moscow Univ. Press, Moscow, 1986) (in Russian)] are algorithmically decidable. Let $$\Phi \subseteq P^{(1)}$$ be a closed class of truth functions. The completeness problem and the $$A$$-completeness problem for systems of the form $$\Phi \cup N$$ are called $$\Phi$$-completeness problem and $$\Phi$$-$$A$$-completeness problem, respectively. The following results are proved in this paper: For every class $$\Phi$$ of type $$F^\infty$$, $$S$$, $$P$$, or $$O$$, the $$\Phi$$-completeness problem and $$\Phi$$-$$A$$-completeness problem are algorithmically undecidable.

##### MSC:
 03D05 Automata and formal grammars in connection with logical questions 03D35 Undecidability and degrees of sets of sentences 68Q45 Formal languages and automata 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010)
Full Text: