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

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Avtomat. i Telemekh.:
Year:
Volume:
Issue:
Page:
Find






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


Avtomat. i Telemekh., 1961, Volume 22, Issue 6, Pages 748–755 (Mi at12277)  

Algorithmic unsolvability of problem of recognition of recursive event representability by finite automata

M. A. Aizerman, L. A. Gusev, L. I. Rozonoer, I. M. Smirnova, A. A. Tal

Moscow

Abstract: An idea of recursive event formalizing the «event effectively given by a word description» is introduced. The problem of recognition of recursive events which are representable in a finite automaton is suggested and the theorem of its algorithmic unsolvability is proved. At the same time an idea of representation of a recursive function in a finite automaton is given and a recognizability criterion for representable recursive functions is given.
Some well-known ideas and facts are also explained because all these problems are discussed in «Avtomatika and Telemeckanika» for the first time.

Full text: PDF file (1310 kB)

Citation: M. A. Aizerman, L. A. Gusev, L. I. Rozonoer, I. M. Smirnova, A. A. Tal, “Algorithmic unsolvability of problem of recognition of recursive event representability by finite automata”, Avtomat. i Telemekh., 22:6 (1961), 748–755

Citation in format AMSBIB
\Bibitem{1}
\by M.~A.~Aizerman, L.~A.~Gusev, L.~I.~Rozonoer, I.~M.~Smirnova, A.~A.~Tal
\paper Algorithmic unsolvability of problem of recognition of recursive event representability by finite automata
\jour Avtomat. i Telemekh.
\yr 1961
\vol 22
\issue 6
\pages 748--755
\mathnet{http://mi.mathnet.ru/at12277}


Linking options:
  • http://mi.mathnet.ru/eng/at12277
  • http://mi.mathnet.ru/eng/at/v22/i6/p748

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Avtomatika i Telemekhanika
    Number of views:
    This page:64
    Full text:48

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2021