Является ли автомат с двумя стопками эквивалентным машине Тьюринга?

41

В этом ответе упоминается

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

Я хотел знать относительно правды смелой части выше. На самом деле это правда или нет? Как можно найти ответ на этот вопрос?

computability turing-machines automata pushdown-automata Lazer
источник
В выделенном тексте есть две претензии, но заголовок вашего вопроса предполагает, что вас интересует только одна из них.
Тайсон Уильямс
@TysonWilliams: да, так?
Лазер
Это смущает. Я не знаю, какое подмножество двух требований вы хотите оправдать.
Тайсон Уильямс
Для того, кто выделен жирным шрифтом , как указано в вопросе.
Лазер
2
@Lazer: жирный текст содержит два утверждения («CSL требует двух стеков», «два стека эквивалентны TM»). Поскольку CSL является надлежащим подмножеством RE, только один может быть истинным.
Рафаэль

Ответы:

38

Два бита на этот ответ;

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

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

Чтобы увидеть эквивалентность, просто представьте первый стек как содержимое ленты слева от текущей позиции, а второй - как содержимое справа. Вы начинаете так:

  • Нажмите на нормальные маркеры "дна стопки" на обеих стопках.
  • Переместите ввод в левый стек (используйте недетерминизм, чтобы «угадать» конец ввода).
  • Переместите все в правильный стек (чтобы держать вещи в правильном порядке).

Теперь вы можете игнорировать ввод и делать все с содержимым стеков (которое имитирует ленту). Вы щелкаете, чтобы прочитать, и нажимаете, чтобы писать (так что вы можете изменить «ленту», нажимая что-то отличное от того, что вы читаете). Затем мы можем симулировать ТМ, выталкивая из правого стека и нажимая влево, чтобы двигаться вправо, и наоборот, чтобы двигаться влево. Если мы достигаем нижней части левого стека, мы ведем себя соответствующим образом (останавливаем и отклоняем или остаемся там, где вы есть, в зависимости от модели), если мы достигаем нижней части правого стека, мы просто толкаем пустой символ слева.

Для полного формального доказательства см. ответе на другой вопрос .

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

Люк Мэтисон
источник