A Possible "solution" to the Halting Problem
in [Theory]
|
From: sillybanter on 21 Oct 2006 11:58 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > <sillybanter(a)gmail.com> wrote in message news:oF5_g.21$A27.19(a)trnddc08... > > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> <sillybanter(a)gmail.com> wrote in message news:TDYZg.3794$4T6.1422(a)trnddc02... > >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> >> > >> >> <sillybanter(a)gmail.com> wrote in message > >> >> news:bnLZg.5347$NK5.1822(a)trnddc08... > >> >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> >> > > >> >> >> So the equivalent of the return value of the Halt() function from > >> >> >> the TM is the integer value that the TM's ReadWrite head rests on > >> >> >> when the TM halts. In this case DOES_NOT_HALT=0 HALTS=1 > >> >> >> MALIGNANT_SELF_REFERENCE=2. This scenario breaks out of the infinite > >> >> >> recursion of the original specification of the problem, and provides > >> >> >> the only possible correct answer. > >> >> > > >> >> > In the standard presentation of the halting problem, there is no > >> >> > recursion, infinite or otherwise. Don't be confused by the fact that > >> >> > the same name of a function is used in the analyzed program and in the > >> >> > analyzer - it's not the same thing, and these two instances of > >> >> > "Halt" are completely separate. > >> >> > >> >> See the ANALYTICAL COMMENTARY of this example mentioned below to see my > >> >> current > >> >> point. > >> > > >> >> ... > >> > > >> >> // ANALYTICAL COMMENTARY > >> >> WillHalt() is provided with the source code of LoopIfHalts(), as > >> >> input, so WillHalt() can see exactly how the return value of the > >> >> invocation of itself under test will be used to toggle the result > >> >> of the analysis of the invocation of itself under test. WillHalt() > >> >> can see that LoopIfHalts() is toggling the result of the invocation > >> >> of itself under test to invalidate the analysis of the invocation > >> >> of itself under test. > >> >> > >> >> Therefore WillHalt() can determine that the question: > >> >> "Does LoopIfHalts(LoopIfHalts) halt?" has no correct YES or NO > >> >> answer, and is thus erroneously formed because it is asking a > >> >> YES or NO question that has no correct YES or NO answer. > >> > > >> > Except that it, of course, DOES have a correct YES or NO answer. > > > >> So which of the correct YES or NO answers can WillHalt() provide > >> such that it has provided the correct YES or NO answer? If you are > >> correct, then you MUST be able to correctly select one of these, > >> otherwise YOU ARE INCORRECT!!! THERE EXISTS NO CORRECT YES OR NO > >> ANSWER THAT WillHalt() CAN POSSIBLY PROVIDE, THUS THIS HALTING > >> PROBLEM IS MERELY THE CASE OF THE INABILITY TO CORRECTLY ANSWER AN > >> ILL-FORMED QUESTION ENTIRELY DUE TO THE FACT THAT THE QUESTION > >> ITSELF IS ILL-FORMED!!! > > > > If you really think about what you yourself just wrote there, you > > would see that you've exactly described the contradiction that is the > > heart of the halting problem proof, and hence you have proved that the > > halting problem is undecidable. > Right there is the error. This reasoning has not shown that the HP > is undecidable. There is a subtle but crucial distinction between > deciding the correct answer to a question, and providing a correct > answer to a question. It is very possible to provide a correct > answer without knowing it (guessing is possible), and it is also > possible to know the correct answer without providing it. Then it hasn't "decided" the answer in the C.S. sense of the term. In this area, "decided" means that you have provided the correct answer. They are completely synonymous. To use your definition of "decided" you'd have to impart some notion of consciousness on the deciding TM so that it could say "I *know* the answer, but I'm not telling you." And I can guarantee you that if you defined that notion (deciding but not telling) in a rigourous and unambiguous way that the halting problem would *still* be undecidable (by your new notion of decidability). As for "providing the correct answer without knowing it" that is completely irrelevant. First off, TMs don't "know" anything at all, so that's a nonsense statement. But even so, I don't care *how* the answer is arrived at -- if you follow a consistent set of rules (an algorithm) to get to the answer, it's unimportant whether you call that a "decision" or a "guess" or a "shot in the dark" or an "intuitive notion". You still can't know/decide/guess/intuit the correct answer to the halting problem, for all inputs, by any algorithm. > There is nothing at all that prevents WillHalt() from deciding the > correct answer. Well, of course there is. That's why it gives (or decides) the wrong answer. -- Steve Stringer sillybanter(a)gmail.com
From: The Ghost In The Machine on 21 Oct 2006 11:52 In sci.logic, Aatu Koskensilta <aatu.koskensilta(a)xortec.fi> wrote on Sat, 21 Oct 2006 18:20:44 +0300 <cVq_g.10769$iN5.6874(a)reader1.news.jippii.net>: > Peter Olcott wrote: >> "Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message >> news:ZOp_g.10712$545.1166(a)reader1.news.jippii.net... >>> Peter Olcott wrote: >>>> So can you see how this equally applies to the UTM versions of the HP? >>> What are "the UTM versions of HP"? >> >> Universal Turing Machine version of the Halting Problem. > > I figured as much. What is "Universal Turing Machine version of the > Halting Problem"? > This is hopefully a variant of Alan Turing's original paper On computable numbers, with an application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, 42 (1936), pp 230-265. http://en.wikipedia.org/wiki/Halting_problem, reference #1. -- #191, ewill3(a)earthlink.net Useless C++ Programming Idea #104392: for(int i = 0; i < 1000000; i++) sleep(0); -- Posted via a free Usenet account from http://www.teranews.com
From: sillybanter on 21 Oct 2006 12:01 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message > news:ehbnrq02gnk(a)drn.newsguy.com... > > Peter Olcott says... > > > >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote: > > > >>>>So you agree that my example shows that within the specific context of this > >>>>example I have shown that this specific form of a Halting Problem is merely > >>>>the ill-formed question of: "Does LoopIfHalts(LoopIfHalts) halt?" > >>> > >>> That's not an ill-formed question. It is a perfectly good question, and it > >>> has a perfectly good answer: Yes, it halts (by throwing an exception). > >> > >>Yes you can see that the program halts, AND WillHalt() can also SEE that the > >>program halts. > > > > Then why did you call it an ill-formed question? You are contradicting > > yourself. > It is analogous to insisting on a verbal answer from a mute > person. It is not that the mute has not correctly determining the > answer. It's also not that the answer doesn't exist or that the problem is ill-formed, which is what you have concluded for some reason. If I take away all accepting states in a TM then it is rendered mute. Does that mean any problem that could be posed to this TM is now ill-formed because this particular TM can't give the right answer? -- Steve Stringer sillybanter(a)gmail.com
From: Daryl McCullough on 21 Oct 2006 11:45 Peter Olcott says... >Did you read the post by the IBM research scientist that agreed with >me before making this shallow assessment? That's another hallmark of the crackpot: He ignores the dozens of experts who say that he is wrong, but if a single expert says something that can be interpreted as providing the slightest support for the crackpot's claims, then that's the expert he pays attention to. R. Sriniva did not say that he agreed with your argument. He admitted that he hadn't studied it in detail. What he agreed with was the conclusion. He is by far in the minority here. An actual researcher, as opposed to a crackpot like you, knows that what is important in scientific research is getting the arguments correct. Getting the right answer for a bogus reason is worth nothing. -- Daryl McCullough Ithaca, NY
From: sillybanter on 21 Oct 2006 12:12
In comp.theory Patricia Shanahan <pats(a)acm.org> wrote: > If you take the existence of a decision algorithm for the Halting > problem as an axiom, while retaining the normal axioms that ultimately > underly theory of computation, you end up with an inconsistent system of > axioms. Even then, it is the set of axioms that is broken, not the > fundamental concept of truth. Not to confuse the mainline discussion going on in this thread, but I wanted to point out that if you're careful about how you do this then you don't get an inconsistent system. For example, you can add an "oracle" the the TM model where the oracle can decide the halting problem. Now it is sensible to ask what can be decided in this augmented, more powerful model of computation. The answer is that there are still problems that are undecidable. So what if you add an oracle for some of *these* problems to the model? Well, now you can decide more, but still not everything. You can keep doing this an unbounded number of times to get progressively larger sets of "decidable" languages, but you'll never have a model powerful enough to be able to decide everything (that's pretty clear if you consider that the number of "programs", even in a very powerful augmented model, is still countable, and the number of possible decision problems is uncountable). There's actually a nice theory of all of this, looking at what are called "recursively enumerable degrees," and the separation proofs within this hierarchy (something called "finite injury proofs" if I remember the term correctly) are some of the most beautiful computer science/math that I've seen. I was fortunate enough in grad school to be able to take a couple of courses on this with one of the people who invented a lot of it back in the 60's and 70's... If you take these RE degrees and replace "decidable problems" with "decidable in polynomial time" then you pretty much get the polynomial time hierarchy (where "recursively enumerable" corresponds roughly to "NP"). At one point in my life I thought that the great theory behind RE degrees could be translated into proofs regarding the polynomial time hierarchy and the P vs NP question, but it turns out that there are some fairly fundamental problems when it comes to translating the proofs... -- Steve Stringer sillybanter(a)gmail.com |