On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions
Matematičeskie zametki, Tome 11 (1972) no. 6, pp. 687-697
Cet article a éte moissonné depuis la source Math-Net.Ru
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]).
@article{MZM_1972_11_6_a9,
author = {V. A. Buevich},
title = {On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions},
journal = {Matemati\v{c}eskie zametki},
pages = {687--697},
year = {1972},
volume = {11},
number = {6},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_1972_11_6_a9/}
}
V. A. Buevich. On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions. Matematičeskie zametki, Tome 11 (1972) no. 6, pp. 687-697. http://geodesic.mathdoc.fr/item/MZM_1972_11_6_a9/