Matematicheskie Zametki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Forthcoming papers
Archive
Impact factor
Guidelines for authors
License agreement
Submit a manuscript

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Mat. Zametki:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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

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
English version:
Mathematical Notes, 1972, Volume 11, Issue 6, Pages 417–421
DOI: https://doi.org/10.1007/BF01093729
Bibliographic databases:
Document Type: Article
UDC: 519.9
Language: Russian
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
Citation in format AMSBIB
\Bibitem{Bue72}
\by V.~A.~Buevich
\paper On the algorithmic undecidability of $A$-completeness for the boundedly determinate functions
\jour Mat. Zametki
\yr 1972
\vol 11
\issue 6
\pages 687--697
\mathnet{http://mi.mathnet.ru/mzm9837}
\mathscinet{http://mathscinet.ams.org/mathscinet-getitem?mr=313028}
\zmath{https://zbmath.org/?q=an:0265.02032|0251.02047}
\transl
\jour Math. Notes
\yr 1972
\vol 11
\issue 6
\pages 417--421
\crossref{https://doi.org/10.1007/BF01093729}
Linking options:
  • https://www.mathnet.ru/eng/mzm9837
  • https://www.mathnet.ru/eng/mzm/v11/i6/p687
  • This publication is cited in the following 8 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Математические заметки Mathematical Notes
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024