A Possible "solution" to the Halting Problem
in [Theory]
|
From: The Ghost In The Machine on 22 Oct 2006 01:12 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. 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? 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: Stephen Harris on 22 Oct 2006 03:04 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.
From: R. Srinivasan on 22 Oct 2006 03:34 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.
From: Stephen Harris on 22 Oct 2006 03:58 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. 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: Mark Jeffcoat on 22 Oct 2006 04:08
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. 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 |