Какие расширения машины Тьюринга расширяют возможности машины?

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

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

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

(Пока мы говорим о расширениях базовых TM, взгляните на Quantum TM, которые, насколько я могу судить, все еще не решают новых проблем: http://en.wikipedia.org/wiki/Quantum_Turing_machine)

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

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

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

Ну, наверное. Я не уверен, что TM не может имитировать такую ​​систему ...