computation-theory - 证明我们可以决定图灵机是否对某些输入采取至少 100 步

Question

我们知道问题是“<em>这个图灵机在那个输入上是否至少采取了这个有限数量的步骤？” 是可判定的，因为它总是回答是或否，如果机器达到给定的步数，它会说是，如果在此之前停止，它会说否。

现在这是我的疑问：如果它在达到那么多步骤之前就停止了——即输入要么（1）被接受，要么（2）被拒绝，或者（3）如果它没有停止而是进入无限循环——那么，当我们在情况（3）中时，我们如何确定它总是在那个循环中？我的意思是，如果它不是永远运行，而是在某个时间点退出循环，那么它可能会超过所要求的步骤数，现在可以做出决定，这在以前是不可能的。如果是这样，那么当我们知道被困在一个循环中我们将无法对结果发表任何意见时，我们怎么能得出结论是可以判定的呢？

标签： computation-theoryturing-machinesdecidable

Answer 1

（当我编辑它时，我已经或多或少地回答了你的问题。）

问题是，将图灵机M、数字N和值X作为输入并返回yes或no的决策系统（图灵机、算法或任何其他等效形式）完全控制其执行方式M在X上。它一步一步地模拟它。因此它可以运行M(X)的一步，增加一个指令计数器，将其与N进行比较，一旦达到给定的步数，它就会停止并返回yes。此时，模拟机M无需处于最终状态，实际上完全计算M(X)很可能发散。我们不在乎，因为我们只运行前N 步。