I have read (and re-read) the informal proof of The Halting Problem. Can we not make the same argument using only the Program, without the Input {e.g. H(P) rather than H(P, I)}? I am confused by the step where we pass the Program as the Input as well. This seems to be the key since all explanations mention this step without fail.

In my mind whatever argument is being made can also be made by considering only the Program, without considering the Input part. There is obviously something that I am overlooking.

Addendum: I am referring to the following informal proof in Discrete Math by Rosen, 8e:

Assume there is a solution to the halting problem, a procedure called H(P, I). The procedure H(P, I) takes two inputs, one a program P and the other I, an input to the program P. H(P,I) generates the string “halt” as output if H determines that P stops when given I as input. Otherwise, H(P, I) generates the string “loops forever” as output. We will now derive a contradiction.

When a procedure is coded, it is expressed as a string of characters; this string can be interpreted as a sequence of bits. This means that a program itself can be used as data. Therefore, a program can be thought of as input to another program, or even itself. Hence, H can take a program P as both of its inputs, which are a program and input to this program. H should be able to determine whether P will halt when it is given a copy of itself as input.

To show that no procedure H exists that solves the halting problem, we construct a simple procedure K(P), which works as follows, making use of the output H(P, P). If the output of H(P, P) is “loops forever,” which means that P loops forever when given a copy of itself as input, then K(P) halts. If the output of H(P, P) is “halt,” which means that P halts when given a copy of itself as input, then K(P) loops forever. That is, K(P) does the opposite of what the output of H(P, P) specifies. (See Figure 3.)

Now suppose we provide K as input to K. We note that if the output of H(K, K) is “loops forever,” then by the definition of K, we see that K(K) halts. This means that by the definition of H, the output of H(K, K) is “halt,” which is a contradiction. Otherwise, if the output of H(K, K) is “halts,” then by the definition of K, we see that K(K) loops forever, which means that by the definition of H, the output of H(K, K) is “loops forever.” This is also a contradiction. Thus, H cannot always give the correct answers. Consequently, there is no procedure that solves the halting problem.

  • $\begingroup$ There are many different versions of the halting problem. Can you point out which version exactly you refer to, as well as the undecidability proof? Also, if you have an argument in mind, can you spell it out? $\endgroup$ Oct 4 at 18:49

Consider the "Total Halting" problem: Given the number of a program P, decide that it halts for every input. Assume we have a program TH for this. And say it either halts and says the truth, or it doesn't halt.

So what does TH(TH) do? If TH halts for every input, and gives the correct result when it halts, it will say "Yes". If TH doesn't halt for every input, then TH(TH) will either halt and say "No" or it will not halt.

But here is what is lacking: There is no obvious reason here that TH couldn't be built. I don't think it can be built, and I'm reasonably sure that it can be proven, but there is no simple contradiction here.

For a program that takes (program, input) as input, we can suggest that a program H(program, input) exists that decides correctly whether "program" halts on input "input" and cleverly constract a program and input where this fails. With only "program" as input, we have not enough material to produce a contradiction.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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