# What is the strongest weaker version of the halts() function?

I was wondering about some questions related to the Halting problem. I might have not understood all the assumptions in it fully. Would you kindly help me, please?

I understand that the construction in the proof leads to a contradiction. My thoughts are:

• If one runs these theoretical programs in the real world, I would expect that the output of halts(f()) will oscillate between true and false with a frequency dependent on the processing speed. This all happens because the execution of f() is made dependent on the output of halts(f()). Self-referenced.

• Obviously there are programs which do not need to be run by a testing halts() function and they can be still decided if they halt or not. For example the following will obviously not halt and there are IDEs which already detect it:

while(true)

;

• Based on the previous 2 thoughts, can we state that there can be such halts() program that tells us if a program halts or not and oscillates between the two values only if the input program code takes the output of a halts(f()) function as an input in the inside?

Such halts() is still useful. Even if it cannot tells us a certain answer for a constructed, self-referenced pathological case.

Basically I am trying to figure out what is the strongest weaker version of the halts() function. What can we expect from it?

• I don't know what you mean by "the output will oscillate between true and false". The output is a single value -- there is no changing over time or "oscillation".
– D.W.
Commented May 23, 2021 at 21:50
• I assumed this program would be realized in a way that it keeps on processing even after its original input has changed, therefore I believed it would end up oscillating between true/false output. I think I was missing what vonbrand pointed out below in an answer: "halt(f) that always halts and always answers correctly" My thought was that it stays in its self-referential loop without an end. Commented May 25, 2021 at 8:52
• Sounds like there is some misconception. The input doesn't change, either. When you run a program, you run it on a single fixed input.
– D.W.
Commented May 25, 2021 at 16:20
• Yes, thank you for the clarification. I noticed that the reasoning does not care about the implementation of halts(). However I wonder how an implemented halts(f) function is expected to run on a function f which is dependent on the output of halts(f) itself? To me, halts(f) does not seem to ever be able to return an output. I believe it would stay in an infinite self-referencing loop, when it tried to analyze the function. Commented May 26, 2021 at 18:52
• My other question is, can there be a halts(f) that works for all the non-pathological non-self-referencing functions? It is not a big deal, I think, if there is a halts(f) function that actually works for all the other functions that were not constructed for its failure. Commented May 26, 2021 at 18:53

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 "Yes", "No", or "Don't know" (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 "Yes" for them, and "Don't know" 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 "Don't know", it'd know that for them the answer is "No" --just running the program would tell eventually if the answer is "Yes"). The point is there can't be a way to answer all cases correctly.