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