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

Question

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

haltChecker = function (arg) => bool

例如在 JavaScript 中，

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

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

谢谢。

Answer 1

halting-problem是不可判定的。运气不好。

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