A Possible "solution" to the Halting Problem
in [Theory]
|
From: george on 22 Oct 2006 13:43 Peter Olcott wrote: > >> >> Right there is the error. This reasoning has not shown that the HP > >> >> is undecidable. Yes, it has. >> > >> There is a subtle but crucial distinction between > >> >> deciding the correct answer to a question, and providing a correct > >> >> answer to a question. Not for TMs there isn't. You don't get to decide how you want things to be here, nor do you get to apply common sense from natural language. A TM is what WE say it is and it does what WE say it does. And we say that the answer comes from what is on the tape when you halt. In particular, as you seem to be WRONGLY assuming is possible, "the answer" does NOT come from WHAT STATE you are in right before you halt (or when you halt, if multiple halt-states are possible). > > >>> It is very possible to provide a correct > >> >> answer without knowing it (guessing is possible), Not for a TM it isn't. > >> >> and it is also > >> >> possible to know the correct answer without providing it. We didn't define ANYthing as "knowing" on the part of a TM. So, therefore, it is never possible for any TM to know anything, period. Therefore it is not possible for any TM to know anything without "providing" it. EVERYthing that EVERY TM "does", it does AT THE SAME TIME, ALL THE TIME. TMs do NOT exist IN TIME. TMs are ABSTRACT objects. They are not like physical running programs. They ARE like source CODE for programs. A piece OF CODE that correctly solves a problem cannot be said to "know the correct answer without providing it". The code provides the correct answer, regardless of whether anybody ever runs it or not. > >> > > >> > To use your definition of "decided" > >> > you'd have to impart some notion of consciousness on the deciding TM > >> > so that it could say "I *know* the answer, but I'm not telling you." > > > >> Not really, all that is required is a Boolean memory variable that > >> is not used as a function call return value. YES, REALLY, dumbass. What you are saying is that the TM knows something depending on what state it is in. But that is simply not the case. That does not constiute TM-knowing. NOTHING constitutes TM-knowing. TMs ARE ABSTRACT. THEY DON'T know or do. They just ARE. > > Whether you "return" it or store it in a Boolean variable in memory > > and then don't return it is completely irrelevant to the halting > > problem. If that's true, then it makes YOU look stupid. If you are in a given state, you can always go back to the beginning and print that state on the tape. So this difference is not even important, except insofar as it proves that you don't understand what a TM is. > > Let's say you have a function PetersHaltDecision() that does what you > > say - stores the decision in a boolean variable and doesn't return it. > > I'll take your function and make StevesHaltDecision() that is an exact > > copy of yours, except immediately before "returning" it reads the > > value you stored in your boolean variable and returns that *instead* > > of whatever it was that PetersHaltDecision returned. > > > > StevesHaltDecision() "decides" *exactly* the same way that > > PetersHaltDecision() does, so StevesHaltDecision() is correct if and > > only if PetersHaltDecision() is correct in what it stores in its > > boolean variable. > > > > Now I will use StevesHaltDecision() in the standard halting problem > > proof to show that in fact StevesHaltDecision() does NOT give the > > right answer for at least one input. Because of the above, > > PetersHaltDecision() will *also* not give the right answer on that > > input. It's irrelevant whether PetersHaltDecision() returns its > > "decision" or not. > > > > Actually that scenario occurred to me last night, after I remembered that this > was the scenario that correctly refuted my alternative line-of-reasoning. YAY! News-flash: Crank admits he was wrong about something. What next, 333 days of PENANCE for inflicting 333 messages worth of BULLSHIT on the world at large?!?
From: Peter Olcott on 22 Oct 2006 14:13 <sillybanter(a)gmail.com> wrote in message news:7_N_g.10502$A27.8602(a)trnddc08... > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> <sillybanter(a)gmail.com> wrote in message news:obw_g.1640$hK.1002(a)trnddc02... >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> >> >> <sillybanter(a)gmail.com> wrote in message >> >> news:Tsr_g.8573$A27.1777(a)trnddc08... >> >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> >> <sillybanter(a)gmail.com> wrote in message >> >> >> news:oF5_g.21$A27.19(a)trnddc08... >> >> >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> >> >> <sillybanter(a)gmail.com> wrote in message >> >> >> >> news:TDYZg.3794$4T6.1422(a)trnddc02... >> >> >> >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> >> >> >> >> >> >> >> >> <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. >> >> >> >> > >> >> >> >> >> ... >> >> >> >> > >> >> >> >> >> // 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. >> >> >> >> > >> >> >> >> > Except that it, of course, DOES have a correct YES or NO answer. >> >> >> > >> >> >> >> So which of the correct YES or NO answers can WillHalt() provide >> >> >> >> such that it has provided the correct YES or NO answer? If you are >> >> >> >> correct, then you MUST be able to correctly select one of these, >> >> >> >> otherwise YOU ARE INCORRECT!!! THERE EXISTS NO CORRECT YES OR NO >> >> >> >> ANSWER THAT WillHalt() CAN POSSIBLY PROVIDE, THUS THIS HALTING >> >> >> >> PROBLEM IS MERELY THE CASE OF THE INABILITY TO CORRECTLY ANSWER AN >> >> >> >> ILL-FORMED QUESTION ENTIRELY DUE TO THE FACT THAT THE QUESTION >> >> >> >> ITSELF IS ILL-FORMED!!! >> >> >> > >> >> >> > If you really think about what you yourself just wrote there, you >> >> >> > would see that you've exactly described the contradiction that is the >> >> >> > heart of the halting problem proof, and hence you have proved that >> >> >> > the >> >> >> > halting problem is undecidable. >> >> > >> >> >> Right there is the error. This reasoning has not shown that the HP >> >> >> is undecidable. There is a subtle but crucial distinction between >> >> >> deciding the correct answer to a question, and providing a correct >> >> >> answer to a question. It is very possible to provide a correct >> >> >> answer without knowing it (guessing is possible), and it is also >> >> >> possible to know the correct answer without providing it. >> >> > >> >> > Then it hasn't "decided" the answer in the C.S. sense of the term. In >> >> > this area, "decided" means that you have provided the correct answer. >> >> > They are completely synonymous. To use your definition of "decided" >> >> > you'd have to impart some notion of consciousness on the deciding TM >> >> > so that it could say "I *know* the answer, but I'm not telling you." >> > >> >> Not really, all that is required is a Boolean memory variable that >> >> is not used as a function call return value. >> > >> > Whether you "return" it or store it in a Boolean variable in memory >> > and then don't return it is completely irrelevant to the halting >> > problem. >> >> Not within the context of the single isolated example of >> LoopIfHalts() and WillHalt() that I provided. Within this context >> this example of a HP clearly shows that it is the specific >> requirement of a Boolean return value that causes the whole >> "problem". I think that this might be able to be generalized to the >> UTM version of the HP, but, this generalization will have to wait >> until the current point is conceded one way or the other. > > That's only a problem with the way that this proof constructs a > specific input instance on which WillHalt fails. The deeper logic of > the proof (beyond the superficial characteristic of which input) > doesn't depend on a "return value" at all. > >> >> > And I can guarantee you that if you defined that notion (deciding but >> >> > not telling) in a rigourous and unambiguous way that the halting >> >> > problem would *still* be undecidable (by your new notion of >> >> > decidability). >> >> >> >> The decision is simply stored in a local Boolean memory value, that >> >> is not used as a function call return value. >> >
From: Jens Auer on 22 Oct 2006 14:44 Peter Olcott wrote: > 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. > (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. > > 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. I first assume that your Halt function, implementing the three conditions exists. Now, take your usual example source code (the one with the famous analytical comment), together with a function WillHalt' (in the sense of source code function) that behaves equivalent to WillHalt, but has a different source code. Now form a new function LoopIfHalts2 by replacing the call the WillHalt with WillHalt'. For this function, Halt cannot determine that LoopIfHalts2 is constructed to fool itself (unless you solve program equivalence), so only condition 1 and 2 can hold. But for these conditions, we formed the usual contradiction, so this Halt function cannot exist. > My special interest is the KR branch of AI. If I can successfully commercialize > my current patent, I intend to pursue this as commercial research. Although I > have little formal training in KR, I have such great interest in it that I have > thought through some aspects of it. One of the aspects that I have thought > through is that one of the prerequisites to fully achieving KR will logically > entail some mechanism by which KR can be specified with 100% complete precision, > without the slightest trace of any ambiguity of any kind what-so-ever. This would be better discussed in another thread, but what is wrong with logics with regard to expression precision? It is mathematically precisely defined what a logical expression means, and when it is true or not. There are other points to challenge, but precision is not one of them (IMHO). > > If one were to take your last statement within the context of this implied > English as a mathematical formalism approach, one would find that you erred. The > answer was required to be of the form of a choice between two colors AND it was > also required to be a numerical quantity, thus not red, would not form a correct > answer. In order to get what I am saying, what I am saying is required to be > taken as if English was a mathematical formalism. My point (if I have one) is > expressed only within the subtleties of very slight nuances of meaning. Your question "How tall are you, red or not red?" does not say anything about a numerical quantity as an answer, but gives only a choice between two values. "How tall are you" in natural language surely implies a metric value, but if you do not add this prerequisite to your question, either directly or in the form of background knowledge, you cannot make this assumption.
From: Peter Olcott on 22 Oct 2006 14:53 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:453bbc0e(a)news.ish.de... > Peter Olcott wrote: >> 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. >> (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. >> >> 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. > I first assume that your Halt function, implementing the three conditions > exists. Now, take your usual example source code (the one with the famous > analytical comment), together with a function WillHalt' (in the sense of > source code function) that behaves equivalent to WillHalt, but has a different > source code. Now form a new function LoopIfHalts2 by replacing the call the > WillHalt with WillHalt'. > For this function, Halt cannot determine that LoopIfHalts2 is constructed to > fool itself (unless you solve program equivalence), so only condition 1 and 2 > can hold. But for these conditions, we formed the usual contradiction, so this > Halt function cannot exist. I can't see what you mean, can you make this concrete by changing to functions below to reflect exactly what you are saying? 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)) return MALIGNANT_SELF_REFERENCE; if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } LoopIfHalts(LoopIfHalts); > >> My special interest is the KR branch of AI. If I can successfully >> commercialize my current patent, I intend to pursue this as commercial >> research. Although I have little formal training in KR, I have such great >> interest in it that I have thought through some aspects of it. One of the >> aspects that I have thought through is that one of the prerequisites to fully >> achieving KR will logically entail some mechanism by which KR can be >> specified with 100% complete precision, without the slightest trace of any >> ambiguity of any kind what-so-ever. > This would be better discussed in another thread, but what is wrong with > logics with regard to expression precision? It is mathematically precisely > defined what a logical expression means, and when it is true or not. There are > other points to challenge, but precision is not one of them (IMHO). >> >> If one were to take your last statement within the context of this implied >> English as a mathematical formalism approach, one would find that you erred. >> The answer was required to be of the form of a choice between two colors AND >> it was also required to be a numerical quantity, thus not red, would not form >> a correct answer. In order to get what I am saying, what I am saying is >> required to be taken as if English was a mathematical formalism. My point (if >> I have one) is expressed only within the subtleties of very slight nuances of >> meaning. > Your question "How tall are you, red or not red?" does not say anything about > a numerical quantity as an answer, but gives only a choice between two values. > "How tall are you" in natural language surely implies a metric value, but if > you do not add this prerequisite to your question, either directly or in the > form of background knowledge, you cannot make this assumption.
From: Jens Auer on 22 Oct 2006 15:05
Peter Olcott wrote: > "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message > news:453bbc0e(a)news.ish.de... >> Peter Olcott wrote: >>> 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. >>> (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. >>> >>> 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. >> I first assume that your Halt function, implementing the three conditions >> exists. Now, take your usual example source code (the one with the famous >> analytical comment), together with a function WillHalt' (in the sense of >> source code function) that behaves equivalent to WillHalt, but has a different >> source code. Now form a new function LoopIfHalts2 by replacing the call the >> WillHalt with WillHalt'. >> For this function, Halt cannot determine that LoopIfHalts2 is constructed to >> fool itself (unless you solve program equivalence), so only condition 1 and 2 >> can hold. But for these conditions, we formed the usual contradiction, so this >> Halt function cannot exist. > > I can't see what you mean, can you make this concrete by changing to functions > below to reflect exactly what you are saying? > > 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)) > return MALIGNANT_SELF_REFERENCE; > if ( TheProgramWillHalt(SourceCode, InputData) ) > return TRUE; > else > return FALSE; > } > > LoopIfHalts(LoopIfHalts); I first assume that WillHalt exists and works. I derive a new function WillHalt' from WillHalt. This function behaves exactly like WillHalt, but has different source code, e.g. int WillHalt'(string SourceCode, string InputData) { int i = 1; if (MalignantSelfReference(SourceCode, InputData)) return MALIGNANT_SELF_REFERENCE; if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } Actually, the real implementation doesn't matter. There are infinitely many of them, and some don't even look similar. I now construct LoopIfHalts2: void LoopIfHalts2(string SourceCode) { if (WillHalt'(SourceCode, SourceCode) == TRUE) while (TRUE); else return; } If I feed this function LoopIfHalts2 to your WillHalt function, it results in a contradiction: 1) MalignantSelfReference fails because there is no reference to WillHalt in LoopIfHalts2. Of course, WillHalt and WillHalt' compute equivalent functions, but his is undecidable in general (Check out Rice's theorem). 2) If WillHalt decides that LoopIfHalt2 halt, than it goes directly into the endless loop => contradiction 3) If WillHalt decides that LoopIfHalt2 does not halt, it immediately returns => contradiction So, our assumption that WillHalt exists has lead us to contradictions, so they must be false. |