我正在阅读有关图灵机的库克定理。在其证明中，据说图灵最多需要 n^k 步（其中 k 是整数且 k > 0）来计算长度为“n”的输入
这可能是假设图灵机对于给定的输入确实停止了它进一步说我们最多有 n^k 步，我们不需要无限的磁带。带有 n^k 个元素的胶带就足够了，因为车床不会移动超过
为什么我们说图灵机最多需要 n^k 步？
我正在阅读有关图灵机的库克定理。在其证明中，据说图灵最多需要 n^k 步（其中 k 是整数且 k > 0）来计算长度为“n”的输入
这可能是假设图灵机对于给定的输入确实停止了它进一步说我们最多有 n^k 步，我们不需要无限的磁带。带有 n^k 个元素的胶带就足够了，因为车床不会移动超过
为什么我们说图灵机最多需要 n^k 步？