Почему машина Тьюринга делает n^k шагов для вычисления ввода?
Я читал о теореме Кука для машины Тьюринга. В доказательстве говорится, что Тьюрингу потребуется не более n^k шагов (где k - целое число, а k > 0), чтобы вычислить входные данные длины 'n'.
Это, вероятно, предполагает, что машина Тьюринга останавливается для данного ввода. Далее говорится, что мы, поскольку существует не более n^k шагов, нам не нужна бесконечная лента. Ленты с n^k элементами достаточно, так как токарный станок не будет двигаться больше, чем это
Почему мы говорим, что машине Тьюринга нужно не более n^k шагов?