A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 23 Oct 2006 00:01 "Frank Ch. Eigler" <fche(a)redhat.com> wrote in message news:y0mlkn7vpli.fsf(a)ton.toronto.redhat.com... > > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> No this is not what I said. If you feed LoopIfHalts2() to >> WillHalt(), then WillHalt'() sees the MALIGNANT_SELF_REFERENCE to >> itself. > > Malignant self reference appears to be the kind of disorder that makes > you want to re-humiliate yourself every few years. Have you already > forgotten summer of 2004? > > http://groups.google.com/group/comp.theory/msg/802adc0adb837521?hl=en& > > - FChE By the way, my prior line-of-reasoning was correctly refuted by someone calling themselves NewsToMe. There is someone here than claims to be that same person: Steve Stringer sillybanter(a)gmail.com, and I accept this claim.
From: Jens Auer on 23 Oct 2006 02:06 Peter Olcott wrote: > What is the result of MalignantSelfReference(g,g) FALSE > what is the result of WillHalt(g, g) TRUE > > WillHalt(), LoopIfHalts() and g() all have different execution traces. Then MalignantSelfReference(g,g) can see that f is different from WillHalt, in other words it shows that f is not equivalent to WillHalt. This is not possible in general because it involves, as Patricia notes, solving the halting problem. For computing MalignantSelfReference(g,g), you need to solve the halting problem for g, but MalignantSelfReference(g,g) is itself part of your halting problem solver. Do you see the problem?
From: Jens Auer on 23 Oct 2006 02:31 Patricia Shanahan wrote: > I'm being a bit more direct, by forcing WillHalt to decide, in the usual > theory of computation sense, the Turing machine halting problem in order > to know whether to throw the MSR. To take up on this argument, consider the definition Peter gives in another post: int MalignantSelfReference(SourceCode, InputData) { if ( IsSourceCode(InputData) ) if ( MatchSelfReferencePattern(SourceCode, InputData) ) if ( DetectedSelfReferenceTogglesTheReturnValue(SourceCode, InputData) ) return TRUE; return FALSE; } There is a function called DetectedSelfReferenceTogglesTheReturnValue(SourceCode, InputData). After finding the self-reference (which is IMHO undecidable as well), it has to check the expression after the self-reference if it is the opposite of the WillHalt(s,s) expression. In other words, DetectedSelfReferenceTogglesTheReturnValue(SourceCode, InputData) has to determine the halting value of the expression following the condition, in the LoopIfHalts example this would be while(TRUE); this is a circular definition.
From: Stephen Harris on 23 Oct 2006 07:32 R. Srinivasan wrote: > 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 What do you mean "except". You write as if that is a minor consideration. You *must* move to another logic so there is a ***HUGE*** difference in your positions. Moreover, Pi is an infinite abstract object. Pi is computable by a Turing Machine. There is no claim that the computation of Pi is completed; there is no claim for a completed infinity. So then you want to belabor the distinction between finitely unbounded and potentially infinite. > 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. > Postulating abstract infinite entities is in no way equivalent to declaring a belief in Platonic realms. TMs are not physical and nothing physical is infinite although perhaps the "universe" can be disputed. The successor axiom is arguably self-referential. Any logic is going to be self-referential is a weak sense, that is inescapable. I think you are another crackpot, you certainly know nothing about philosophy, such as "I think, therefore I am." That is the foundation and no logic can escape that assumption.
From: Stephen Harris on 23 Oct 2006 07:54
Stephen Harris wrote: > R. Srinivasan wrote: >> 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 > > What do you mean "except". You write as if that is a minor > consideration. You *must* move to another logic so there is > a ***HUGE*** difference in your positions. > > Moreover, Pi is an infinite abstract object. Pi is computable > by a Turing Machine. There is no claim that the computation > of Pi is completed; there is no claim for a completed infinity. > So then you want to belabor the distinction between finitely > unbounded and potentially infinite. > >> 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. >> > > Postulating abstract infinite entities is in no way equivalent > to declaring a belief in Platonic realms. TMs are not physical > and nothing physical is infinite although perhaps the "universe" > can be disputed. The successor axiom is arguably self-referential. > Any logic is going to be self-referential is a weak sense, that > is inescapable. I think you are another crackpot, you certainly > know nothing about philosophy, such as "I think, therefore I am." > That is the foundation and no logic can escape that assumption. Ok, I started on your Platonism paper and you are not a crackpot. I am going to critique it because it surely is more interesting than this thread. |