A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 18 Oct 2006 22:45 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:IUAZg.9011$Lv3.6307(a)newsread1.news.pas.earthlink.net... > Peter Olcott wrote: > ... >> What it boils down to is this, (at least within the scope of the HP) it is >> not that there exists some problems too difficult to be solved by >> computation, it is merely the case that some ill-formed questions have no >> correct answer. > > I might agree with that formulation if you presented an algorithm for > deciding if something is an ill-formed question. I've asked for it often > enough, without result, that by now I'm convinced you do not have any > algorithm for identifying what you call an ill-formed question, or > distinguishing them from questions you consider well-formed. > > I'm not surprised, because I strongly suspect that even if you defined > what you consider to be an ill-formed question, deciding the set of > ill-formed questions would still be halting-problem equivalent, and > cannot depend on the existence of an ill-formed question decider. > > How are we supposed to avoid asking ill-formed questions, or to find out > that we have asked one, without an algorithm for deciding if a question > is ill-formed? > > Patricia > It is not that difficult really. I will explain how an ill-formed question can be determined in terms of the example below. See the end of the example for the analytical commentary. 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 an erroneously formed because it is asking a YES or NO question that has no correct YES or NO answer. If you don't agree with this, then please point out every step and every detail that you do not agree with.
From: Peter Olcott on 18 Oct 2006 22:54 "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. > Whatever else goes in informal discussion about that theorem, you at > least do recognize that the above is a description of a theorem (and > that there's nothing such as an "ill formed question") in the proof of > such mathematical theorems, right? > > MoeBlee > 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.
From: Peter Olcott on 18 Oct 2006 22:56 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh6m7g02hkl(a)drn.newsguy.com... > Peter Olcott says... > >>What it boils down to is this, (at least within the scope of the HP) >>it is not that there exists some problems too difficult to be solved >>by computation, it is merely the case that some ill-formed questions >>have no correct answer. > > I'm afraid to ask, but what is ill-formed about the question: > I already answered this question to another respondent. > Does polynomial equation P have any positive integer solutions? > > The halting problem is provably equivalent to that problem. > > For example, the polynomial equation > > x^2 + y^2 = z^2 > > has infinitely many integer solutions, for example x=3, y=4, z=5. > In contrast, the equation > > x^3 + y^3 = z^3 > > has no positive integer solutions. > > It would be nice if we had a computer program that whenever it > is given a polynomial equation, returns "true" if the equation > has integer solutions, and returns "false" if it does not. What > is ill-formed about the question "Does this polynomial equation > have any positive integer solutions?" > > Well, it is provably the case that there is no deterministic > computer program that can solve this problem. This problem > is provably equivalent to the halting problem. > > -- > Daryl McCullough > Ithaca, NY >
From: Daryl McCullough on 18 Oct 2006 22:55 Peter Olcott says... >What it boils down to is this, (at least within the scope of the HP) >it is not that there exists some problems too difficult to be solved >by computation, it is merely the case that some ill-formed questions >have no correct answer. Here's another question that is provably equivalent to the halting problem. Let's define a little game with symbols. A term is something formed from the symbols S and K according to the following rules: S is a term. K is a term. If x and y are expressions, then so is (x y). Now, we give the following "rewrite rules" on terms: 1. If x, y, and z are any terms, then (((S x) y) z) can be rewritten as ((x z) (y z)). 2. If x and y are any terms, then ((K x) y) can be rewritten as x. For example, if we start with the term (((S K) K) S) we can rewrite it using rule 1 as ((K S) (K S)) then we can rewrite it using rule 2 as S Define a term as being in "normal form" if neither of the above rules apply. For example, the following terms are all in normal form: 1. S 2. K 3. ((S K) K) 4. (K S) Finally, define a term to be "normalizable" if it is possible to convert it (using the rewrite rules) into a term in normal form. It is called "unnormalizable" if you keep on applying the rules without every reaching a normal form. An example of an unnormalizable term is the following: (((S ((S K) K)) ((S K) K)) ((S ((S K) K)) ((S K) K))) So here is a question that is provably unsolvable by any deterministic computer program: There is no computer program which, given any term, will output "true" if that term is normalizable, and "false" if it is not. This is provably equivalent to the halting problem. What is ill-formed about the question of whether a term is normalizable? -- Daryl McCullough Ithaca, NY
From: Patricia Shanahan on 18 Oct 2006 23:21
Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message .... >> How are we supposed to avoid asking ill-formed questions, or to find out >> that we have asked one, without an algorithm for deciding if a question >> is ill-formed? >> >> Patricia >> > > It is not that difficult really. I will explain how an ill-formed question can > be determined in terms of the example below. See the end of the example for the > analytical commentary. > > 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 Not necessarily. It can be provided with the source code of any program that is equivalent to LoopIfHalts in the sense of halting on SoureCode if, and only if, SourceCode itself does so: if ( WillHalt(ObfuscateHorribly(SourceCode),SourceCode) == True ) For example, ObfuscateHorribly may translate SourceCode to Snobol, and wrap it up with a Snobol interpreter. > 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. How does it recognize programs equivalent, but not identical, to itself? Moreover, you need to consider far more complicated LoopIfHalts implementations. The result of the WillHalt test may be run through all sorts of calculations before ultimately controlling a halt or loop decision. The loop can be far subtler. It might, for example, be a search for the largest prime number. > > Therefore WillHalt() can determine that the question: "Does > LoopIfHalts(LoopIfHalts) halt?" has no correct YES or NO answer, and is thus > an erroneously formed because it is asking a YES or NO question that has no > correct YES or NO answer. > > If you don't agree with this, then please point out every step and every detail > that you do not agree with. I've written out a couple of my objections. Essentially, I believe MalignantSelfReference has to perform two very difficult tests: 1. Determine whether two programs, its source code and its first parameter, have the same halting behavior on a given input. 2. Find out whether its result ever affects a loop-or-terminate decision. Patricia |