Может ли КПК с двумя стеками принимать RE Language?

Question

Итак, мне было немного сложно понять, что именно означает строка, на которой машина Тьюринга не останавливается. Я где-то читал, что машина Тьюринга эквивалентна детерминированному c автомату с двумя стеками. Но как детерминированные c автоматы с 2 стеками будут принимать строку, которая не останавливается, когда для любой конечной строки она определена как остановка ... Я что-то упустил ??

Answer 1

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

Показать КПК с двумя стеками, по крайней мере, так же мощно, как TM с двумя стеками, немного сложнее, но в основном идея такова. что вы можете моделировать одиночную ленту, используя два стека следующим образом:

1. Вызов одного стека L, а другой R
2. Содержимое L представляет все, что находится слева от головки ленты (включая текущий символ)
3. Содержимое R представляет все, что находится справа от головки ленты
4. Чтобы перезаписать текущий символ: pop от L и pu sh до L
5. Для перемещения влево на ленте: pop от L и pu sh до R
6. Для перемещения вправо на ленте: pop от R и pu sh до L

Итак, мы можем перемещать влево и вправо и перезаписывать символы. Это позволяет нам смоделировать ленту, что в любом случае может сделать TM.