javascript - 检查函数是否针对所有输入停止

Question

我想编写一个程序来检查一个函数，比如 f 是否停止其输入的所有值。简而言之 -

haltChecker = function (arg) => bool

例如在 JavaScript 中，

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

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

谢谢。

Answer 1

停止问题是不可判定的。倒霉。

举一个简单的例子，考虑Collat​​z 猜想（实际上，这是一个不好的例子，因为它没有被证明是不可判定的——但它证明了这个问题是困难的 :)。

Answer 2

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

Answer 3

这也是一个停机问题，无法以这种通用形式解决。你能做的最好的事情是编写一个程序，如果函数对所有输入都停止，它可能会返回 true，但它也可能无限期地运行。