Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Anybody can ask a question
Anybody can answer
The best answers are voted up and rise to the top
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:
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?