Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима?

12

Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима?

Проблема пустотности для вычислительной модели (например, автомат конечного состояния, автомат с переменным нажатием, квантовый автомат с ограниченной ошибкой со счетчиком, детерминированный LBA и т. Д.) Состоит в том, чтобы определить, является ли для данной такой машины язык, распознаваемый / определяемый этой машиной пустой. Здесь описание машины должно быть конечным!

Я знаю, что слово «самый простой» немного расплывчато. Для некоторых несравненных вычислительных моделей может быть более одного ответа.

Как особое замечание, я считаю, что вопрос станет более интересным, если сосредоточиться на унарном и двоичном алфавите по отдельности.

Обратите внимание, что существует много вычислительных моделей, для которых проблема остановки разрешима, но проблема пустоты (и некоторые другие проблемы) неразрешима, например, линейные ограниченные автоматы (LBA) .

Абузер Якарылмаз
источник
не следуйте за вопросом, но самая простая модель, вероятно, будет тривиальной или игрушечной. Вы имели в виду прямо противоположное, наименее простое? FSM часто рассматриваются как одна из простейших вычислительных моделей ...
vzn
Есть ли основания полагать, что остановка и пустота должны быть связаны?
Бабу
@babou: нет! Я просто пытался указать, что проблема разрешимости пустоты интересна для ограниченных моделей, но проблема остановки, наиболее известная среди других, - нет.
Абузер Якарылмаз

Ответы:

15

Вероятно, вы уже получили их в сумке :-)

  • Двухсторонний встречный автомат над одинарным алфавитом (Minsky61).
  • Двухсторонние слабые счетные машины (счетчик не влияет на вычисления, но машина останавливается, если счетчик достигает нуля) [1].
  • Квантовые одноконтурные автоматы [2].

С двоичными алфавитами пустота остается неразрешимой для:

  • Машины с односторонним движением с одним бесконечным счетчиком и одним магазином с опрокидыванием, обеспечивающим не более одного разворота [3]

  • Двусторонние машины детерминированных конечных автоматов с кратными обратными счетчиками (даже над ограниченным языком) [3].

  • Без состояния (переходы зависят только от отсканированного символа) 2-головные 2-сторонние детерминированные конечные автоматы, даже когда каждая головка выполняет только одно обращение на входной ленте [4].

Изменить : на границе:

  • (Открытая задача). Решаема ли проблема пустоты для двусторонних недетерминированных конечных автоматов с одним обратным ограниченным счетчиком над неограниченными языками? (над ограниченными языками это разрешимо [5])

[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)

Марцио де Биаси
источник
Ух ты ... Есть ли сайт со всей этой информацией, хорошо организованной относительно решений об автоматах и ​​языках? Тот же вопрос для закрытия свойств.
Бабу
2
@babou: я не знаю, но я согласен с вами, «Зоопарк автоматов» или такой сайт, как graphclasses.org, был бы очень полезен (и я также заметил, что, вероятно, сейчас самое подходящее время для исследования по теме) ,
Марцио Де Биаси