Abstract:
A functional system $P$ is considered, whose elements are functions realized by the so-called finite automata and known as the boundedly determinate functions (B. D. functions) and whose operations are known as the operations of superposition. The system $\mathfrak{M}$ of B.D. functions is called $A$-complete if, for an arbitrary B. D. function and for every natural number $\tau>0$, we can obtain (with the help of the operations of superposition) a B. D. function coinciding with the given one of all the words of lenth $\tau$ from the B. D. functions of the system $\mathfrak{M}$. The question is: does there exist an algorithm for deciding the $A$-completeness of an arbitrary finite system of B. D. functions? It is shown that such an algorithm does not exist (see [4]).