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.
- 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.
- 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.
- 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:
- 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.
- 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.
- 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.
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.
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.
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.