Before asking: My background is natural science and a bit of "coding" skills. I didn't study rigorous mathematics and logics since undergrad freshman, and this question is based on some videos and articles I read on the internet.
I've seen a lot of explanations regarding the Halting Problem, but all of the explanations I've seen so far evade one critical point, and it has been bugging me ever since.
So the popular "demonstration" of the proof for the halting problem goes like this.
- Suppose there is a function $h(x)$ which is 1 if program $x$ halts, and 0 otherwise.
- Let $g(x)$ to be a program that loops infinitely if $x=1$, and halts otherwise.
- Make $f(x)=g(h(x))$.
- Whether $f(f)$ halts or not cannot be decided, thus halting problem is undecidable.
Wikipedia lists a bit more complicated version of the sketch of the proof with introducing the input for the program, but I think it too shares the same problem I'm about to describe:
What bugs me is, I thought that to determine whether a program "will halt" or "will not halt", the program must be "complete." So, by "complete" I mean the "program" should be a set of fixed (although not necessarily finite) instructions. Like a number, compared to a function. For me, $h(x)$ is a function that takes a program and returns a value. $g(x)$ is a function, or a "template of program" (or co-program, or whatever is the appropriate term), that takes a value and returns a program. So, by design $g(x)$ alone cannot be a program, it is only a program. $f(x)=g(h(x))$ is a function that takes a program and returns a program, but not a program by itself. Thus, if you make $f(f)=f\circ f$, it still requires an argument $x$ to complete it as $f\circ f (x)$. In other words, $f$ seems to be outside of the domain of $f$ without an argument. And as soon as you complete the function by giving it an argument, the decidability of $f\circ f$ depends solely on the decidability of $h$. Or at least that seems natural to me.
What am I missing here?