A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 22 Oct 2006 07:50 "The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message news:c6br04-m5f.ln1(a)sirius.tg00suus7038.net... > In sci.logic, Peter Olcott > <NoSpam(a)SeeScreen.com> > wrote > on Sat, 21 Oct 2006 21:32:49 -0500 > <mLA_g.31731$eZ4.18940(a)dukeread06>: >> >> "R. Srinivasan" <sradhakr(a)in.ibm.com> wrote in message >> news:1161472471.337655.301150(a)f16g2000cwb.googlegroups.com... >>> >>> >>> On Oct 21, 8:45 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: >>>> Peter Olcott says... >>>> >>>> >Did you read the post by the IBM research scientist that agreed with >>>> >me before making this shallow assessment?That's another hallmark of the >>>> >crackpot: He ignores the dozens >>>> of experts who say that he is wrong, but if a single expert says >>>> something that can be interpreted as providing the slightest >>>> support for the crackpot's claims, then that's the expert he >>>> pays attention to. >>>> >>>> R. Sriniva did not say that he agreed with your argument. He >>>> admitted that he hadn't studied it in detail. What he agreed >>>> with was the conclusion. He is by far in the minority here. >>>> >>> >>> Let me clarify the NAFL position. Undecidability of the halting problem >>> means that there must exist at least one instance that is undecidable, >>> which would contradict the NAFL truth definition. Hence each instance >>> of the halting problem is decidable in NAFL, but it is not possible to >>> express that all instances of the halting problem are decidable. This >> >> So it seems that our conclusions are the same, even if the means to derive >> these >> conclusions might differ. I think that I might have derived a means to show >> that >> at least one, and perhaps all of the prior proofs of the Halting Problem form >> conclusions that are less than completely correct. >> >> I have been able to form a little more rigor in this conclusion, probably >> still >> short of the standards of academia. My hypothesis is that at least one, and >> perhaps all of the prior proofs of the Halting Problem are ill formed in a >> specific way. At least one, and perhaps all of these proofs can be construed >> as >> requiring an answer from a solution set, whereas none of the elements in this >> solution set forms a correct answer. >> >> I boil this does into simpler language in that these proofs require a YES or >> NO >> answer to a question that has no correct YES or NO answer. > > And why is that? > > Granted, the Halting Problem is an impractical beast anyway; the > algorithm > > double[] bubblesort(double a[]) > { > double[] b = new double[a.length]; > for(int i = 0; i < b.length; i++) > { > for(int j = i+1; j < b.length; j++) > { > if(b[i] > b[j]) > { > swap(b[i],b[j]); > } > } > } > > return b; > } > > will always halt but is O(N^2) and therefore impractical for large a[]. > > The algorithm > > void traverse(tree * p, void (*visitor)(tree *)) > { > if(p != null) > { > (*visitor)(p); > traverse(p->left, visitor); > traverse(p->right, visitor); > } > } > > may not halt if the tree is misconstructed, but is a useful method > for recursively traversing binary trees. > > I've already given you some examples of other algorithms > which may or may not halt (such as finding the first even > number > 2 that isn't the sum of two primes); we simply > don't know. However, they're reasonably well-implemented. There is a crucial distinction between examples where halting can not be shown to exist, and examples where halting can be shown to not exist, I am only dealing with the latter. > > I for one don't see how the Halting Problem is > ill-construed. Given an algorithm A and an input B[], > does A(B[]) halt? Within the specific context of the single isolated example that I provided, I have shown an example of a halting problem, where the whole problem exists and is constructed from the requirement of a YES or NO answer to a question that has no possible, YES or NO answer. I have further recently defined the concept of an ill-formed question as the case of any question that limits its answers to a specific solution set, whereas no possible correct answer exists within this solution set. Another example of an ill-formed question that meets this definition is the question: "How tall are you blue or green?" Iff (if and only if) you can see that I have shown for the isolated example that I provided, that, I have shown this example of a halting problem to be nothing more than an ill-formed question, thenn (then and only then) I will proceed to show the generalization of this analysis to other halting problems. The next one that I will deal with is the UTM version. > > Formalization of this notion is what led Alan Turing to the tape > machine which eventually got branded with his moniker. > > [rest snipped] > > -- > #191, ewill3(a)earthlink.net > Windows. Because it's not a question of if. > It's a question of when. > > -- > Posted via a free Usenet account from http://www.teranews.com >
From: Peter Olcott on 22 Oct 2006 07:56 "R. Srinivasan" <sradhakr(a)in.ibm.com> wrote in message news:1161502481.271266.156700(a)b28g2000cwb.googlegroups.com... > > Peter Olcott wrote: >> "R. Srinivasan" <sradhakr(a)in.ibm.com> wrote in message >> news:1161472471.337655.301150(a)f16g2000cwb.googlegroups.com... >> > >> > >> > On Oct 21, 8:45 pm, stevendaryl3...(a)yahoo.com (Daryl McCullough) wrote: >> >> Peter Olcott says... >> >> >> >> >Did you read the post by the IBM research scientist that agreed with >> >> >me before making this shallow assessment? > >> >> That's another hallmark of the >> >> crackpot: He ignores the dozens >> >> of experts who say that he is wrong, but if a single expert says >> >> something that can be interpreted as providing the slightest >> >> support for the crackpot's claims, then that's the expert he >> >> pays attention to. >> >> >> >> R. Sriniva did not say that he agreed with your argument. He >> >> admitted that he hadn't studied it in detail. What he agreed >> >> with was the conclusion. He is by far in the minority here. >> >> >> > >> > Let me clarify the NAFL position. Undecidability of the halting problem >> > means that there must exist at least one instance that is undecidable, >> > which would contradict the NAFL truth definition. Hence each instance >> > of the halting problem is decidable in NAFL, but it is not possible to >> > express that all instances of the halting problem are decidable. This >> >> So it seems that our conclusions are the same, even if the means to derive >> these >> conclusions might differ. I think that I might have derived a means to show >> that >> at least one, and perhaps all of the prior proofs of the Halting Problem form >> conclusions that are less than completely correct. >> >> I have been able to form a little more rigor in this conclusion, probably >> still >> short of the standards of academia. My hypothesis is that at least one, and >> perhaps all of the prior proofs of the Halting Problem are ill formed in a >> specific way. At least one, and perhaps all of these proofs can be construed >> as >> requiring an answer from a solution set, whereas none of the elements in this >> solution set forms a correct answer. >> >> I boil this does into simpler language in that these proofs require a YES or >> NO >> answer to a question that has no correct YES or NO answer. >> > > Let me assure you that you are not the only one who has looked at > Turing's proof and felt uneasy about it, in particular, the > self-reference involved. When you disagree with self-reference and > doubt whether a particular proposition within classical theories has a > determinate truth value, you are in the territory of those who question > classical logic itself, in this case, classical infinitary reasoning. > > The hypothesis that you mention, namely, *all* proofs of the > undecidablity of the halting problem are ill formed in a specific way, > is precisely what I am also saying, except that I have moved to another > logic to arrive at this conclusion. I am asserting that the general > principles that you would need to maintain your hypothesis are > precisely those formulated in NAFL. In particular, what is unacceptable > is quantification over infinite entities. E.g. if a TM is considered as > an infinite object in the sense that george mentioned, namely that it > has an infinite tape, then there is no "all" for TMs from the point of > view of NAFL, nor is there an "arbitrary" TM. i.e., you cannot > formulate propositons that explicitly mention "all" TMs or "any" TM -- > this is what I mean by saying that quantification over infinite objects > is objectionable. The self-referential propositions of the type that > you question may come in many different guises in many different proofs > (e.g. of Godel's and Turing's theorems), but I claim that they all have > a common feature -- to formalize these self-referential propositions > (say, by encoding them into Peano Arithmetic, i.e., make them > equivalent to arithmetical propositions) you would need to quantify > over infinite entities in some step of the formalization. If you accept > this step, there would be no way for you to find any explicit > self-reference in at least some of the existing proofs and classical > logicians will defend themselves by invoking these proofs and thereby > *justifying* the self-reference in the proof that you are objecting to. > > In a philosophical sense, quantification over infinite entitites is > arguably a self-referential operation unless you concede some form of > Platonism, i.e., these infnite entities are "pre-existing" in some > Platonic world. This is what NAFL rejects. > So then the proof that one thing is possible or impossible that requires the assumption of one or more things that are impossible (the infinite tape) is not well-formed because it takes as its a part of its foundation a premise that must remain false.
From: Peter Olcott on 22 Oct 2006 08:02 "Stephen Harris" <cyberguard-1048(a)yahoo.com> wrote in message news:QwF_g.22754$7I1.7456(a)newssvr27.news.prodigy.net... > Peter Olcott wrote: >> "J?n Fairbairn" <jon.fairbairn(a)cl.cam.ac.uk> wrote in message >> news:wf3b9igcw5.fsf(a)calligramme.charmers... >>> Patricia Shanahan <pats(a)acm.org> writes: >>> >>>> If you take the existence of a decision algorithm for the Halting >>>> problem as an axiom, while retaining the normal axioms that ultimately >>>> underly theory of computation, you end up with an inconsistent system of >>>> axioms. Even then, it is the set of axioms that is broken, not the >>>> fundamental concept of truth. >>> I think this illustrates why reasoned argument is futile in >>> this thread. The OP /does/ take the existence of a decision >>> algorthm for the halting problem as an axiom. Consequently, >>> working from his axioms he can reach any conclusion he >>> wishes. >>> >>> -- >>> J?n Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk >> >> The problem is the mathematical mapping between the conclusions based on the >> mathematical formalisms and the higher level English language meanings. This >> problem is caused by arbitrary constraints placed on the formalisms that do >> not actually exist in the greater context. > > Of course formalisms have arbitrary restraints, they are meant > to have. They are not intended to describe some greater context > such as physical reality. The Halting Problem is a FORMAL result. > It is not a result about physical reality and nobody makes that > claim unless they are poorly educated. I told you before that > Turing machines are abstractions not physically real devices. > Turing used TMs to demonstrate his conclusion which later came > to be known as the Halting Problem. > > The question is well-posed because it is a formal question > about a *formal* context. There is no other context, there > is no greater context, such as physical reality. It is a > system of rules. The rules of chess and the movements of > knights have nothing to do with horses and real life. > The Halting Problem is only about the context of formal > mathematics or logic, there is no such thing as a larger > context such as physical reality having restrictions > applied to it by formal results. > > The only person making claims about a larger context > is you making up an imaginary claim for what the domain > of what formal results cover. > > formal logic > n. > > "The study of the properties of propositions and > deductive reasoning by abstraction and analysis > of the form rather than the content of propositions > under consideration." > > When you keep saying greater context, you are > trying to introduce content into the context > which is not an area of consideration. > > Meaning #1: any logical system that abstracts the > form of statements away from their content in order > to establish abstract criteria of consistency and > validity. > > It is like football, which is played within boundaries > that make no claims about defining what land mass is. > A catch is made in bounds or is not a catch, that's > the rule. Whether the game is being played in a greater > context such as a stadium is never an issue. > > "First, formal methods involve the essential use > of a formal language. A formal language is a set > of strings over some well-defined alphabet. Rules > are given for distinguishing those strings, defined > over the alphabet, that belong to the language from > strings that do not." > > That is the province (precise context) of the Halting > Problem. It says nothing about natural language or > the actual universe that natural language attempts to > describe. Your bringing in a "greater context" is an > imaginary postion, all your own, that you attribute > to others. The people on the forum are talking about > a formal result in a specified formal system. It is > proven somewhat like a geometry result. In Euclidean > geometry the sum of a triangle has 180 degrees. In > another kind of geometry it can have more than or > less than 180 degrees, in which case the context is > specified, just like the context of Godel's Inc. > result is specified. The context is exactly defined > it is what it is. It doesn't apply to some non-formal > greater context, or more precisely it isn't proven > to apply to a greater context. Your mention that there > is a greater context has no meaning at all, because even > if it were a formal system, then it would be a different > formal system then the one which is under discussion and > formal systems don't have any direct correspondence to > reality. You are making a strawman argument, which means > you are imagining a false position for other people and > then arguing against that imaginary false position. > So then within the greater context of truth itself, (the mathematical mapping between (typically abstract) representations of actuality and actuality itself), the Halting Problem is saying nothing more than: "Some ill-formed questions lack correct answers entirely due to the fact that the question itself is ill-formed." > > > The only reason that the HP (at least the >> isolated example that I provided) can not be solved, is that it is merely an >> ill-formed question. The fact that ill-formed questions lack correct answers >> should not be elevated to the level of a fundamental theory of computation. >> (if my isolated example can be generalized).
From: Peter Olcott on 22 Oct 2006 08:04 "Mark Jeffcoat" <jeffcoat(a)alumni.rice.edu> wrote in message news:87wt6sn5pt.fsf(a)myc.servebeer.com... > Stephen Harris <cyberguard-1048(a)yahoo.com> writes: > >> J?n Fairbairn wrote: >>> Patricia Shanahan <pats(a)acm.org> writes: >>> >>>> If you take the existence of a decision algorithm for the Halting >>>> problem as an axiom, while retaining the normal axioms that ultimately >>>> underly theory of computation, you end up with an inconsistent system of >>>> axioms. Even then, it is the set of axioms that is broken, not the >>>> fundamental concept of truth. >>> >>> I think this illustrates why reasoned argument is futile in >>> this thread. The OP /does/ take the existence of a decision >>> algorthm for the halting problem as an axiom. Consequently, >>> working from his axioms he can reach any conclusion he >>> wishes. >>> >> >> That sounds nearly as crazy as the OP's ravings. >> What is axiomatic about the Halting Problem?? >> Isn't it consistent with the axioms, and not at >> all independent like the Axiom of Choice. The OP >> *cannot* possibly have just one delusional axiom. > > Of course he can. We are free to believe any axioms > that strike our fancy--we just can't expect conclusions > drawn from them to necessarily make much sense. Sure like the basis for non-Euclidean geometry's foundation (Let me know if I get this incorrectly) that parallel lines meet. > > You know, unless we take that as yet another axiom. > > (It's late, and just in case I'm having a bad-irony > night: reasoning about what other people may believe > is a really, really bad idea. ... If one of your > personal axioms is that you enjoy being right.) > > -- > Mark Jeffcoat > Austin, TX
From: Patricia Shanahan on 22 Oct 2006 09:36
Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message > news:4dx_g.17125$UG4.12313(a)newsread2.news.pas.earthlink.net... >> Peter Olcott wrote: >>> "Patricia Shanahan" <pats(a)acm.org> wrote in message >>> news:yWw_g.10604$Lv3.9258(a)newsread1.news.pas.earthlink.net... >>>> Peter Olcott wrote: >>>> ... >>>>> We can precisely define what is meant by an ill-formed question by saying >>>>> that an ill-formed question is any question that has no possible correct >>>>> answer from the required solution set. The variation of the HP that your >>>>> example refers to has no correct YES or NO answer, thus derives an >>>>> ill-formed question equivalent to the question: "How tall are you red or >>>>> blue?" >>>> Do you think your "Ill formed statement" condition is computable? >>>> >>>> Patricia >>> If we make the usual assumptions that are made in the HP, then yes. If we >>> assume that an algorithm is capable of correctly determining whether or not >>> another program halts, at least in each and every case where this is >>> possible, then this same algorithm would by definition already know the >>> ill-formed cases. The ill-formed cases would be any case where it can neither >>> conclude HALTS, nor conclude NOT_HALTS. >> I do NOT "assume that an algorithm is capable of correctly determining >> whether or not another program halts", whether or not qualified by "at >> least in every case in which this is possible". >> >> It is certainly not an assumption that is usually made in discussing the >> halting problem, other than in the sense that some versions of the proof >> use a proof by contradiction form, in which the prover temporarily >> assumes something exists, demonstrates a contradiction, and concludes it >> does not exist. > > I am not taking on the burden of proving that solving the HP is possible. The > most burden that I am taking on is showing that there might have been some > errors with some of the prior proofs that solving the HP is impossible. Within > the context of the above mentioned assumptions, if I can merely show that the > conclusions drawn from these assumptions and proofs might not logically follow > from the logic of these proofs, I have met the minimum degree of my original > goals. The problem with this is that I believe you need a Turing machine halting problem decider to decide the MSR condition: int HaltTest(HaltTestSource){ if(WillHalt(HaltTestSource,HaltTestSource){ Turing(someTM, someInput); }else{ return; } } Suppose HaltTestSource is the source code for HaltTest, including the strings specifying someTM and someInput. Turing is a Turing machine simulator that runs someTM with someInput as initial tape contents. As a Turing machine simulator, it does not allow for exceptions. It returns if, and only if, someTM reaches a terminal state when run with initial tape contents someInput. If someTM(someInput) halts, then this program halts regardless of the result of WillHalt. WillHalt can, and should, return TRUE. If someTM(someInput) does not halt, then WillHalt should throw an MSR exception. In order to decide whether to throw the exception or not, at least according to your current definition, you need to know whether Turing returns or not. That can be determined only by a general, no exceptions, Turing machine halting problem decider. someTM may involve code equivalent to your HaltTest implementation, with the exception treated as a form of halting. Regardless of that, you need to know whether it halts. A lot of questions about dynamic properties of programs, such as "does it ever reach this statement", turn out to be halting problem equivalent. I will be surprised if you can find a specification for the MSR condition that is decidable. Patricia |