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

 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}