Quote:
Originally Posted by Buffy
That's what I said too! And yes, its very cute! 
The program itself is of finite length. It's input is itself, but the only way to get "infinite regress" is to apply the input to the input to the input, each discrete input is indeed finite, and that's what you appeared to be talking about. Without this, there's no possibility for "infinite regress."
There's nothing special about the nature of a Halting Problem Program: it's just an arbitrary algorithm. Saying that *by definition* feeding a Halting Problem Program to itself would cause infinite regress does not really make any sense without making lots of assumptions about what makes up such a program. You'll need to explain what you're talking about in more detail to get past this issue.
What is clear is that: - If your assumption that no Halting Problem Program can resolve its own halting status for itself, then the theorem is by definition proven. Your assumption is that it never completes, then it's halting status is undecidable, showing that there's at least one instance of an algorithm that is not decidable.
- You could even circumscribe the recursive case, and you can still prove that the halting problem is undecidable: Your assumption that "Every Halting problem undecidability proof asks us to assume that such functions could operate on themselves" is actually not the case, heck the proof in the Wikipedia page on the topic doesn't make this assumption, and there are other approaches as well. So its actually unnecessary to make this exception.
If you'd like to take a stab at the notion that all Halting Problem Programs result in infinite regress or otherwise do not halt given themselves as input, we might have an interesting discussion, but you need to prove it: its not true by definition.
But even then, it does not have any impact on whether or not the Halting Problem Theorem is false.
Not to see many things, not to hear them, not to let them approach one--first piece of ingenuity, first proof that one is no accident but a necessity, 
Buffy |
I do not have to prove that this would happen - that it is not true is an assumption that the undecidability proof makes. And therefore it is just as likely if not more likely to be the cause of the contradiction that results.
IE if there exists a halting machine H that always loops if run on itself but otherwise works, the halting problem is still possibly decidable except for halting machines. Which is very likely a trivial distinction from the idea that the halting problem is possibly solvable.
That being said there is pretty good reason to believe that such an infinite regress really would occur. Any halting machine run on itself would at some point try to trace at least a part of its own computations - at which point it would redo everything it had done up to that point when it would again restart and so forth. Each time it would be tracing an additional level of depth.
The wikipedia "proof" does assume that the g function could operate on itself. Note where it says that the function g corresponding to the halting problem is the eth possible input to the halting function. It's asking us to run:
g(g()), which tests h(g(),g())
So here g traces it's own computation creating the same infinite regress.
