A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 19 Oct 2006 17:34 "Alan Smaill" <smaill(a)SPAMinf.ed.ac.uk> wrote in message news:fwebqo8cw0i.fsf(a)collins.inf.ed.ac.uk... > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> "Alan Smaill" <smaill(a)SPAMinf.ed.ac.uk> wrote in message >> news:fwehcy01tf7.fsf(a)collins.inf.ed.ac.uk... >>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > ... >>>> I am using the sort of model that the link provides as my basis, >>>> rather than the >>>> formal mathematical model. >>>> >>>> int WillHalt(string SourceCode, string InputData) { >>>> if (MalignantSelfReference(SourceCode, InputData)) >>>> throw(MALIGNANT_SELF_REFERENCE); >>>> if ( TheProgramWillHalt(SourceCode, InputData) ) >>>> return TRUE; >>>> else >>>> return FALSE; >>>> } >>>> >>>> This defeats the "problem" aspect of the Halting Problem. >>> >>> You have simply ignored my question. >>> Yes, you can tackle what problems you want and call them what >>> you want from your own piont of view. >>> >>> Yet again, do you agree that in standard usage in computer science, >>> the terminology "Halting Problem" uses "problem" in the same way >>> as in the terminology "Travelling Salesman Problem"? This is a specific example of one of the tangents that I don't want to go off on. I can not adequately answer this question without spending more time than I have to spend. >>> >>> This is a small enough point which for some reason you >>> seem determined to ignore. >>> >>> -- >>> Alan Smaill >> >> In order for me to cause comprehension to occur, I must insist on making one >> point at a time, and not allow the process to go off on any tangents. > > You will I hope allow that comprehension involves the person > you are addressing as well as the person trying to get ideas across. > > I cannot comprehend why you want to avoid answering a simple > yes or no to my question. Your answer would help me to see where > you are coming from, either way. > > Evidently, you will not answer. > > > -- > Alan Smaill
From: Peter Olcott on 19 Oct 2006 17:40 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh7tad028sc(a)drn.newsguy.com... > Peter Olcott says... > >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote > > >>> You are assuming that there is a program >>> MalignantSelfReference(SourceCode, InputData) >>> which will return true if executing that >>> particular source code on that input data >>> results in a "malignant self reference". >>> >>> But then determining whether something involves >>> "malignant self reference" is, in fact, >>> equivalent to solving the halting problem. > >>I am assuming nothing. I have shown step by step point by point, >>item by item, exactly and precisely how such a program could be >>constructed within the precise focus of this specific example. > > What you have described is perhaps a way to detect *explicit* > self-reference. However, given any computer program, there are > infinitely many programs that do the exact same thing, but have > different source codes. It is not possible to detect that > two programs are, in fact, equivalent programs. > > In light of that, consider your proposed solution. > > 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? Only after you answer this point will I proceed with even the slightest trace of any steps beyond this point, or any other points besides this point. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 19 Oct 2006 17:44 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh7u0r02aiu(a)drn.newsguy.com... > Peter Olcott says... > >>>>int WillHalt(string SourceCode, string InputData) { >>>> if (MalignantSelfReference(SourceCode, InputData)) >>>> throw(MALIGNANT_SELF_REFERENCE); >>>> if ( TheProgramWillHalt(SourceCode, InputData) ) >>>> return TRUE; >>>> else >>>> return FALSE; >>>>} >>> >>> You are assuming that there is a program >>> MalignantSelfReference(SourceCode, InputData) >>> which will return true if executing that >>> particular source code on that input data >>> results in a "malignant self reference". > >>I am assuming nothing. > > 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 !!! Please stay completely focused on the specific example that I have provided, and do not proceed to any other points besides or beyond this sharply focused point. Every other point is 100% completely and totally moot, unless and until we can get past this first single point. > > Once again, you have your program > WillHalt(string SourceCode, string InputData). > > Now, let Q(p,x) be a function that has exactly > the same behavior as WillHalt, but completely > different source code. Let f(x) be the following > function > > f(String x) { > if (Q(x,x)) { > loop(); > } > } > > Let #f be the source code for f, and consider the computation > > WillHalt(#f,#f) > > On what basis will WillHalt throw a Malignant Self Reference > Exception? Step through the computation of > MalignantSelfReference(#f,#f), and show how it decides > whether to return true or not. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 19 Oct 2006 17:47 <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. // // 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. > > That can certainly be confusing, but if you don't understand that then > consider it like this: Take the putative Halt procedure and everywhere > you see "Halt" just replace that with the name "CopyOfHalt". Now you > have something completely equivalent, and you can call "CopyOfHalt" in > the "LoopIfHalts" function. There is no requirement in the halting > problem proof that CopyOfHalt be recursive (or that it not be > recursive for that matter). And CopyOfHalt certainly can't call > "LoopIfHalts" or the original "Halt" function, so there's no chance of > indirect recursion there either. So now we have something that > clearly doesn't have to be recursive in any shape or form, and yet the > proof of the halting problem still works out. > > How does that affect your belief that somehow "infinite recursion" is > involved? > > -- > > Steve Stringer > sillybanter(a)gmail.com >
From: Peter Olcott on 19 Oct 2006 17:50
<sillybanter(a)gmail.com> wrote in message news:SrLZg.5348$NK5.2906(a)trnddc08... > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > >> That seems to be a very precise English language statement that is >> most typically used to describe the results of the HP. It is this >> statement that I refute. I may be wrong, I have been wrong before, >> but, it is still this specific statement that I refute. The HP can >> be decided, yet the answer can not be restricted to YES or NO >> because the question is not a YES or NO question. > > There are certainly problems that are ill-formed, but the halting > problem is not one of those. Deal with the real form of the halting 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. Iff (if and only if) I can reach a consensus on this point, I will proceed to a UTM version of the same problem, and attempt to show the mathematical mapping from the prior example to the UTM example. I will not do this unless or until I have reached a consensus on my prior point. > problem for a minute - don't try to change the model or anything. Now > consider the following statement: > > Given a TM (or a program in any TM-equivalent language, if you > prefer) and an input, when the TM is run with the input it either > halts in a finite number of steps or it doesn't. > > Do you somehow disagree with that? I'm not sure how you could - that > seems to partition the space of possibilities quite nicely. Either > something happens or it doesn't. Yes or no. Completely well formed. > *You* may not know for a particular program/input whether the answer > is yes or no, so you might want to add a third choice "I dont' know", > but that's a different question - and doesn't negate the fact that > there *is* a yes or a no answer. > > -- > > Steve Stringer > sillybanter(a)gmail.com > |