A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 22 Oct 2006 18:35 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:453bea20(a)news.ish.de... > Peter Olcott wrote: >> "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message >> news:453bdcc4(a)news.ish.de... >>> Peter Olcott wrote: >>>> int MalignantSelfReference(SourceCode, InputData) { >>>> if ( IsSourceCode(InputData) ) >>>> if ( MatchSelfReferencePattern(SourceCode, InputData) ) >>>> if ( DetectedSelfReferenceTogglesTheReturnValue(SourceCode, >>>> InputData) ) >>>> return TRUE; >>>> return FALSE; >>>> } >>>> >>>> For all the examples provided so far Matching the pattern has not been >>>> shown to be impossible. There might be constructions whereby the first >>>> step must be removed to be comprehensive. >>> // Let f be some terminating function >>> bool f(p,x) { >>> // implementation does not matter, eg >>> // return length(p) > length(x) >>> } >>> >>> bool g(s) { >>> if f(s,s) == TRUE >>> return FALSE; >>> else >>> return TRUE; >>> } >>> // g clearly terminates >>> >>> What's the result of MalignantSelfReference(g,g)? >>> If it returns FALSE, how can it distinguish g from WillHalt? If it returns >>> TRUE, WillHalt(g) gives a wrong result. >> >> Your question is not precisely correct, the basis for comparison is >> LoopIfHalts(LoopIfHalts), not WillHalt() please try and re-formulate your >> question, I can't tell exactly where you are plugging g into the prior >> example from what you have said. Please be 100% explicit, and modify the code >> below to indicate exactly what you mean. > The question is: What is the result of MalignantSelfReference(g,g)? Is it Yes > or No? How can this question be not precisely correct?!? > And following from that, what is the result of WillHalt(g)? 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. > >> >> void LoopIfHalts(string SourceCode) { >> if ( WillHalt(SourceCode, SourceCode) == TRUE ) >> while (TRUE) // loop forever >> ; >> else >> return; >> } >> >> int WillHalt(string SourceCode, string InputData) { >> if (MalignantSelfReference(SourceCode, InputData)) >> return MALIGNANT_SELF_REFERENCE; >> if ( TheProgramWillHalt(SourceCode, InputData) ) >> return TRUE; >> else >> return FALSE; >> } >> >> LoopIfHalts(LoopIfHalts);
From: Frank Ch. Eigler on 22 Oct 2006 20:32 "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
From: The Ghost In The Machine on 22 Oct 2006 21:07 In sci.logic, Frank Ch. Eigler <fche(a)redhat.com> wrote on 22 Oct 2006 20:32:41 -0400 <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 Not to mention that a self-reference is in fact impossible in this problem. The code is passed in as a *string* [*]; while it is possible to pass in a modified copy of WillHalt that's hardly a self-reference, malignant or otherwise. [*] one could construe it as an array of codons, but the two aren't all that different, and one can also contemplate a machine whose operations and operands are all ASCII characters. -- #191, ewill3(a)earthlink.net "640K ought to be enough for anybody." - allegedly said by Bill Gates, 1981, but somebody had to make this up! -- Posted via a free Usenet account from http://www.teranews.com
From: Peter Olcott on 22 Oct 2006 23:52 "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 If you can prove me wrong then simply do so. It might only take a single valid counter-example, otherwise a single valid counter-example might not exist.
From: Peter Olcott on 22 Oct 2006 23:57
"The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message news:j7ht04-ghv.ln1(a)sirius.tg00suus7038.net... > In sci.logic, Frank Ch. Eigler > <fche(a)redhat.com> > wrote > on 22 Oct 2006 20:32:41 -0400 > <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 > > Not to mention that a self-reference is in fact impossible in this > problem. The code is passed in as a *string* [*]; while it is possible to > pass in a modified copy of WillHalt that's hardly a self-reference, > malignant or otherwise. The WillHalt() function obviously performs a simulated execution trace, there is no problem with doing this on the basis of source-code. void LoopIfHalts(string SourceCode) { if ( WillHalt(SourceCode, SourceCode) == TRUE ) while (TRUE) // loop forever ; else return; } int WillHalt(string SourceCode, string InputData) { if (MalignantSelfReference(SourceCode, InputData)) return MALIGNANT_SELF_REFERENCE; if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } Hypothesis: There does not exist any possible set of SourceCode, InputData, whereby detection of MALIGNANT_SELF_REFERENCE can be shown to be impossible. A single valid counter-example is all that is required to correctly refute this hypothesis. > > [*] one could construe it as an array of codons, but the two aren't > all that different, and one can also contemplate a machine whose > operations and operands are all ASCII characters. > > -- > #191, ewill3(a)earthlink.net > "640K ought to be enough for anybody." > - allegedly said by Bill Gates, 1981, but somebody had to make this up! > > -- > Posted via a free Usenet account from http://www.teranews.com > |