A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 18 Oct 2006 23:11 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
From: Peter Olcott on 19 Oct 2006 00:10 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:LaCZg.9137$Lv3.7949(a)newsread1.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message > ... >>> How are we supposed to avoid asking ill-formed questions, or to find out >>> that we have asked one, without an algorithm for deciding if a question >>> is ill-formed? >>> >>> Patricia >>> >> >> 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; >> } >> >> >> LoopIfHalts(LoopIfHalts); >> >> // ANALYTICAL COMMENTARY >> WillHalt() is provided with the source code of LoopIfHalts(), as input, so > > Not necessarily. It can be provided with the source code of any program > that is equivalent to LoopIfHalts in the sense of halting on SoureCode > if, and only if, SourceCode itself does so: > > if ( WillHalt(ObfuscateHorribly(SourceCode),SourceCode) == True ) > > For example, ObfuscateHorribly may translate SourceCode to Snobol, and > wrap it up with a Snobol interpreter. > > >> 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. > > How does it recognize programs equivalent, but not identical, to itself? > > Moreover, you need to consider far more complicated LoopIfHalts > implementations. The result of the WillHalt test may be run through all > sorts of calculations before ultimately controlling a halt or loop decision. 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. > > The loop can be far subtler. It might, for example, be a search for the > largest prime number. > >> >> Therefore WillHalt() can determine that the question: "Does >> LoopIfHalts(LoopIfHalts) halt?" has no correct YES or NO answer, and is >> thus an 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. > > I've written out a couple of my objections. Essentially, I believe > MalignantSelfReference has to perform two very difficult tests: Not in the form of the fundamental essence that I have framed it. In the precise form that I framed the problem it becomes obviously clear that asking 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 do not see this, within the specific context of this precisely defined framework, what point is it that you disagree with? > > 1. Determine whether two programs, its source code and its first parameter, > have the same halting behavior on a given input. > > 2. Find out whether its result ever affects a loop-or-terminate decision. > > Patricia Maybe it might help if you don't begin your response starting with the goal of refutation?
From: Patricia Shanahan on 19 Oct 2006 00:33 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
From: Jack Campin - bogus address on 19 Oct 2006 05:55 >>> 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? ============== 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: Alan Smaill on 19 Oct 2006 06:39
"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 |