Cтраница 2
Эта работа касается определения нижних границ времени вычисления некоторых входно-выходных преобразований и взаимосвязи между временем вычисления и размерностью лент машины Тьюринга. Метод, использованный при установлении этой границы, применяется в разд. Этот результат обобщается в разд. Хартманиса - Стирнза [2, 3] не может быть значительно улучшен и что имеется существенная разница между размерностью и количеством лент машины Тьюринга. [16]
В то же время Т считывает очередной входной символ не более чем через с шагов на рабочих лентах. Прибавляя лишние холостые операции, можно добиться того, чтобы Т читала с постоянной скоростью с шагов на входной символ. Именно это и делает алгоритм Хартманиса и Стирнза. [17]
Итак, для приведенного примера время наилучшего вычисления, которого можно достичь в случае одноленточной машины с записью на ленте, пропорционально квадрату времени наилучшего вычисления, которого можно достичь в случае двулен-точной машины. С другой стороны, из работы Хартманиса и Стирнза [2] известно, что если данная двуленточная машина завершает свои вычисления за Т2 ( п) единиц времени, то должна существовать одноленточная машина, которая завершает свои вычисления за время C [ Ti ( n) ] 2, где С-константа. Другими словами, переходя от двуленточной машины к одноленточной, никогда не нужно требовать более чем квадрата времени вычисления. Однако теперь мы имеем пример, в котором квадрат необходим. Таким образом, закон квадрата Хартманиса - Стирнза не может быть, вообще говоря, улучшен. [18]