Итак, мне было немного трудно понять, что именно подразумевается под строкой, на которой машина Тьюринга не останавливается. Я где-то читал, что машина Тьюринга эквивалентна детерминированному автомату с двумя стеками. Но как детерминированный автомат с двумя стеками примет строку, которая не останавливается, когда для любой конечной строки определено, что она останавливается... Я что-то упустил??
Может ли КПК с двумя стеками принимать RE Language?
Ответы (1)
КПК с двумя стеками эквивалентен машине Тьюринга. Чтобы показать, что ТМ по крайней мере так же мощен, как двухстековый КПК, мы можем использовать тот факт, что ТМ точно так же мощен, как двухленточный ТМ. В двухленточном TM мы можем ограничить использование лент, чтобы имитировать их стекирование. Таким образом, ТМ, безусловно, может делать то же, что и КПК с двумя стеками.
Показать, что КПК с двумя стеками по крайней мере так же мощен, как TM с двумя стеками, немного сложнее, но в основном идея состоит в том, что вы можете смоделировать одну ленту, используя два стека, следующим образом:
- Вызовите один стек L, а другой R
- Содержимое L представляет все, что находится слева от головки ленты (включая текущий символ).
- Содержимое R представляет все, что находится справа от головки ленты.
- Чтобы перезаписать текущий символ: вытащите из L и нажмите на L
- Чтобы переместиться влево по ленте: нажмите на L и нажмите на R.
- Чтобы двигаться вправо по ленте: выдвиньте из R и нажмите на L
Итак, мы можем перемещаться влево и вправо и перезаписывать символы. Это позволяет нам имитировать ленту, что в любом случае может сделать ТМ.
person
Patrick87
schedule
29.05.2020
