Mutli-трековые машины Тьюринга

Question

Я делаю домашнее задание, и у меня проблема с многоканальной (многодорожечной) машиной Тьюринга:

У нас есть многоленточная машина Тьюринга, которая всегда, прежде чем сдвинуть голову влево, пишетпустой символ.

Распознает ли эта машина тот же класс языков, что и стандартные машины Тьюринга?

У вас есть идеи, как это доказать?Конечно, стандартная машина Тьюринга распознает рекурсивно перечислимый язык (Typa-0 в иерархии Хомского).

Answer 1

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

Рассмотрим следующий КПК P:

1. P моделирует ТМдо первого шага влево и помещает вывод в стек.
2. ТМ движется влево с помощью щелчков из стека.
3. При повторном движении вправо ТМ читает только пробелы, пока не достигнет первого нетронутого входного символа.P может сделать это за один шаг.

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

Если это правильно, эти ТМ принимают только класс контекстно-свободных языков.Но эти детали должны быть разработаны, чтобы действительно доказать это.