A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 20 Oct 2006 17:10 "Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message news:DO3_g.9833$vw1.5754(a)reader1.news.jippii.net... > Peter Olcott wrote: >> 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 > > Too bad for WillHalt, then. The program still either halts or does not halt > given the input. > >> 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!!! > > Yep, it might be that WillHalt could answer "Well, this question is posed so > that I can't possibly answer it correctly", but then it would have to use some > algorithm to decide which program-input pairs constitute ill-formed questions. > What is your proposed algorithm for doing so? In order to make it possible for me to make my point, I must insist that the conversation never digresses to tangents until the prerequisite point is made. I have already shown, and it is completely obvious that there is no possible correct YES or NO answer that WillHalt() can possibly provide. The fact that there is a possible correct YES or NO answer that someone else can provide always draws people's attention from the fact that there is no possible correct YES or NO answer that WillHalt() can possibly provide. From the fact that there is no possible YES or NO answer that WillHalt() can possibly provide, the logical leap is made that WillHalt() must not know the answer because it can not provide the answer. This is stated in the form WillHalt() can not correctly decide whether or not LoopIfHalts(LoopIfHalts) will halt. My point is that this logical leap is an error, it does not logically follow. It might even be possible for WillHalt() to always provide the correct determination regarding whether or not LoopIfHalts(LoopIfHalts) will halt. I will not begin to provide my reasoning on this point until the prerequisite point is first made. > > For example, is the following question ill-formed: > > Does the program P halt with input 0? > > where P is a program executing the following algorithm > > 1. n := 4 > 2. if n isn't a sum of two primes, go into an endless loop if > WillHalt("P",0) returns true and otherwise print "neener-neener" > 3. n := n+2 > 4. Go to step 2 > > What is the algorithm WillHalt uses to determine whether this is an ill-formed > question or not? > > -- > Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) > > "Wovon man nicht sprechen kann, daruber muss man schweigen" > - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Peter Olcott on 20 Oct 2006 17:12 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:ehajpt$p5k$1(a)f1node01.rhrz.uni-bonn.de... > Peter Olcott schrieb: > >> It does get the right answer!!! It simply can not provide the results of its >> correct and complete decision to a caller that toggles the result of this >> return value. I will say it again, most everyone have missed this point: IT >> DOES GET THE RIGHT ANSWER!!! > How do check for this? Do you just search for the string "WillHalt" with > needed parameters? It can do a simulated execution trace using the SourceCode for LoopIfHalts(), and its own SourceCode, if needed.
From: sillybanter on 20 Oct 2006 17:16 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message > news:ehab9n01r9b(a)drn.newsguy.com... > > Aatu Koskensilta says... > >> > >>Jack Campin - bogus address wrote: > >>> "Peter Olcott" <NoSpam(a)SeeScreen.com> wrote: > >>>> if (MalignantSelfReference(SourceCode, InputData)) > >>> > >>> This isn't code, it's wishful thinking. You haven't proved that > >>> any such function as MalignantSelfReference can exist, you haven't > >>> programmed it, and you haven't proved that it always returns a value. > >>> > >>> For that matter you haven't even *specified* it. > >> > >>He has said something to the effect that a program contains "malignant > >>self-reference" if it has a call to Halt with its own source as an argument. > > > > I seem to remember an article from long ago in which Peter suggested > > that tight computer security could be used to solve the halting > > problem. The idea is that you keep the source code for Halt secret, > > so that nobody can ever use it to generate a logical contradiction. > > > > -- > > Daryl McCullough > > Ithaca, NY > That entire line-or-reasoning had been correctly refuted by a PhD > computer science professor calling themselves NewToMe. The > line-of-reasoning that I am providing now is the only possible > line-of-reasoning that could work within the categorically complete > enumeration of every possible line-of-reasoning that could ever > possibly exist. Actually, that's "NewsToMe" (Usenet News - get it?). I know that, because that was me -- I've just changed ISPs and posting names now... -- Steve Stringer sillybanter(a)gmail.com
From: Jens Auer on 20 Oct 2006 17:18 Peter Olcott schrieb: > I have already said this quite a few times in the ANALYTICAL COMMENTARY. Why > don't you point out the precise point within the exact phrase of this ANALYTICAL > COMMENTARY that you either fail to understand, or disagree with. > > WillHalt() performs the same sort of simulated execution trace that a human > would use to unequivocally determine that it WILL indeed HALT. From this same > sort of simulated execution trace it can obviously see (in the same way that a > person can see) that providing this decision back to its caller is corrupted by > its caller to change the result of the decision. So, you can obviously see if a program terminates on any input? This is great, I can't and if I need to show it, I have to prove it by hand (or with the help of some semi-automated verification tool), but this is not as simple as looking at it. > Because it can see this (in the same way that a person can see this), it can > determine (in the same way that a person can determine) that even though it > knows full well that it will halt, (thus is not undecidable) it can not provide > this result back to its caller without the result becoming corrupted by the > caller. > // 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. So, if I get this correctly (without a precise in terms of source code definition of MalignantSelfReference() this is more guessing than reasoning.), WillHalt checks the source code it is given as argument whether it is called somewhere, and the result is used to form the contradiction. By this, you hope to avoid the constructed counter-example. But what do you do if I feed in the source code of LoopIfHalts, where I replaced the call to WillHalt with another function (as a source code entity, not a mathematical function) which has the same behaviour (in computational terms, both program compute the same function)? Can your magic function MalignantSelfReference() detect this? Still, I would like to see a definition of MalignantSelfReference, even as pseudo-code or as a mathematical definition for the set of programs it decides. This would ease talking very much.
From: Peter Olcott on 20 Oct 2006 17:21
"Patricia Shanahan" <pats(a)acm.org> wrote in message news:gHa_g.12168$Y24.4097(a)newsread4.news.pas.earthlink.net... > Peter Olcott wrote: >> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >> news:87y7rbmum0.fsf(a)bsb.me.uk... >>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>> >>>> 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. >>> You have not been able to say exactly when a question is ill-formed, >> >> I have said this many times here it is again. >> >> // >> // To make the problem more clear we are assuming >> // that function call syntax results in inline expansion, >> // thus specifying the name of a function specifies the >> // text body of the function. >> // >> >> 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. >> >> > > In order to define a function you need to state the domain and > co-domain, and a rule determining which element of the co-domain is > associated with each element of the domain. > > All you have told us about MalignantSelfReference is a single element of > its domain, and that it is true for that element. From its use in an > if-test, I assume it is a Boolean function, a function whose co-domain > is a set containing some representation of "true" and "false", but I > have not yet been told about any element of its domain for which it is > false. > > If its domain really only contained one element, then it could be > defined by telling us the value for that element. However, that would > make it inappropriate for the way it is being used in WillHalt. > > Without a definition, other than a single domain-range pair, for > MalignantSelfReference, the source code is useless for defining your > WillHalt. > > Patricia It simply sees the same obvious things in this specific example that a person can see. At this point this function is only intended to work for this one single example. It is completely obvious to anyone with much compsci background that WillHalt() can not possible provide a correct YES or NO answer within this example. All that MalignantSelfReference(SourceCode, InputData) does is make this same obvious determination for this single isolated example. |