Может ли машина Тьюринга пройти начало ленты?

Question

У меня очень простой вопрос о токарных станках.

Если самое первое действие, которое требуется выполнить, включает в себя перемотку ленты, будет ли она возвращаться за начальную точку или это особый случай и останется ли она в начальной точке?

Answer 1

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

Answer 2

Лента в машине Тьюринга бесконечна в обоих направлениях;обычно предполагается, что все перед началом заполнено 0.

Answer 3

Лента бесконечно растягивается в обоих направлениях. Википедия имеет это сказать:

Лента, которая разделена на ячейки, одна рядом с другой. Каждая ячейка содержит символ из некоторого конечного алфавита. Алфавит содержит специальный пустой символ (здесь пишется как «B») и один или несколько других символов. Предполагается, что лента может произвольно расширяться влево и вправо, т. Е. Машина Тьюринга всегда снабжена таким количеством ленты, которое необходимо для ее вычисления.