A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 21 Oct 2006 18:51 "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. > > Can you discuss the question without introducing arbitrary, and highly > controversial, assumptions? > > Patricia
From: R. Srinivasan on 21 Oct 2006 19:14 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 is so because TMs are infinite objects (in the same way that real numbers 1, 2, 3, .. are infinite objects), they must be specified constructively, as required by NAFL; quantification over TMs is not allowed and an arbitrary TM, with no construction specified, does not exist. In spite of these restrictions, it is possible to formulate computability theory in NAFL. See <http://arxiv.org/abs/math.LO/0506475>. Cantor's diagonal argument and Turing's argument for undecidability of the halting problem do not go through because mappings from the real numbers or TMs to the natural numbers do not exist in NAFL. Many of the results of classical real analysis and classical recursion theory fail in NAFL. Hence the NAFL TM is a non-classical entity. Regards, RS
From: Karl Klose on 21 Oct 2006 19:40 Peter Olcott schrieb: > The Halt program throws an "Invalid Input" exception. > This would be analogous to the hardware exception of an attempt to divide by > zero. > > It seems less and less undecidable, if this threat will ever end. SCNR, Karl
From: Jack Campin - bogus address on 21 Oct 2006 20:09 > TMs are infinite objects (in the same way that real > numbers 1, 2, 3, .. are infinite objects), they must be specified > constructively, as required by NAFL; The usual specification *is* constructive - more than that, completely finitistic, ity's just a finite set of tuples - and a terminating TM computation only uses a finite amount of tape so that's a finite combinatorial object too. > quantification over TMs is not > allowed and an arbitrary TM, with no construction specified, does not > exist. In spite of these restrictions, it is possible to formulate > computability theory in NAFL. I think I see what you're driving at but it sure ain't what Peter's driving at. ============== j-c ====== @ ====== purr . demon . co . uk ============== Jack Campin: 11 Third St, Newtongrange EH22 4PU, Scotland | tel 0131 660 4760 <http://www.purr.demon.co.uk/jack/> for CD-ROMs and free | fax 0870 0554 975 stuff: Scottish music, food intolerance, & Mac logic fonts | mob 07800 739 557
From: Peter Olcott on 21 Oct 2006 22:32
"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. > is so because TMs are infinite objects (in the same way that real > numbers 1, 2, 3, .. are infinite objects), they must be specified > constructively, as required by NAFL; quantification over TMs is not > allowed and an arbitrary TM, with no construction specified, does not > exist. In spite of these restrictions, it is possible to formulate > computability theory in NAFL. See > <http://arxiv.org/abs/math.LO/0506475>. Cantor's diagonal argument and > Turing's argument for undecidability of the halting problem do not go > through because mappings from the real numbers or TMs to the natural > numbers do not exist in NAFL. Many of the results of classical real > analysis and classical recursion theory fail in NAFL. Hence the NAFL TM > is a non-classical entity. > > Regards, RS > |