RUS  ENG
Full version
JOURNALS // Matematicheskie Zametki // Archive

Mat. Zametki, 1972 Volume 11, Issue 6, Pages 687–697 (Mi mzm9837)

This article is cited 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]).

UDC: 519.9

Received: 17.03.1971


 English version:
Mathematical Notes, 1972, 11:6, 417–421

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025