I just watched a video by Computerphile on the halting problem (https://www.youtube.com/watch?v=macM_MtS_w4) . I’m having some difficulty understanding the argument as it is made. Let me explain it as I see it:
So that our terminology is the same, H is a (hypothetical) program which can analyze another program to see if it halts. H+ is a modified version of H which loops forever if the analyzed program halts and halts if the analyzed program does loops forever.
In order to run H, you need to specify 2 things – a program and the input to that program. The Input to the analyzed program is necessary because the program’s behavior will depend on its input.
According to Computerphile’s explanation of Turing’s argument, we are asked to consider what would happen if H+ were to analyze H+ with H+ as its input. Since there are a lot of H+’s being thrown around, let’s define H+1 as the program that I am running, H+2 as the program being analyzed, and H+3 as the input to H+2. (Of course, H+1, H+2, and H+3 have the exact same code; they are just being used in different ways.) My question is this: if we require H+3 as an input to H+2, then shouldn’t we require an input to H+3? And if we continue the pattern and use H+4 as an input to H+3, then wouldn’t this mean that we require an H+5 as an input to H+4? And so on?
If you counter by saying that Turing’s argument doesn’t require H+3 to have an input (or that its input doesn’t have to be H+), then doesn’t this break the whole symmetry of the problem? After all, the whole point of Turing’s argument (as I currently understand it) is that if H+2 runs on H+3 and halts then it would be a contradiction to have H+1 loop forever on H+2 since H+1,H+2,and H+3 are all identical (and vice versa were H+2 to loop forever on H+3). But the situation isn’t identical. In one case H+2 is running on H+3. In the other, H+1 is running on "H+2-running-on-H+3".
I guess you could say that each H+ maybe can only look one step in front of it, so that H+1 only “sees” H+2 and H+2 only sees H+3. But then what does H+3 see? Doesn’t it need some input of its own? After all, whether or not H+3 halts depends on the program it’s given. If so, this brings it back to my first point (that we would need an H+4).
It seems to me this whole argument falls apart. Either you would need an infinite stack of H+’s which can’t happen, or you have a finite stack which because of the discontinuity at the end means that the symmetry of each level doesn’t translate to the one below it.
So what am I missing?