|
This article is cited in 8 scientific papers (total in 8 papers)
On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions
V. A. Buevich Computation Center, Academy of Sciences of the USSR
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]).
Received: 17.03.1971
Citation:
V. A. Buevich, “On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions”, Mat. Zametki, 11:6 (1972), 687–697; Math. Notes, 11:6 (1972), 417–421
Linking options:
https://www.mathnet.ru/eng/mzm9837 https://www.mathnet.ru/eng/mzm/v11/i6/p687
|
|