Check if a function halts for all inputs
-
15-03-2021 - |
Question
I want to write a program that checks if a function, say f halts for all values of its input. In short -
haltChecker = function (arg) => bool
e.g. in JavaScript,
bool haltChecker ( f(a) ){
return {f halts for all values of a};
}
Solution in JS is not required, any language will do.
Thanks.
Solution
The halting-problem is undecidable. Tough luck.
To give a simple example, consider the Collatz conjecture (actually, this is a bad example, as it is not proven to be undecidable - but it demonstrates that the problem is hard :).
OTHER TIPS
You could amaze your professor with this.
This is also know a the Halting Problem and cannot be solved in this generic form. The best you can do is to write a program which might return true if the function stops for all inputs but it also might run indefinitely.
Licensed under: CC-BY-SA with attribution
Not affiliated with StackOverflow