A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 22 Oct 2006 16:36 "Jens Auer" <jens.auer-news(a)betaversion.net> wrote in message news:453bd212(a)news.ish.de... > Peter Olcott wrote: >> No this is not what I said. If you feed LoopIfHalts2() to WillHalt(), then >> WillHalt'() sees the MALIGNANT_SELF_REFERENCE to itself. > So, there is not a single MALIGNANT_SELF_REFERENCE function, but one for each > function? I have to ask you again, define either the set of MSR functions or > give a definition of MSR, in terms of pseudo-code, Turing machine program or > some equivalent statement. 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.
From: Jens Auer on 22 Oct 2006 16:21 Peter Olcott wrote: > No this is not what I said. If you feed LoopIfHalts2() to WillHalt(), then > WillHalt'() sees the MALIGNANT_SELF_REFERENCE to itself. Another question: Does the call the MSR in WillHalt(LoopIfHalts2, LoopIfHalts2) see the self-reference or not? It has to, because WillHalt and WillHalt' compute equivalent functions. But how can the call to MSR in WillHalt decide that?
From: Jens Auer on 22 Oct 2006 17:04 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.
From: Peter Olcott on 22 Oct 2006 17:53 "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. 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: Jens Auer on 22 Oct 2006 18:01
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)? > > 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); |