A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 19 Oct 2006 08:14 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:ueDZg.11396$Y24.6326(a)newsread4.news.pas.earthlink.net... > Peter Olcott wrote: > ... >> I can do as others have done and complicate the problem beyond all possible >> recognition. Instead I chose to boil the problem down to its most fundamental >> essence. Try to address the problem as I have framed it, and refrain from >> attempts to change this framework. The ability to complicate the example so >> that no one can understand it, is not a valid form of refutation. >> >> Within the exact and precise framework that I have defined the Halting >> Problem, is it now clear, that at least within the context of this framework >> 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. > ... > > If you are defining your own problem, you can solve it any way you like, > but please don't call it "the Halting Problem" unless you really do mean > a decision procedure for the set of terminating Turing machine computations. > >> Maybe it might help if you don't begin your response starting with the goal >> of refutation? > > It would not help at all with testing the validity of your ideas, which > is my objective. > > If you are trying to test a program, do you feed it only the easy cases, > or do you feed it deliberately difficult cases, such as the largest and > smallest permitted inputs? > > Patricia 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?" 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. If you agree with this please say so, if you don't agree with this then please explain why you do not agree. Apparently you do not agree that this example of a Halting Problem mathematically maps tot he original Halting Problem. I will proceed to this step only after we have formed agreement on the preceding step. Effective communication must proceed one step at a time, or it does not work effectively.
From: Peter Olcott on 19 Oct 2006 08:16 "Jack Campin - bogus address" <bogus(a)purr.demon.co.uk> wrote in message news:bogus-A85378.10550219102006(a)news.news.demon.net... >>>> The Halting Problem too, is merely an ill-formed question, nothing more, >>>> and nothing less. >>> How do you deal with the fact that the halting problem for some kinds of >>> computation *is* solvable? That's what complexity analysis is about. >>> Any time you make a database query, it will have gone through an optimizer >>> that solves the halting problem for the database query language (and does >>> considerably more than that). There is nothing at all ill-formed about >>> asking how long it will take to get an answer. >>> This works because database query languages can't do as much as Turing >>> machines or unbounded-memory abstract machines programmed in C can. Read >>> a book and you might see what the relevant difference is. >> >> +-----------------------+ >> | | >> V | >> (What is the answer to this quesion?)--+ >> >> What is it about the about above question that make it unsolvable? > > That's a pretty boring question. The difference between database query > languages and Turing machines is interesting, important, and *written > up in books* which you would be better occupied reading than flinging > around defensive bullshit like this. > > What's stopping you from reading about computability? I have read about it. In order to make my point effectively I must boil the original problem down to its most fundamental essence and achieve agreement on this point, and the and only then proceed to show that this simplified version mathematically maps to the original. Now can you please answer the original question, that it is boring is merely evasive. > > ============== j-c ====== @ ====== purr . demon . co . uk ============== > Jack Campin: 11 Third St, Newtongrange EH22 4PU, Scotland | tel 0131 660 4760 > <http://www.purr.demon.co.uk/jack/> for CD-ROMs and free | fax 0870 0554 975 > stuff: Scottish music, food intolerance, & Mac logic fonts | mob 07800 739 557
From: Peter Olcott on 19 Oct 2006 08:29 "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: > >> "Alan Smaill" <smaill(a)SPAMinf.ed.ac.uk> wrote in message >> news:fwepscp1xz4.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:fwezmbu0xdj.fsf(a)collins.inf.ed.ac.uk... >>>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>> >>>>>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>>>>> Are you saying that the root cause of the "Problem" aspect of the >>>>>> "Halting Problem" has nothing to do with self-reference? >>>>> >>>>> The "problem" nomenclature is just the same as is used in >>>>> the Travelling Salesman Problem. >>>>> >>>>> en.wikipedia.org/wiki/Traveling_salesman_problem >>>>> >>>>> The halting problem, just as with the TSP, is well-posed and unambiguous. >>>>> >>>>> -- >>>>> Alan Smaill >>>> >>>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>>> None-the-less it is this mode that I am using in my investigation. I >>>> understand Turing Machines, and UTM's, both of these would mathematically >>>> map to this alternative model. >>> >>> You can do what you want in your own work, obviously. >>> >>> What is the relevance of the link you just cited to my observation >>> about the normal use in computer science? >>> In that link, the word "problem" is used as I suggested. >>> >>> >>> -- >>> Alan Smaill >> >> 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 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. Please analyze the ANALYTICAL COMMENTARY mentioned below, as it applies within the specific context of this single example. Whether or not this example mathematically maps to the UTM form of the Halting Problem or any other form of the HP will only be addressed after this example has been fully addressed. 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. If you don't agree with this, then please point out every step and every detail that you do not agree with. Please do not change the subject to anything at all outside of the scope of this specifically focused example. Whether or not this form of a halting problem mathematically maps to any other form will only be addressed after this example has been fully explored.
From: Peter Olcott on 19 Oct 2006 08:36 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh6qcm02r5d(a)drn.newsguy.com... > Peter Olcott says... > >>It is not that difficult really. I will explain how an ill-formed question can >>be determined in terms of the example below. See the end of the example for >>the >>analytical commentary. >> >>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; >>} > > 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. > > -- > Daryl McCullough > Ithaca, NY > 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. Please restrict all discussion to this specific example, and do not raise any issue pertaining to whether or not this example of a halting problem mathematically maps to any other form of a HP. these will be addressed at a later late, provided that we reach agreement on this example. If we do not reach agreement on this example all these other points become moot. 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: Alan Smaill on 19 Oct 2006 08:47
"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 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 |