DPDA для машины Тьюринга?

Question

Есть ли способ превратить детерминированные автоматы в систему Тьюринга? Я думал о размещении стека после ввода на ленте, с '#' между ними. Но кажется, что это невозможно доказать формально.

У вас есть какие-нибудь предложения? Кто-то уже делал это?

Спасибо

Answer 1

Автомат нажатия работает только в одном направлении. То есть он не может проследить свой шаг или вести счет.
Например, если вы хотите формальный язык:

L = {1^n+0^m | n>m, m>0}  

Здесь нет. из 1 больше, чем нет. нулей.
Эта проблема решается как DPDA, так и машиной Тьюринга.

Однако, если мы добавим еще одно условие, например:

L = {1^n.0^m.1^n | n>m, m>0}

Предполагая, что вы знаете, как решить вышеуказанную проблему в Turing Machine, вы поймете, что ее невозможно решить без обратного отслеживания входной ленты.
Поэтому нет способа сделать КПК таким же мощным, как машина Тьюринга.
Вот ссылка на Wiki для вашего лучшего понимания: https://en.wikipedia.org/wiki/Chomsky_hierarchy