|
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
Citing articles on Google Scholar:
Russian citations,
English citations
Related articles on Google Scholar:
Russian articles,
English articles
|
Number of views: |
This page: | 64 | Full text: | 48 |
|