# Reasoning given with explanation of Halting Problem

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.

• 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? Oct 4 at 18:49