A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 23 Oct 2006 08:53 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:453c5c09(a)news.ish.de... > 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? Rice's theorem? A possible practical way around the results of this theorem would be to constrain the means of specifying algorithms to some form of well-ordered set where Rice's theorem would not apply. In this case one could not only possibly achieve a universal halt detector that works correctly on every program that adheres to the required specification conventions, but, further still an automatic logical validator. In any case my original point still applies. The classical form of the Halting Problem still seems to be more accurately construed as an ill-formed question, rather than an undecidable problem.
From: Peter Olcott on 23 Oct 2006 08:54 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:453c61bf(a)news.ish.de... > 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. It is not a circular definition, it is a stub for details left out.
From: Daryl McCullough on 23 Oct 2006 09:04 Peter Olcott says... >If you can prove me wrong then simply do so. There are different issues here: Proving to someone *else* that Peter Olcott is wrong, and proving to Peter Olcott that he is wrong. To accomplish the latter requires *both* that you have a correct proof, *and* that Peter Olcott can follow a correct proof. That's way too much to ask. -- Daryl McCullough Ithaca, NY
From: Antti Valmari on 23 Oct 2006 09:49 Peter Olcott wrote: > All > that my maximum burden of proof requires is that I show that prior proofs that > Halting is undecidable are incorrect. > > If in each and every specific attempt to provide a valid counter-example that > Halting is undecidable I can show that this specific attempt has failed, I will > have met my maximum burden of proof. Perhaps a week ago I posted in comp.theory a "no halting tester" proof that goes along entirely different lines of thought from what has been discussed. (It follows the "busy beaver" argument.) I used the Subject: "Non-existence of halting tester proven without "malignant self reference"". Did you notice it? My newsreader still found it, about 230 postings back. In that proof, there are no programs looking at other programs' or their own code. The argumentation is simple, and I tried my best to make the proof very readable. I would be curious to learn where the MSR emerges in that proof, or if you find any other flaw in it. --- Antti Valmari ---
From: Peter Olcott on 23 Oct 2006 10:46
"Antti Valmari" <ava@.c.s...t.u.t...f.i.invalid> wrote in message news:ehih9n$b4s$1(a)news.cc.tut.fi... > > Peter Olcott wrote: >> All >> that my maximum burden of proof requires is that I show that prior proofs >> that >> Halting is undecidable are incorrect. >> >> If in each and every specific attempt to provide a valid counter-example that >> Halting is undecidable I can show that this specific attempt has failed, I >> will >> have met my maximum burden of proof. > > Perhaps a week ago I posted in comp.theory a "no halting tester" proof > that goes along entirely different lines of thought from what has been > discussed. (It follows the "busy beaver" argument.) I used the Subject: > "Non-existence of halting tester proven without "malignant self reference"". > Did you notice it? My newsreader still found it, about 230 postings back. > In that proof, there are no programs looking at other programs' or their > own code. The argumentation is simple, and I tried my best to make the > proof very readable. I would be curious to learn where the MSR emerges > in that proof, or if you find any other flaw in it. > > --- Antti Valmari --- > > My recent response to Daryl presents my currently updated position within the context of TM's. |