0
$\begingroup$

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?

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ 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". $\endgroup$
    – D.W. ♦
    Commented May 23, 2021 at 21:50
  • $\begingroup$ 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. $\endgroup$
    – polarka
    Commented May 25, 2021 at 8:52
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W. ♦
    Commented May 25, 2021 at 16:20
  • $\begingroup$ 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. $\endgroup$
    – polarka
    Commented May 26, 2021 at 18:52
  • $\begingroup$ 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. $\endgroup$
    – polarka
    Commented May 26, 2021 at 18:53

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Can we have a non-total halt(f) function such that it always answers if f halts or not when f is not self-referential? Is it true that there exists a halt(f) function that always halts and always answers correctly when f is not a deliberate pathological construction against halt(f) but an actual real useful program? I mean it is great to know that there is no halt(f) that gives an answer for any funstion, but it is still useful to have a halt(f) that answers for f's that are not built to make halt fail. $\endgroup$
    – polarka
    Commented May 25, 2021 at 9:00
  • $\begingroup$ Thank you for your answer. It is indeed helpful. $\endgroup$
    – polarka
    Commented May 25, 2021 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.