我们知道问题是“<em>这个图灵机在那个输入上是否至少采取了这个有限数量的步骤?” 是可判定的,因为它总是回答是或否,如果机器达到给定的步数,它会说是,如果在此之前停止,它会说否。
现在这是我的疑问:如果它在达到那么多步骤之前就停止了——即输入要么(1)被接受,要么(2)被拒绝,或者(3)如果它没有停止而是进入无限循环——那么,当我们在情况(3)中时,我们如何确定它总是在那个循环中?我的意思是,如果它不是永远运行,而是在某个时间点退出循环,那么它可能会超过所要求的步骤数,现在可以做出决定,这在以前是不可能的。如果是这样,那么当我们知道被困在一个循环中我们将无法对结果发表任何意见时,我们怎么能得出结论是可以判定的呢?