Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима?
Проблема пустотности для вычислительной модели (например, автомат конечного состояния, автомат с переменным нажатием, квантовый автомат с ограниченной ошибкой со счетчиком, детерминированный LBA и т. Д.) Состоит в том, чтобы определить, является ли для данной такой машины язык, распознаваемый / определяемый этой машиной пустой. Здесь описание машины должно быть конечным!
Я знаю, что слово «самый простой» немного расплывчато. Для некоторых несравненных вычислительных моделей может быть более одного ответа.
Как особое замечание, я считаю, что вопрос станет более интересным, если сосредоточиться на унарном и двоичном алфавите по отдельности.
Обратите внимание, что существует много вычислительных моделей, для которых проблема остановки разрешима, но проблема пустоты (и некоторые другие проблемы) неразрешима, например, линейные ограниченные автоматы (LBA) .
источник
Ответы:
Вероятно, вы уже получили их в сумке :-)
С двоичными алфавитами пустота остается неразрешимой для:
Машины с односторонним движением с одним бесконечным счетчиком и одним магазином с опрокидыванием, обеспечивающим не более одного разворота [3]
Двусторонние машины детерминированных конечных автоматов с кратными обратными счетчиками (даже над ограниченным языком) [3].
Без состояния (переходы зависят только от отсканированного символа) 2-головные 2-сторонние детерминированные конечные автоматы, даже когда каждая головка выполняет только одно обращение на входной ленте [4].
Изменить : на границе:
[1] Тат-Ханг Чан. На двухсторонних слабых встречных машинах . Теория математических систем 01/1987;
[2] Ричард Ф. Боннер, Русинс Фрейвальдс и Максим Кравцев. 2001. Квантовые и вероятностные односторонние конечные автоматы со счетчиком . В материалах 28-й конференции по актуальным тенденциям в теории и практике информатики Пьештяны: теория и практика информатики (SOFSEM '01), Лешек Пачольски и Петер Ружичка (ред.). Springer-Verlag, Лондон, Великобритания, Великобритания, 181-190.
[3] Оскар Х. Ибарра. 1978. Многооборотные машины с ограничением обращения и проблемы их решения . J. ACM 25, 1 (январь 1978), 116-133.
[4] Оскар Х. Ибарра, Юхани Кархумяки, Александр Охотин,О многоголовых автоматах без состояний: иерархии и проблема пустоты , Теоретическая информатика, том 411, выпуск 3, 6 января 2010 года, страницы 581-593, ISSN 0304-3975.
[5] Чжэ Дан, Оскар Х. Ибарра, Чжи-вэй Сунь. О проблемах пустоты для двустороннего nfa с одним ограниченным обращением счетчиком . В учеб. Тринадцатый Int. Symp. по алгоритмам и вычислениям (2002)
источник