Quote:
Originally Posted by Kriminal99
Quote:
|
Originally Posted by Buffy
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.
|
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. |
Yes you do. The theorem makes no assumption of that the Halting Problem Program must use itself as input.
Quote:
Originally Posted by Kriminal99
The wikipedia "proof" not only assumes that both involved functions could operate on themselves, they do not specify a finite input as you seemed to require. 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(?))
|
But that's not a requirement for the proof! The core of the proof is simply that the f() algorithm is different from h() .
For your argument to disprove the theorem, you need to demonstrate why Halting Problem Programs are somehow different than any other algorithm in a fundamental way.
That the operation is "recursive" is of no consequence: an algorithm is an algorithm. There's no special effect on *any* algorithm simply because it takes itself as input. That's quite non-sensical.
In other words:
Quote:
Originally Posted by Kriminal99
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.
|
Yes, it's not only trivial because you've simply assumed that there is such an algorithm, it's more than insufficient in showing any sort of weakness in the proof.
Quote:
Originally Posted by Kriminal99
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.
|
Why are you making assumptions about what a halting machine would do? Isn't that the very charge that you are laying against the proof?
Why should your argument--for which you are providing no evidence or logic at all--be taken at face value when that is the very weakness you're--quite incorrectly--accusing the theorem of doing?
Human speech is like a cracked kettle on which we tap crude rhythms for bears to dance to, while we long to make music that will melt the stars,
Buffy
