A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 21 Oct 2006 18:00 <sillybanter(a)gmail.com> wrote in message news:obw_g.1640$hK.1002(a)trnddc02... > 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. Not within the context of the single isolated example of LoopIfHalts() and WillHalt() that I provided. Within this context this example of a HP clearly shows that it is the specific requirement of a Boolean return value that causes the whole "problem". I think that this might be able to be generalized to the UTM version of the HP, but, this generalization will have to wait until the current point is conceded one way or the other. > >> > 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 >
From: Patricia Shanahan on 21 Oct 2006 18:11 Peter Olcott wrote: .... > We can precisely define what is meant by an ill-formed question by saying that > an ill-formed question is any question that has no possible correct answer from > the required solution set. The variation of the HP that your example refers to > has no correct YES or NO answer, thus derives an ill-formed question equivalent > to the question: "How tall are you red or blue?" Do you think your "Ill formed statement" condition is computable? Patricia
From: Peter Olcott on 21 Oct 2006 18:21 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:yWw_g.10604$Lv3.9258(a)newsread1.news.pas.earthlink.net... > Peter Olcott wrote: > ... >> We can precisely define what is meant by an ill-formed question by saying >> that an ill-formed question is any question that has no possible correct >> answer from the required solution set. The variation of the HP that your >> example refers to has no correct YES or NO answer, thus derives an ill-formed >> question equivalent to the question: "How tall are you red or blue?" > > Do you think your "Ill formed statement" condition is computable? > > Patricia If we make the usual assumptions that are made in the HP, then yes. If we assume that an algorithm is capable of correctly determining whether or not another program halts, at least in each and every case where this is possible, then this same algorithm would by definition already know the ill-formed cases. The ill-formed cases would be any case where it can neither conclude HALTS, nor conclude NOT_HALTS.
From: Patricia Shanahan on 21 Oct 2006 18:31 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message > news:yWw_g.10604$Lv3.9258(a)newsread1.news.pas.earthlink.net... >> Peter Olcott wrote: >> ... >>> We can precisely define what is meant by an ill-formed question by saying >>> that an ill-formed question is any question that has no possible correct >>> answer from the required solution set. The variation of the HP that your >>> example refers to has no correct YES or NO answer, thus derives an ill-formed >>> question equivalent to the question: "How tall are you red or blue?" >> Do you think your "Ill formed statement" condition is computable? >> >> Patricia > > If we make the usual assumptions that are made in the HP, then yes. If we assume > that an algorithm is capable of correctly determining whether or not another > program halts, at least in each and every case where this is possible, then this > same algorithm would by definition already know the ill-formed cases. The > ill-formed cases would be any case where it can neither conclude HALTS, nor > conclude NOT_HALTS. I do NOT "assume that an algorithm is capable of correctly determining whether or not another program halts", whether or not qualified by "at least in every case in which this is possible". It is certainly not an assumption that is usually made in discussing the halting problem, other than in the sense that some versions of the proof use a proof by contradiction form, in which the prover temporarily assumes something exists, demonstrates a contradiction, and concludes it does not exist. Can you discuss the question without introducing arbitrary, and highly controversial, assumptions? Patricia
From: Peter Olcott on 21 Oct 2006 18:40
"Patricia Shanahan" <pats(a)acm.org> wrote in message news:4dx_g.17125$UG4.12313(a)newsread2.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message >> news:yWw_g.10604$Lv3.9258(a)newsread1.news.pas.earthlink.net... >>> Peter Olcott wrote: >>> ... >>>> We can precisely define what is meant by an ill-formed question by saying >>>> that an ill-formed question is any question that has no possible correct >>>> answer from the required solution set. The variation of the HP that your >>>> example refers to has no correct YES or NO answer, thus derives an >>>> ill-formed question equivalent to the question: "How tall are you red or >>>> blue?" >>> Do you think your "Ill formed statement" condition is computable? >>> >>> Patricia >> >> If we make the usual assumptions that are made in the HP, then yes. If we >> assume that an algorithm is capable of correctly determining whether or not >> another program halts, at least in each and every case where this is >> possible, then this same algorithm would by definition already know the >> ill-formed cases. The ill-formed cases would be any case where it can neither >> conclude HALTS, nor conclude NOT_HALTS. > > I do NOT "assume that an algorithm is capable of correctly determining > whether or not another program halts", whether or not qualified by "at > least in every case in which this is possible". > > It is certainly not an assumption that is usually made in discussing the > halting problem, other than in the sense that some versions of the proof > use a proof by contradiction form, in which the prover temporarily > assumes something exists, demonstrates a contradiction, and concludes it > does not exist. Yes that is it. > > Can you discuss the question without introducing arbitrary, and highly > controversial, assumptions? > > Patricia |