A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 21 Oct 2006 14:33 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:ehdmpp0147a(a)drn.newsguy.com... >>>> > Peter Olcott says... > >>>> >>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. > > Then why did you call it an ill-formed question? If the mute > person can figure out the answer, then it clearly is not an > ill-formed question. You are contradicting yourself. > > -- > Daryl McCullough > Ithaca, NY > This will be my last reply to you unless you are much more careful in your replies. I am sick of people that glance at a couple of words, and then refute, refute refute. If you were paying the degree of attention that is required to follow what I am saying, the answer to your question is already provided above. It is the fact that the form of the answer from the mute it required to be verbal spoken communication that derives the ill-form of the question to the mute.
From: Patricia Shanahan on 21 Oct 2006 17:18 sillybanter(a)gmail.com wrote: > 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. I can see that you could reason about Turing computation plus a halting oracle, but I would not call a halting oracle "a decision algorithm". I suppose it depends on your attitude to the Church-Turing thesis - can something be an "algorithm" if no Turing machine computes it? Patricia
From: sillybanter on 21 Oct 2006 17:21 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > > <sillybanter(a)gmail.com> wrote in message news:Tsr_g.8573$A27.1777(a)trnddc08... > > 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." > Not really, all that is required is a Boolean memory variable that > is not used as a function call return value. Whether you "return" it or store it in a Boolean variable in memory and then don't return it is completely irrelevant to the halting problem. > > 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). > > The decision is simply stored in a local Boolean memory value, that > is not used as a function call return value. Let me be very specific - and *think* about this before you respond, because you have a habit of ignoring what people are telling you. Let's say you have a function PetersHaltDecision() that does what you say - stores the decision in a boolean variable and doesn't return it. I'll take your function and make StevesHaltDecision() that is an exact copy of yours, except immediately before "returning" it reads the value you stored in your boolean variable and returns that *instead* of whatever it was that PetersHaltDecision returned. StevesHaltDecision() "decides" *exactly* the same way that PetersHaltDecision() does, so StevesHaltDecision() is correct if and only if PetersHaltDecision() is correct in what it stores in its boolean variable. Now I will use StevesHaltDecision() in the standard halting problem proof to show that in fact StevesHaltDecision() does NOT give the right answer for at least one input. Because of the above, PetersHaltDecision() will *also* not give the right answer on that input. It's irrelevant whether PetersHaltDecision() returns its "decision" or not. Now really *think* about that. You seem to believe for some reason that the halting problem issue is a problem with an observer, almost as if this were quantum physics or something. The observer is irrelevant to a deterministic computation like this - similarly, what you do with an answer after you've computed it - return it or store it in a variable - is also irrelevant. -- Steve Stringer sillybanter(a)gmail.com
From: sillybanter on 21 Oct 2006 17:23 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > <sillybanter(a)gmail.com> wrote in message news:%ir_g.8572$A27.4407(a)trnddc08... > > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> <sillybanter(a)gmail.com> wrote in message news:H0b_g.42$rx.8(a)trnddc04... > >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > > > >> > Actually, that's "NewsToMe" (Usenet News - get it?). > >> > > >> > I know that, because that was me -- I've just changed ISPs and posting > >> > names now... > >> > >> So you are the PhD computer science professor that correctly refuted > >> my prior line-of-reasoning? What was the basis for this correct > >> refutation? > > > > Yes, I used to post under "NewsToMe", and yes I do have a PhD in > > Computer Science, and yes I have posted here for a long time (I've > > posted here for around 20 years under various names) and have even > > once spent time leading someone to understanding why their incorrect > > reasoning about the halting problem was incorrect. While I recognize > > your name, I can't swear that this was you earlier, to be honest... > > and I certainly don't remember the details of that exchange (although > > now that I think about it I'm fairly certain it was you - seems like > > we defined "PO machines" or something like that based on your > > initials). > > Then you would be in a good position to evaluate my current > position, here it is: I already have, several times. You've just chosen to ignore it. I've just written something in a different reply to you that is very specific and that you should be able to follow. I'll leave substantive contents in that thread rather than replying here as well. -- Steve Stringer sillybanter(a)gmail.com
From: Daryl McCullough on 21 Oct 2006 17:30
sillybanter(a)gmail.com says... >Let's say you have a function PetersHaltDecision() that does what you >say - stores the decision in a boolean variable and doesn't return it. >I'll take your function and make StevesHaltDecision() that is an exact >copy of yours, except immediately before "returning" it reads the >value you stored in your boolean variable and returns that *instead* >of whatever it was that PetersHaltDecision returned. Peter wants to prevent you from doing that by keeping his algorithm protected. He'll prosecute you if you try to create StevesHaltDecision based on his idea. -- Daryl McCullough Ithaca, NY |