turing-machines - 可以解决某些有限函数的停止问题吗？

Question

我的理解是，对于一个足够简单的功能，让我们说

function(boolean input){
    while(input){
    }
}

可以判断它是否会因任何可能的输入而停止。

很容易看出，上面的函数会因为 fhaltingFinder(haltingFinder)` 而终止而false不是终止，本质上是一个悖论。true. It's only impossible to solve the halting problem for an arbitrary function, as of course you can evaluate

我的理解正确吗？

Answer 1

是的，你当然是对的。拿一个甚至没有循环的函数：它总是会停止。对于像常规语言和上下文无关语言这样的整个类，停止问题是微不足道的：相应的机器（有限自动机，没有 epsilon 移动的下推自动机）只能使步数等于输入单词的长度，因此总是会停止。不过，当然，您可以为简单的功能设计非停止计算，例如为常规语言设计一个带有无用循环的图灵机。