Машина Тьюринга - бесконечная лента в одном или двух направлениях

Я видел машины Тьюринга, изображенные бесконечными лентами в одном и двух направлениях. Есть ли разница в мощности таких машин Тьюринга или они в основном эквивалентны? В своей голове я думаю, что они эквивалентны, так как я предполагаю, что должен быть какой-то способ представить двустороннюю бесконечную ленту как одностороннюю бесконечную ленту, но я не могу найти доказательство или пример.

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

Идея состоит в том, чтобы разрезать вашу дважды бесконечную ленту на две части, чтобы у вас было две одинаково бесконечные ленты: левая и правая, которые вы в конечном итоге объедините. Вы можете пометить концы местоположением ленты, содержащим специальный символ EOF. Вы также дублируете свой конечный элемент управления, чтобы у вас было два идентичных конечных элемента управления. Предполагается, что у вас есть устройство для передачи управления (см. Ниже), поэтому, когда левая машина пытается выйти за правый конец своей ленты, она передает управление правой машине в крайнем левом положении ленты (непосредственно перед левый конец правой ленты). И наоборот, при попытке передать левый конец правой ленты.

Теперь, чтобы различить левую и правую машины, мы меняем имена состояний и символы ленты, индексируя их с и соответственно для левой и правой машины. И мы соответственно меняем переходы двух машин, чтобы они работали как раньше.$R$$L$

Теперь мы готовы объединить две половинки ленты, например, сложив правую на левую. Для этого вы переворачиваете правую половину ленты и стараетесь соответствующим образом изменить переходы, меняя правую на левую и левую на правую. Затем вы объединяете две половины ленты в одну ленту, содержащую пары символов, левый и правый, причем каждый компонент может быть пустым.

Вы снова изменяете переходы обеих машин, так что левые (соответственно правые) переходы используют и изменяют только левую (соответственно правую) часть пар на ленте. Затем вы объединяете управление двумя машинами путем простого объединения множеств соответственно для состояний и для переходов.

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

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

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

Затем вы убираете отвертку, так как это может быть опасно для детей.

PS Я только показал, что дважды бесконечную ленту можно смоделировать одной бесконечной лентой. Обратное кажется слишком очевидным.