Quote:
Originally Posted by Buffy
That's ridiculous!
Just because you choose an algorithm that traces and that does not halt, does not invalidate the proof. What Turing is saying is that there aren't *any* that work!
If you identify a class of programs intended to solve the Halting Problem that by definition do not halt, it has no impact on the whether the theorem is valid.
Nor does it matter that the weaker claim that there exist programs that can solve the Halting Problem as long as they do not try to work on themselves: that's just an alternate theorem that its up to you to prove if you wish.
What you're arguing is somewhat interesting, heck it would be interesting to have a discussion concerning the validity of the assertion "all programs that use a tracing algorithm to determine halting states will not halt," which might even be true!
But as should be clear from the discussion so far, it bears absolutely no relevance in determining the validity of Turing's theorem. Any inability to see this simply comes from a misunderstanding of it.
The last part of your argument simply seems to be that nothing can be proven by contradiction, which would certainly be an interesting philosophical problem to attack, but it should be done in my opinion without the obfuscation of a particular theorem.
Such an approach is, to use your own term, "weak."
Well, nothing useful at any rate!
That's exactly what a 4 year old says when being scolded to stop poking his little sister....
Need a mirror? 
Nor should they! I'm perfectly harmless! 
Idealism is fine, but as it approaches reality the cost becomes prohibitive, 
Buffy |
What Turing says is of no interest to anyone, rather only what he can prove is useful. It is claimed that he has proved no Halting machine/algorithm exists, but upon closer inspection it is revealed just to be logical magicianry.
What I have been trying to argue for several pages now is that the setup that Turing proposes in his proof is most likely self contradicting. IE one of his assumptions is A does not equal A, thus trivially creating the contradiction that led him to claim that there is no Halting Machine.
That is he claims there is a halting machine that can be part of a composite machine that includes an input copying machine that then feeds its output to the (inverted) halting machine. This machine is then fed itself as input and then expected to retain it's normal function in order for the proof to hold.
That is, despite this machine being fed it's own encoding, it is expected to still return a result of whether or not the input machine would halt on it's input which was also given. However in this situatiton a Halting Machine would uniquely be unable to provide a proper result - instead it would always loop. It doesn't always loop, just went given it's own encoding.
The machine Turing creates for his proof, if it existed, would have a domain that would exclude it's own encoding. Refering to the fact that the encodingn is just 1's and 0's (or colors or anything else) changes nothing. It is an encoding that the machine is designed to recognize as another machine.
The assumption in Turing's proof by contradiction that this machine would continue to function normally outside of it's domain is absurd and the obvious cause of the contradiction he derives. Thus anyone who believes this as a disproof of the existence of a Halting Machine has been had.
At best I can see that if what I claim truly is the source of the contradiction, there probably exists some proof that a Halting machine has to trace the computatitons of the machine encoding it was given as input. However, a proof precludes the possibillity of any alternative, and Turing's argument does not do this.
