Какие удлинители машины Turing расширяют мощность машины?

Question

Из всех расширений машины Тьюринга есть (например, двусторонняя бесконечная лента, ОЗУ, несколько головок чтения/записи и недетерминизм), позволяет любой из них разрешать ТМ решать проблемы, которые ранее были неразрешимы?

Answer 1

Двусторонняя бесконечная лента не растягивает вычислительную мощность. ОЗУ изменяет скорость обработки в некоторых ситуациях, но не вычислительную мощность. Множество головок чтения/записи могут использоваться для имитации недетерминированной машины Тьюринга (NDTM), но при этом не улучшаются ее вычислительная мощность.

Таким образом, нет никаких новых проблем с этими настройками, но скорость вычислений иногда может быть изменена.

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

(В то время как мы находимся на тему расширений для основного ДЧА, взглянуть на квантовом ДЧЕ, которые до сих пор не решают новые проблемы, насколько я могу сказать: http://en.wikipedia.org/wiki/Quantum_Turing_machine)

Answer 2

Стандартная машина Тьюринга модель - конечный автомат с двунаправленной неограниченной лентой - может имитировать любую модель конечного хранилища. В самом деле, я думаю, вы обнаружите, что он может имитировать любую бесконечномерную модель хранения; это может занять много времени, но это можно сделать.

Таким образом, чтобы найти истинное расширение для ТМ, которое действительно отличается от того, что есть, нам нужно получить экзотику, и нам нужно посмотреть на другую половину системы: конечный автомат. Наиболее очевидным расширением было бы сделать сам автомат бесконечным, т. Е. Дать ему бесконечное число состояний, бесконечную программу. Недостатком этого является то, что он заставляет ваш мозг болеть! Вполне возможно, что в этом случае вы можете получить систему, в которой число общих состояний превышает ℵ , т. Е. Существует не только бесконечная система, но вы уже не знаете точно, в каком состоянии вы находитесь.

Более простое расширение - это изменение определения терминации, так что машина считается «завершающей», если она посещает определенный набор (общих) состояний бесконечно часто, а не вводит специальное состояние остановки. Понятно, что это скорее как нерегулярное выражение ω, которое определяется даже при сопоставлении с бесконечными строками, и совершенно очевидно, что такая система не обязательно будет озадачена простыми версиями проблемы остановки, которые классическая ТМ не может (он мог бы обнаружить неприятное циклическое поведение), хотя все равно будут программы, которые он не мог бы анализировать (как мы знаем из приложения теоремы Гёделя к вычислению). Однако, что это на самом деле означает на практике, я не знаю; расширенная TM ω - все еще довольно странная теоретическая конструкция, и ее очень странность должна предупредить нас о том, что она находится вне вычислений, как мы ее знаем.

Ну, наверное. Я не уверен, что ТМ не смогла имитировать такую ​​систему ...