Help Understanding the Halting Problem

Question

There are certain points about the halting problem that do not make sense to me. I couldn't seem to find a good breakdown of it that addresses my notes below. I was wondering if someone could clarify or correct my understanding of it.

To start, every version of the proof I have heard seems vague on how it defines the halting check. So, I will go through each different version of what could constitute a halting check.

1. We define our halting check as a check on a program that may or may not requires input and is only haltable if it can NEVER go on indefinitely. For example, we have a piece of code that may take input and has an internal loop or logic. If any input would cause the loop to run indefinitely, then it is NOT haltable.
2. We define our halting check as a check on a program that may or may not require input and must have at least one set of input that would cause it to stop, to be considered haltable. For example, we have a piece of code that may take input and has an internal loop or logic. If any input would cause the loop to stop, then that program is haltable.
3. We define our halting check by the given parameters and not the program itself. So, this is not defining a program as halt-able or not. But, whether given certain input, if that input would cause the program to halt. For example, the program given input x halts, but given input y runs indefinitely. We would return halt for p(x) and return not halt for p(y). This is not defining a program as halt-able, but instead a program with input as halt-able or not.

We start with the normal halting problem premise:

1. We have the assumption that a program, we will call H, can be built such that it takes program x as input and determines if it is haltable. If the other program is haltable it returns true. If the other program is not haltable it returns false.
2. We now define a second program, which we will call H+. H+ will take a program x as input. If it determines that x is haltable, the program H+ will run forever. If it determines x is not haltable, the program H+ will halt.
3. Then we run some variation of H+(H+), or run H+ on itself and the result is a contradiction and this is the proof.

However, as I noted, this doesn't necessarily seem true as long as we stick to our definitions of haltable above.

1. Let's go through option 1. We have program H, that we reasonably know can return true or false. Some programs are haltable and some programs are not haltable. This is a fact. Based, on this, we know that H+ on certain programs x will occasionally run forever. So, H+(H+) should by definition stop. Outer H+ checks internal H+ to see if all paths are halt-able. It returns false, there are paths that are indefinite. So, the external H+ simply stops.

2. Let's go through option 2. This check is the same as above. We have program H, that we reasonably know can return true or false. Some programs are haltable and some programs are not haltable. This is a fact. Based, on this, we know that H+ will occasionally halt. So, H+(H+) should by definition run forever. Outer H+ checks internal H+ to see if it has any paths that are halt-able. It returns true, there are paths that would cause the internal H+ to halt. So, the external H+ simply runs forever.

3. Let's go through option 3. The initial way we would write this is H+(H+). We want to determine if this is haltable or not. Well, this program/method isn't complete, right? Since the internal H+ also needs a variable for us to do the check. So, it would need to be H+(H+(x)). Obviously, we can set that internal x to H or H+. But, by definition, those would also require input. Thus we couldn't provide the definition as we want to for the problem at hand. This doesn't prove that the program is a contradiction. It just proves that it can't be used to test the input we are trying to give to the program.

Answer 1

It seems you are struggling to understand the definition of the halting problem. So I will try my best to define it so you can understand easily.

Our task, is to create some algorithm, which we will call $H$ and will solve the following problem:

• We are given inputs $\langle M, x\rangle$ such that $M$ is the description of another algorithm (for example, the text representing the code in a file), and $x$ is an arbitrary input to $M$, represented as a string
• Our job is to return $True$ if $M$ when fed with the input $x$ doesn't run forever (that is, there is some finite time such that after that much time $M$ will give us an answer). We will return $False$, if $M$ gets stuck in some sort of infinite loop when fed with the input $x$ (that is, no matter how much we will wait, it will never give us an answer)

Now, the halting problem theorem states that no matter how hard you will try, such an algorithm $H$ that solves this problem cannot exist.

---

To prove the non-existance of $H$ in the halting problem, here is what you do:

• Assume (towards contradiction) that such an $H$ does in fact exist.
• Now we want to get some contradiction. The basic idea is to somehow feed $H$ as an input to itself or some other similar program.

And those are the specifics:

We will build from $H$ a different algorithm $H^+$, that given an input $\langle M\rangle$ when $M$ is a description of another algorithm, it will get stuck in an infinite loop if $H(M,M)$ returns $True$ and otherwise halt.

Notice, that this new program $H^+$ gets a single input! Therefore, it is valid to ask what is the value of $H^+(H^+)$? But now you notice the weird part. You use $H^+$ on itself. You can think of this as a program that opens the file that stores the the code of it, and reading it. After you understand why this tricky part is valid, you will find that actually $H^+(H^+)$ cannot halt, as if it would have halted then $H(H^+,H^+)$ would have returned $True$, and by the definition of $H^+$ it means that it would have actually just gotten stuck in an infinite loop (and hence doesn't halt, in contradiction)! And a similar argument can prove that $H^+(H^+)$ also must halt, since otherwise $H(H^+,H^+)$ would have returned $False$, and you can complete it from here.