Докажите, что КПК с k стеками распознается по Тьюрингу
Когда-то это было домашнее задание, но сейчас я использую его для пересмотра; Но нет решения этой проблемы. Любые советы будут высоко ценится.
Вопрос задается следующим образом: "Пусть k-PDA будет автоматом с пониженным доступом с доступом к k стекам. 1-PDA - это стандартный PDA, и вы видели, что 2-PDA могут распознавать любой распознаваемый по Тьюрингу язык. Покажите это для любого k ≥ 0, любой язык, распознаваемый как k-PDA, распознается по Тьюрингу ".
Непосредственно скопировать и вставить, кто-нибудь может помочь с этой проблемой? Кроме того, я чувствую, что это неправильно написано, но я не уверен, что было бы правильно.
1 ответ
Кажется, что мы можем моделировать движения k-pda с помощью многолентовой (k-tape) машины Тьюринга, чьи движения можно моделировать с помощью стандартной машины Тьюринга.