A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 21 Oct 2006 12:40 "Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message news: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"? > > -- > Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) > > "Wovon man nicht sprechen kann, daruber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus Essentially the original problem as posed by Alan Turing
From: Peter Olcott on 21 Oct 2006 12:42 <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). > > -- > > Steve Stringer > sillybanter(a)gmail.com > Then you would be in a good position to evaluate my current position, here it is: // // To make the problem more clear we are assuming // that function call syntax results in inline expansion, // thus specifying the name of a function specifies the // text body of the function. // void LoopIfHalts(string SourceCode) { if ( WillHalt(SourceCode, SourceCode) == TRUE ) while (TRUE) // loop forever ; else return; } int WillHalt(string SourceCode, string InputData) { if (MalignantSelfReference(SourceCode, InputData)) throw(MALIGNANT_SELF_REFERENCE); if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } LoopIfHalts(LoopIfHalts); // 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.
From: Peter Olcott on 21 Oct 2006 12:46 <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. > 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. > 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. See my above commentary. > > -- > > Steve Stringer > sillybanter(a)gmail.com >
From: Peter Olcott on 21 Oct 2006 12:56 <sillybanter(a)gmail.com> wrote in message news:Evr_g.8574$A27.6297(a)trnddc08... > 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? The problem with this isolated example of a Halting Problem is that it requires the artificially contrivance of restricting the form of the output to a Boolean true or false. Although it is deeply rooted in common sense that all programs must either halt or fail to halt, within the specific context of this isolated example, the question posed to WillHalt() becomes ill-formed. > > -- > > Steve Stringer > sillybanter(a)gmail.com >
From: Daryl McCullough on 21 Oct 2006 13:52
>>> > 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 |