A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 19 Oct 2006 18:34 Peter Olcott says... >"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> You want to have a program willHalt(p,x) with three >> possible outcomes: >> >> (1) If program p halts on input x, then willHalt returns true. >> (2) If program p does not halt on input x, then willHalt returns false. >> (3) If program p makes a self-referential call on willHalt, then willHalt >> throws an exception. >> >> Okay, so now let Q(p,x) be some other program with two inputs. >> Let F(x) be a program with the following behavior: >> >> if Q(x,x) returns true, then loop forever, >> if Q(x,x) returns false, then halt. >> >> Now, let's run willHalt(F,F). How does willHalt decide whether >> to throw a "MalignantSelfReferenceException"? > >Would you agree that I have shown, that in the specific instance of >a halting problem that I have provided, that in this specific case, >the "problem" is merely that the question: "Does LoopIfHalts(LoopIfHalts) >halt?" is of the ill-form of requiring a YES or >NO answer to a question that has no correct YES or NO answer? No, I don't agree with that, at all. It is a perfectly well-formed question to ask whether LoopIfHalts(LoopIfHalts) halts. The fact that WillHalt can't correct answer the question doesn't make the question ill-formed. It *is* a yes-no question. It has a yes-no answer. The way that you have defined LoopIfHalts, it *does* halt (by throwing an exception). -- Daryl McCullough Ithaca, NY
From: Peter Olcott on 19 Oct 2006 18:53 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh8tt501jne(a)drn.newsguy.com... > Peter Olcott says... > >>> Whether it is a valid solution depends on the definition of >>> MALIGNANT_SELF_REFERENCE. If it is just equivalent to the I_GIVE_UP >>> exception, then always throwing it is valid but pointless. >> >>It is equivalent to saying that no correct answer exists to the question, "How >>tall are you green or blue?" because the question itself is ill-formed. It is >>not at all equivalent to I_GIVE_UP. > > On the contrary, there is nothing ill-formed about the question: > > Does the program LoopIfHalts halt when it is fed its own source > code as input. There is nothing ill-formed about this question until one adds the specific context of the LoopIfHalts() program. Thenn (then and only then) the question become ill-formed. There are many questions that are not ill-formed until adding a specific context. > > It's a perfectly sensible question to ask, and your program WillHalt > fails to give a correct answer. Instead, your program raises an > exception. It gives up, rather than answering the question. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 19 Oct 2006 18:55 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh8u3001k82(a)drn.newsguy.com... > Peter Olcott says... > >>I think that I have shown in my prior response to you at least one example of >>a >>halting problem, that is only a problem because it is ill formed. > > No, you did not. There is nothing ill formed about the question: > > Does LoopIfHalts halt when given its own source code as an input? > > Your program WillHalt fails to answer that question, but there is nothing > ill formed about the question. > >>Iff (if and only if) I can reach a consensus on this point > > Your point is false. There is nothing ill-formed about the question. When we add the context that the program always changes the result of any answer that is provided, thenn, the quesion become ill-formed. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 19 Oct 2006 20:58 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh8u9q01kru(a)drn.newsguy.com... > Peter Olcott says... >> >> >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote > >>> Yes, you are. You are assuming that >>> MalignantSelfReference(SourceCode,InputData) >>> can detect whether there is a "malignant self >>> reference". There is no such program. >> >>I provided the detailed steps of the design of such a program >>for this specific instance of a halting problem TWICE !!! > > You described a MalignantSelfReference detector that works > by checking if LoopIfHalts makes calls to WillHalt. > If instead LoopIfHalts uses a program that is different from, > but has the same behavior as WillHalt, then your detector > will not work. > > -- > Daryl McCullough > Ithaca, NY > So then you admit that I have solved a halting problem, yet do not accept that this solution can be generalized to all halting problems?
From: Peter Olcott on 19 Oct 2006 21:32
"Charlie-Boo" <shymathguy(a)gmail.com> wrote in message news:1161286660.787506.128520(a)i42g2000cwa.googlegroups.com... > Peter Olcott wrote: >> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >> news:1161210790.800534.60930(a)h48g2000cwc.googlegroups.com... >> > Peter Olcott wrote: >> >> What is the >> >> official precise English language conclusion drawn from the results of the >> >> mathematical analysis of the Halting Problem? >> > >> > Why not start by at least informing yourself of an exact mathematical >> > statement of the theorem and its proof? >> > >> > MoeBlee >> > >> >> That is not within my purpose. My purpose is to show that the Halting Problem >> is >> really nothing more than an ill-formed question. > > Ill-formed in what sense? The problem is that it is inconsistent - > regarding whether a program that runs the program being specified > against its input as both program and input, when run against itself > halts or not. Inconsistent in the sense of the ANALYTICAL COMMENTARY mentioned below // // 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. > > Results from Mathematical Logic manifest themselves in common > programming activities. In this case, it is just a case where the > programmer sends the specs back to the applications specialist for > fixing due to bad logic in the spec. > > (I know people don't like the idea that the HP is simply an example of > bad specs, but it's true. There is an inconsistency in the spec when > you put all of its aspects together. You simply have to look at it as > a scientist, rather than becoming emotional and defensive about it.) > > C-B > |