Ограничения машины Тьюринга, которые делают остановку разрешимой

33

Если ограничить машины Тьюринга конечной лентой (т. Е. Использовать ограниченное пространство ), то проблема остановки решаема, в основном потому, что после ряда шагов (которые можно рассчитать из числа состояний Q , S и размер алфавита), конфигурация должна быть повторена.SQS

Существуют ли другие естественные ограничения машины Тьюринга, которые делают остановку разрешимой?

Конечно, если граф переходов между состояниями не имеет циклов или циклов, остановка разрешима. Любые другие?

Джозеф О'Рурк
источник
1
Вы также можете рассмотреть ТМ, которое может быть доказано как полное, скажем, PA, ZFC, ...
Kaveh
@Kaveh: Можно ли это сформулировать как ограничение поведения ТМ, в каком-то почти физическом смысле?
Джозеф О'Рурк
Нет, я так не думаю.
Каве
1
Решение проблемы на машине с одним регистром (с инструкциями безусловного увеличения-и-перехода, если ноль-затем-прыжок-еще-уменьшение-и-прыжок и остановка) разрешимо.
wchargin
AFAIK Проблема остановки для машин Тьюринга с ограниченным пространством S, не разрешима машинами Тьюринга, ограниченными пространством S.
Таемир

Ответы:

30

Довольно естественным и изученным вариантом является машина ограниченного реверса ленты (число реверсивных лент ограничено); см. например:

Юрис Хартманис: Расчеты ленты Тьюринга, связанные с обращением ленты. J. Comput. Сист. Sci. 2 (2): 117-135 (1968)


Редактировать : [этот вариант более искусственный] проблема остановки решаема для не стирающей машины Тьюринга, которая имеет не более двух левых инструкций в алфавите ; см. Морис Маргенштерн: Непрекращающиеся машины Тьюринга: граница между разрешимой проблемой остановки и универсальностью. Теор. Вычи. Sci. 129 (2): 419-424 (1994){0,1}

Марцио де Биаси
источник
Граница обращения ленты действительно вполне естественна. Благодарность!
Джозеф О'Рурк
18

Учитывая, что передача параметров в подпрограммы и огромную часть управления памятью в основных компьютерных языках основана на стеке, очевидным и естественным вариантом является ограничение неограниченной памяти машины Тьюринга в качестве стека.

Такая модель обладает хорошими свойствами , в дополнение к тому, что она может быть разрешимой (хорошо известной для КПК ):

Понятие КПК может быть обобщено на вспомогательный автомат ( S ( n ) -AuxPDA)S(n)S(n) . Это состоит из

  1. входная лента только для чтения, окруженная конечными маркерами,
  2. контроль конечного состояния,
  3. лента для чтения и записи длиной , где n - длина входной строки, иS(n)n
  4. стек

В «Хопкрофт / Ульман (1979) Введение в теорию автоматов, языков и вычислений» (1-е изд.) Мы находим:

Теорема 14.1 . Следующие условия эквивалентны для .S(n)logn

  1. принимается детерминированным S ( n ) -AuxPDALS(n)
  2. принимается недетерминированным S ( n ) -AuxPDALS(n)
  3. находится в DTIME ( c S ( n ) ) для некоторой константы c .LDTIME(cS(n))c

с удивительным

Следствие находится в P тогда и только тогда, когда L принимается log n -AuxPDA.LPLlogn

Томас Климпел
источник
Спасибо, Томас, это тоже естественное ограничение.
Джозеф О'Рурк
3

формулировка этого вопроса является немного проблематичной, потому что машина Тьюринга с конечной лентой, вероятно, не сильно связана с машиной Тьюринга и ближе к / по существу, машине конечного состояния. аналогично всем остальным «ограничениям» на машинах Тьюринга, практически любое ограничение представляется совершенно другим явлением (т. е. кроме полноты по Тьюрингу с совершенно другими свойствами). на самом деле, в некоторых работах сейчас подробно описывается / изучается эта граница, и она может иметь некоторое грубое сходство с другой известной вычислительной границей, то есть NP-полными фазовыми переходами.

и это несколько нелогично, что «вычислительно более простая / полностью разрешимая» теория FSM появилась задолго до изобретения машины Тьюринга, по-видимому, несколько слабо вдохновленной ею. поэтому, возможно, один из способов перефразировать это - попросить «самые сложные разрешимые модели» вычислений или «изучение границы между неразрешимыми и разрешимыми вычислительными моделями».

так что в любом случае, затем, слегка переформулировав таким образом, разумная программа ответов / теорий / исследований, еще не перечисленная, является в настоящее время значительно разработанной и активно исследуемой / развивающейся теорией временных автоматов, которая только что получила церковный приз за Алара / Укропа. Вот пример статьи о временных автоматах и ​​изучении границы разрешающей способности модели вычисления (не), и есть много других в этом ключе.

ВЗН
источник
по совпадению вопрос кажется вполне концептуально похожим на тот, который недавно задавался в области компьютерных наук : какие языки являются наиболее выразительными, завершающими?
vzn
1
Спасибо за ссылки на синхронизированные автоматы , концепцию которых я не знал.
Джозеф О'Рурк
кстати, запоздалая мысль / дополнение: один аспект известной теории, который стремится / кажется отталкивает любое «естественное разрешимое расслабление» существующей ТМ, Rice thm . однако другая естественная идея / идея, в некоторой степени вызванная другими ответами, заключается в том, что вся иерархия времени и пространства и классы сложности - это все «естественные» разрешимые версии TM.
августа
Конечный автомат может быть слишком далек от машины Тьюринга, чтобы говорить об ограничении, но ограниченная машина Тьюринга, которая могла бы вычислять все примитивно-рекурсивные функции, была бы достаточно близкой, чтобы можно было разумно сказать, что это ограниченная модель машины Тьюринга.
Томас Климпел