What is the strongest weaker version of the halts() function?
The gist of the argument is that the assumption that a one can write a function halt(f) that always halts and always answers correctly if f halts leads to a contradiction (by way of self-reference, applying it to a variant of itself), thus such function can't be written.
Sure, you can write functions that answer &quot;Yes&quot;, &quot;No&quot;, or &quot;Don't know&quot; (or even never stop) always correctly. Say we consider C programs only, it is (more of less) easy to check they are just a main function that doesn't include any loops, and so answer &quot;Yes&quot; for them, and &quot;Don't know&quot; for anything else. You can certainly refine the above a lot, and each refinement can in itself be further refined (if a program could identify the cases where all have to answer &quot;Don't know&quot;, it'd know that for them the answer is &quot;No&quot; --just running the program would tell eventually if the answer is &quot;Yes&quot;). The point is there can't be a way to answer all cases correctly.