Автоматика и телемеханика
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор
Правила для авторов
Загрузить рукопись

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Автомат. и телемех.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Автоматика и телемеханика, 1961, том 22, выпуск 6, страницы 748–755 (Mi at12277)  
Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий в конечных автоматах

М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр, И. М. Смирнова, А. А. Таль

Москва
PDF полного текста (1310 kB)
Аннотация: Вводится понятие о рекурсивных событиях, формализующее понятие «событие, эффективно заданное словесным описанием». Ставится проблема распознавания тех рекурсивных событий, которые представимы в конечном автомате. Доказывается теорема об алгоритмической неразрешимости этой проблемы. Попутно вводится понятие о представлении в автомате рекурсивной функции и дается критерий распознавания представимых функций.
В связи с тем, что этот круг вопросов обсуждается на страницах журнала «Автоматика и телемеханика» впервые, разъясняются также и некоторые известные понятия и факты.
Тип публикации: Статья
Образец цитирования: М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр, И. М. Смирнова, А. А. Таль, “Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий в конечных автоматах”, Автомат. и телемех., 22:6 (1961), 748–755
Цитирование в формате AMSBIB
\RBibitem{1}
\by М.~А.~Айзерман, Л.~А.~Гусев, Л.~И.~Розоноэр, И.~М.~Смирнова, А.~А.~Таль
\paper Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий в конечных автоматах
\jour Автомат. и телемех.
\yr 1961
\vol 22
\issue 6
\pages 748--755
\mathnet{http://mi.mathnet.ru/at12277}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/at12277
  • https://www.mathnet.ru/rus/at/v22/i6/p748
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Автоматика и телемеханика
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2025