A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 23 Oct 2006 16:24 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:ehj6330284t(a)drn.newsguy.com... > Peter Olcott says... > >>The question posed to the TM is: "Does the program halt { State(HALTS) or >>State(NOT_HALTS) }?" > > No, the question is just "Does program P halt on input X?". If you > are the one who is writing WillHalt, you get to decide what it means > for WillHalt to have figured out that the answer is "yes", and you > get to decide what it means for WillHalt to have figured out that > the answer is "no". > > -- > Daryl McCullough > Ithaca, NY > There is a crucial distinction that it seems you are letting slip through. If I am the one writing WillHalt() and WillHalt() is to meet this original specification, then "no" is prohibited, all that I am permitted is either "yes" or Not("yes"). I am not permitted "no". This is equivalent to entering the State(HALTS) or refraining from entering this state. It is not equivalent to entering the State(NOT_HALTS).
From: sillybanter on 23 Oct 2006 17:20 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > <sillybanter(a)gmail.com> wrote in message news:7_N_g.10502$A27.8602(a)trnddc08... > My purpose is not to solve the Halting Problem. My purpose (at most) is to show > that the conclusion of the HP is incorrect. Within this context I have > determined three possible halt decision outcomes: > (1) The Halt() function can determine that the program subject to test will > halt, and can return this value. > (2) The Halt() function can determine that the program subject to test will > halt, yet can not return this value. Hogwash - if it can determine that the program will halt, it can certainly say "yes" as an answer to the halting problem. Did someone confiscate all the 1 bits so it can't say this? > (3) The Halt() function can determine that the program subject to > test is constructed such that it can not be determined whether or > not the program under test will halt because the question regarding > the halting status of the program under test is > ill-formed. Ill-formed is taken to mean that no correct solutions > exist within the required solution set. Again wrong - the answer is "yes" or "no". If this particular Halt() function can't determine the answer that just means that it can't give the right answer for this input. Being wrong doesn't mean that the answer doesn't exist. If I asked you how tall I am, and you can't answer because you don't know the answer, does that make the question ill-formed? Of course not, it just makes you wrong (or at best, you have to resort to guessing...). > If you can provide a concrete example of a HP proof that does not > fall into one of these categories, please do. Try to do it in the > form of WillHalt() / LoopIfHalts() if you can. Well, you've missed the obvious case of "Halt() can determine that the program subject to test does not halt" but I'll assume that was a simple oversight on your part. Your option (2) is clearly a non-existent case. And option (3) is meaningless - while option (3) could exist if defined as "Halt() can't determine the answer", that has no bearing on whether the problem is ill-formed or not. -- Steve Stringer sillybanter(a)gmail.com
From: Peter Olcott on 23 Oct 2006 17:42 <sillybanter(a)gmail.com> wrote in message news:Nma%g.4818$bb.2921(a)trnddc03... > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> <sillybanter(a)gmail.com> wrote in message >> news:7_N_g.10502$A27.8602(a)trnddc08... >> My purpose is not to solve the Halting Problem. My purpose (at most) is to >> show >> that the conclusion of the HP is incorrect. Within this context I have >> determined three possible halt decision outcomes: >> (1) The Halt() function can determine that the program subject to test will >> halt, and can return this value. >> (2) The Halt() function can determine that the program subject to test will >> halt, yet can not return this value. > > Hogwash - if it can determine that the program will halt, it can > certainly say "yes" as an answer to the halting problem. Did someone > confiscate all the 1 bits so it can't say this? > >> (3) The Halt() function can determine that the program subject to >> test is constructed such that it can not be determined whether or >> not the program under test will halt because the question regarding >> the halting status of the program under test is >> ill-formed. Ill-formed is taken to mean that no correct solutions >> exist within the required solution set. > > Again wrong - the answer is "yes" or "no". If this particular Halt() > function can't determine the answer that just means that it can't give > the right answer for this input. Being wrong doesn't mean that the > answer doesn't exist. If I asked you how tall I am, and you can't > answer because you don't know the answer, does that make the question > ill-formed? Of course not, it just makes you wrong (or at best, you > have to resort to guessing...). > >> If you can provide a concrete example of a HP proof that does not >> fall into one of these categories, please do. Try to do it in the >> form of WillHalt() / LoopIfHalts() if you can. > > Well, you've missed the obvious case of "Halt() can determine that the > program subject to test does not halt" but I'll assume that was a > simple oversight on your part. > > Your option (2) is clearly a non-existent case. And option (3) is > meaningless - while option (3) could exist if defined as "Halt() can't > determine the answer", that has no bearing on whether the problem is > ill-formed or not. > > -- > > Steve Stringer > sillybanter(a)gmail.com > I have updated my position to clarify it and correct any inconsistencies. My updated position is as follows: The question posed to the TM is: "Does the program halt { State(HALTS) or State(NOT_HALTS) }?" is an ill-formed question because the TM is constrained to provide its response from a solution set that contains no correct answer. Thus the Halting Problem meets the definition of an ill-formed question. The Halting Problem is only undecidable because it has the same form as the question" "How tall are you green or blue?"
From: Jack Campin - bogus address on 23 Oct 2006 18:23 > The question posed to the TM is: "Does the program halt { State(HALTS) > or State(NOT_HALTS) }?" The question is does the program halt or not. Adding uninterpreted pseudo-C verbiage doesn't clarify anything. > is an ill-formed question because the TM is constrained to provide its > response from a solution set that contains no correct answer. The correct answer is "yes" if it halts and "no" if it doesn't. I suspect the basic reason Peter is so confused is that he hasn't even seen the possibility of the kind of reasoning Turing and his successors were investigating (and showing the limits of) - i.e. *static* analysis of program code used to predict *dynamic* behaviour. Peter seems to think you have to simulate all the loops in a program before you can tell if it terminates or not. Turing (like any present-day programming language implementor) knew you could often do better than that, and estimate the running time of a program by looking at its textual or graph-theoretic structure, for some simple kinds of program. The next question was, can you do so much better as to solve *all* such problems with one piece of pre-packaged software? It didn't take long to work out that you can't. ============== 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: Jens Auer on 23 Oct 2006 13:57
Peter Olcott wrote: > I have updated my position to clarify it and correct any inconsistencies. My > updated position is as follows: > > The question posed to the TM is: "Does the program halt { State(HALTS) or > State(NOT_HALTS) }?" > > is an ill-formed question because the TM is constrained to provide its response > from a solution set that contains no correct answer. Thus the Halting Problem > meets the definition of an ill-formed question. The Halting Problem is only > undecidable because it has the same form as the question" "How tall are you > green or blue?" Am I the only one that has seen that sentence many times before? This is no update, it is restating your prior postings. What other halting property can a program have except that it halts or doesn't? And since the halting problem is a decision problem, every decision function must be compuatble and yield either yes or no on all possible inputs. If it doesn't, it might be a nice and very useful function, but it is not, and will never be by definition, a decision function. The characteristic function for the halting problem (the set of all pairs (p,x) for which p(x) halts) certainly exists and is well defined since each program is either part of the set or not, but the function cannot be expressed by a TM. |