检查函数是否对所有输入都停止

Check if a function halts for all inputs

本文关键字：输入 函数 是否 检查      更新时间：2023-09-26

我想写一个程序，检查一个函数，比如f，是否对其输入的所有值都停止。总之-

haltChecker = function (arg) => bool

。在JavaScript中,

bool haltChecker ( f(a) ){
    return {f halts for all values of a};
}

不需要在JS中解决，任何语言都可以。

谢谢。

停机问题是无法确定的。坏运气。

给一个简单的例子，考虑Collatz猜想(实际上，这是一个糟糕的例子，因为它没有被证明是不可判定的-但它表明这个问题很难:)。

你可以用这个让你的教授大吃一惊。

这也被称为停机问题，不能用这种一般形式来解决。你能做的最好的是编写一个程序，如果函数停止所有输入，它可能返回true，但它也可能无限期地运行。

相关文章：