0

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.

  1. Suppose there is a function $h(x)$ which is 1 if program $x$ halts, and 0 otherwise.
  2. Let $g(x)$ to be a program that loops infinitely if $x=1$, and halts otherwise.
  3. Make $f(x)=g(h(x))$.
  4. 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?

Hojin Cho
  • 164
  • The Wikipedia article specifically mentions that this argument is merely intended to provide intuition, not as a proper proof. Indeed, a purported halts function wouldn't take a subroutine, but rather source code and an input for it. Something like Cantor Diagonalization is typically used, as the wiikipedia article discusses in depth. – lulu Jul 26 '23 at 16:27
  • @lulu That is also what I've been wondering. If you take a function and make it a number by whatever method, then how can you say that the number is representing the same entity as the function? If not, how is feeding a function to itself important? Lastly, wikipedia describes "A rigorous proof addresses these issues.", which is exactly I want to see the explanation, hopefully without taking a semester or two of courses, if possible. – Hojin Cho Jul 26 '23 at 16:33
  • 1
    The proof given in the wiki article isn't bad, but as a general matter, I wouldn't try to learn complicated proofs from Wikipedia. this question gives a few arguments, and links to others. – lulu Jul 26 '23 at 16:35

0 Answers0