A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 19 Oct 2006 17:57 "Dr A. N. Walker" <anw(a)maths.nott.ac.uk> wrote in message news:eh81a5$p72$1(a)oyez.ccc.nottingham.ac.uk... > In article <KyxZg.28265$eZ4.22514(a)dukeread06>, > Peter Olcott <NoSpam(a)SeeScreen.com> wrote: >>> [...] There is also no need for >>> the HP to refer to programs *at all*; >>Then what would it be that we are attempting to test the halting of? It would >>seem that you must be wrong here. If there are no programs, then there is no >>halting, thus no "Halting Problem" is possible, [...] > > I didn't say "there are no programs", only that the HP doesn't > need to refer to them. Ever since the invention of the "stored program" > concept, we have known that there is no interesting distinction between > "program" and "data". As for "halting", this is merely one particular > state of the computer [and not usually, since the invention of operating > systems, an actual literal "halt", but merely an instruction to the OS > that it is not to return control to this program]. > >>> there is a simple equivalent >>> formulation entirely in terms of data [eg as supplied to a UTM]. >>A UTM is essentially defined as being a program. > > A UTM is essentially a *computer*. Spot the difference. The same sort of difference between a computer language runtime interpreter program, and this exact same thing when it is called the Java virtual machine, there is no actual difference, its all a mere play on words. > >>>> All that the HP shows is that there exists >>>>some cases of malignant self-reference where this determination can not be >>>>provided as a return value to a caller. >>> No, it doesn't show that. No matter how MSR your program may be, >>> there are programs out there that will show whether or not your program >>> with its data will halt. But this is a game of "you show me yours and >>> I'll show you mine". >>Not when the result of this determination is structured as listed below: >> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > > Yes, even so. What that [standard] proof shows is that *if* you > show me your [purported] halt-tester, *then* I can construct a derived > [MSR] program on which your tester fails. I can't write down that code > without seeing the code that claims to be a correct tester, and after I > have written down my buster, all it shows is that your code is incorrect. > The MSR program is not itself hard to analyse -- no harder than your code > on which it is based. *Your* code cannot analyse it, but there is other > code out there that can [but that code in turn is not going to be able to > analyse some inputs]. > > See "http://www.maths.nott.ac.uk/personal/anw/G12FCO/lect18.html" > for perhaps relevant [though now rather old] discussion. [The preceding > lecture discusses UTMs and the standard HP proof, and there are also > relevant snippets in later lectures.] > > It's not MSR-ness of code that makes it hard to analyse, but what > we might loosely call "3x+1" or "Collatz" behaviour -- code with lots of > special cases that never seem to explode to the extent that it's provable > we're losing, but never collapse to a result either, so that it always > seems worthwhile to go on a little longer. > > -- > Andy Walker, School of MathSci., Univ. of Nott'm, UK. > anw(a)maths.nott.ac.uk
From: Peter Olcott on 19 Oct 2006 18:01 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:r1NZg.15912$UG4.2273(a)newsread2.news.pas.earthlink.net... > The Ghost In The Machine wrote: >> In sci.logic, Patricia Shanahan >> <pats(a)acm.org> >> wrote >> on Wed, 18 Oct 2006 22:22:10 GMT >> <mOxZg.15598$UG4.10415(a)newsread2.news.pas.earthlink.net>: >>> Peter Olcott 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. >>> OK, so now we are down to a well-defined environment. Perhaps >>> you can explain how you define a MALIGNANT_SELF_REFERENCE in a Turing >>> machine computation? >>> >>> Patricia >> >> It can always be true, which leads to a Halt() function >> that always throws an exception. This is a valid if >> pointless solution. > > 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. > > To the extent that I've been able to find out its meaning, it seems to > relate to whether the result will be used to control whether the TM > halts or not. That, of course, is a halting problem equivalent test, so > it cannot be implemented. > > Patricia
From: Patricia Shanahan on 19 Oct 2006 18:11 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message > news:r1NZg.15912$UG4.2273(a)newsread2.news.pas.earthlink.net... >> The Ghost In The Machine wrote: >>> In sci.logic, Patricia Shanahan >>> <pats(a)acm.org> >>> wrote >>> on Wed, 18 Oct 2006 22:22:10 GMT >>> <mOxZg.15598$UG4.10415(a)newsread2.news.pas.earthlink.net>: >>>> Peter Olcott 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. >>>> OK, so now we are down to a well-defined environment. Perhaps >>>> you can explain how you define a MALIGNANT_SELF_REFERENCE in a Turing >>>> machine computation? >>>> >>>> Patricia >>> It can always be true, which leads to a Halt() function >>> that always throws an exception. This is a valid if >>> pointless solution. >> 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. There is a very big difference. Whether there is a correct answer to "How tall are you, x or y" depends on whether the set {x,y} includes your height. That is decidable: measure the person in question, look at all elements of {x,y} that represent lengths, and see if any of them match the height. Similarly, whether a division involves division by zero is decidable: Compare the divisor to zero. If it is equal, there is a division by zero. Whether a program uses the result of a given function call to control whether to loop forever or to halt is not decidable. Patricia
From: Peter Olcott on 19 Oct 2006 18:14 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:mJNZg.11568$Y24.3672(a)newsread4.news.pas.earthlink.net... > Peter Olcott wrote: >> "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. > > I strongly disagree with any idea of using the term "halting problem" > for this, because the Halting Problem is a decision problem. It asks > whether its input is, or is not, a member of a specific language, and > the only possible answers are to accept or reject the input. http://www.cprogramming.com/tutorial/computersciencetheory/halting.html 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); My version of a "Halting Problem" is essentially identical to the one on the link, the only difference is that I have added a possible solution. In each of these cases the entire subject matter focuses on the ability to determine whether or not a program halts. This by itself forms a completely sufficient condition to call both of these halting problems. If your issue is that at least one of these does not sufficiently correspond to the original UTM Halting Problem, then your point is off-topic. That topic will be covered as soon as consensus is achieved this halting problem. > > Note that the traditional proof shows that self-contradictory programs > can be created if you assume the set of Turing machine computations that > halt is a decidable language. > > In my opinion, the only reasonable reaction to the LoopIfHalts behavior > is to conclude that there is no decision algorithm for halting TM > computations. Once you accept that, LoopIfHalts cannot be written > because there is no Halts function for it to call. > > Instead of working on the decision problem, you seem to be trying to > construct a function that maps input strings to "Yes", "No", or "MSR". > Whether MSR is the correct output for a specific input depends on > exactly how MSR is defined. I cannot comment on which result is the > right one for a given program until you define your function. > > I strongly suspect your function will be either unrelated to the Halting > problem or not computable, but I won't know which unless you define it. I have defined it at least twice. The problem is that you are assuming that I must define it to work universally, whereas the actual requirements of the problem as I have precisely specified it only require me to show that it works for this single isolated case. Here it is again, for this single isolated case: // 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. > >> >> 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 18:22
"MoeBlee" <jazzmobe(a)hotmail.com> wrote in message news:1161275720.941271.93980(a)h48g2000cwc.googlegroups.com... > Peter Olcott wrote: >> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >> news:1161222967.470438.31270(a)m7g2000cwm.googlegroups.com... >> > Peter Olcott wrote: >> >> it is >> >> merely the case that some ill-formed questions have no correct answer. >> > >> > There is no "ill-formed question" involved in the theorem that, to >> > quote a standard textbook, "there exists a Turing machine whose halting >> > problem is recursively unsolvable." >> > >> >> It is only unsolvable, because it is ill-formed. One could say that all >> ill-formed questions are unsolvable questions, this leaves out a crucial >> detail. >> How tall are you, (blue or green) ? is an unsolvable math problem, more >> importantly it is an ill-formed question. > > There is no question at all in the statement or proof of the theorem. > There are no interrogatives in a fully formalized proof of the halting > theorem. The interrogatives involved are for the purpose of motivating > the mathematics, but are not part of the theorem itself nor its proof. So then you are necessarily saying that the "Halting Problem" must have nothing at all do with whether or not anything at all halts! Someone goofed somewhere here, and it sure does not seem to be me. > Morevover, there is nothing "ill-formed" in the questions. Either a > given Turing machine with an initial state halts or it doesn't, and Whoops didn't that last statement imply a question ??? > regarding any Turing machine with an inititial state we can ask whether > it halts. That was a question for sure, it looks like you just not contradicted yourself! The problem with translating statements between English and mathematical formalisms and back is that things get lost, in the translation, and things get added that were not in the other form. The "Halting Problem" is fundamentally about whether or not a TM halts. This is inherently and fundamentally a question. If the mathematical formalism loses track of this, then the mathematical formalism errs. > >> It matters not whether an ill-formed question is posed in natural language or >> in >> the language of mathematical formalism, in either case it is still an >> ill-formed >> question. > > There are no interrogatives in a fully formalized proof of the > unsolvability of the halting problem. > > MoeBlee > |