Quote:
Originally Posted by Kriminal99
Aww isn't that cute... I didn't say anything about feeding it anything infinite. I said that any halting machine which was fed a finite encoding of itself would cause an infinite regress instead of going through it's normal function.
|
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.
Quote:
Originally Posted by Kriminal99
Thus the only thing proven is that it cannot operate on itself. It could still very well exist and handle all other machine/input combos.
|
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
