对于某些有限功能，可以停止使用吗？

Question

这是我的理解是十分简单的功能，让我们说

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

就可以判断它会阻止任何可能的输入。

很容易看出上述函数将终止为false，而不是终止于haltingFinder（haltingFinder），并且本质上会产生一个悖论。

我的理解是否正确？

Answer 1

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