Рассмотрим такую ТМ, которая всегда завершается, имеет n состояний и алфавит ленты / ввода {0,1}.На входе размера m он должен остановиться не более чем за 2 * m * n шагов.Это потому, что он не может пройти через одно и то же состояние, читая один и тот же символ дважды без продвижения вперед;если бы он это сделал, он бы не остановился.
Это означает, что все проблемы, решаемые такой ТМ, находятся в P. С другой стороны, существуют регулярные ТМ для решения проблем в EXPTIME.Поскольку P является подходящим подмножеством EXPTIME, две модели не эквивалентны.
Кстати: машина Тьюринга обычно имеет только одну ленту, поэтому копирование на другую ленту не является опцией.