КПК для преобразования машины Тьюринга

Question

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

Answer 1

Как указывает Вельбог в комментариях, просто используйте ленту как стек:

1. , когда КПК поместил бы в стек:

   • оставьте только текущий символ ленты
   • переместить головку ленты вправо
   • записать символ на ленту и остаться в том же положении

2. когда КПК выскочил из стека:

   • замените текущий символ пустым
   • переместите головку ленты влево

Обратите внимание, что эта конструкция означает, что для каждого перехода "pu sh" в вашем КПК потребуется дополнительное промежуточное состояние в TM для обработки двухэтапной операции перемещения-затем-записи. Есть разные способы структурировать это, так что, возможно, вместо этого вы можете использовать дополнительный шаг в операции pop.