A Possible "solution" to the Halting Problem
in [Theory]
|
From: Chris Menzel on 20 Oct 2006 12:11 On Fri, 20 Oct 2006 08:27:32 -0500, Peter Olcott <NoSpam(a)SeeScreen.com> said: > > <sillybanter(a)gmail.com> wrote in message > news:nGYZg.3795$4T6.1868(a)trnddc02... >>> Iff (if and only if) I can reach a consensus on this >>> point, I will proceed to a UTM version of the same problem, and >>> attempt to show the mathematical mapping from the prior example to >>> the UTM example. I will not do this unless or until I have reached a >>> consensus on my prior point. >> >> You will not get consensus on this point, because you're wrong, and >> pretty much everyone here except you sees that quite clearly. > > Or, pretty much everyone here does not 100% completely grasp every > subtle nuance of the complete meaning of my statements. Or not. :-) What are the odds, dude?
From: Chris Menzel on 20 Oct 2006 12:14 On 20 Oct 2006 04:18:15 -0700, Daryl McCullough <stevendaryl3016(a)yahoo.com> said: > 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. Yes, and if only Russell hadn't sent that damned letter to Frege we could still be using Naive Comprehension!
From: Peter Olcott on 20 Oct 2006 16:06 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh7vo302e00(a)drn.newsguy.com... > Peter Olcott says... > >>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?" > > That's not an ill-formed question. It is a perfectly good question, and it > has a perfectly good answer: Yes, it halts (by throwing an exception). Yes you can see that the program halts, AND WillHalt() can also SEE that the program halts. It is not undecidable because both you and WillHalt() can decide this. > > (The semantics of exceptions hasn't been spelled out, but in most normal > programming languages, if a program throws an exception, then the program > stops at that point.) > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 20 Oct 2006 16:09 "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. > and you are very worried about what you see as "malignant > self-reference", but the HP comes in many disguises. > > As a programmer you will be very familiar with context-free grammars. > CFGs are used to describe the syntax of all sorts of programming > languages: a finite set of clauses describe how, starting from an > initial clause, sequences of strings drawn from the grammar's "terminal > alphabet" can be generated. Given the simple alphabet S = {0, 1} this > grammar: > > E -> D E | /\ > D -> 0 | 1 > > has the rather boring property that is can generate all strings of 0s > and 1s. We say the language of the grammar L(E) = S* (the set of all > string made from the symbols in S). I am using /\ to mean the empty > string (since it shows up better) and | to show alternatives in rules. > > The grammar: > > X -> D X | 1 > D -> 0 | 1 > > does not generate all string because every string in L(X) ends with a 1. > > It seems to me a simple and well-formed question to ask of a grammar, > G, if L(G) = S* and, more specifically, to imagine a program > > bool generates_all_binary_strings(grammar g) > { > if (<have a really good look at g and if it does>) > return true; > else return false > } > > This problem is equivalent to the Halting Problem so the The Halting > Theorem tells me that no such program exists, but where is the > ill-formedness of the question and where is the malignancy? > > [Aside. I don't really expect you to be convinced by this. In fact I > expect you to say "since I've solved the HP this one is solvable > too!". But since you have resolutely refused to say what kind of > thing might shake you resolve, I thought I'd try this take -- a > simple, easy to understand problem that is just as "nasty" as the HP.] > > -- > Ben.
From: Peter Olcott on 20 Oct 2006 16:23
"Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:eh9v3q$lhs$1(a)f1node01.rhrz.uni-bonn.de... > Peter Olcott schrieb: >> // 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. > Would you be so kind and show us how WillHalt accomplishes this, in a more > precise form than a verbal comment? It all comes down to you definition of > MalignantSelfReference, which I believe is itself undecidable. 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. 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. // // 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. |