A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 19 Oct 2006 09:07 Peter Olcott says... >"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> You are assuming that there is a program >> MalignantSelfReference(SourceCode, InputData) >> which will return true if executing that >> particular source code on that input data >> results in a "malignant self reference". >> >> But then determining whether something involves >> "malignant self reference" is, in fact, >> equivalent to solving the halting problem. >I am assuming nothing. I have shown step by step point by point, >item by item, exactly and precisely how such a program could be >constructed within the precise focus of this specific example. What you have described is perhaps a way to detect *explicit* self-reference. However, given any computer program, there are infinitely many programs that do the exact same thing, but have different source codes. It is not possible to detect that two programs are, in fact, equivalent programs. In light of that, consider your proposed solution. You want to have a program willHalt(p,x) with three possible outcomes: (1) If program p halts on input x, then willHalt returns true. (2) If program p does not halt on input x, then willHalt returns false. (3) If program p makes a self-referential call on willHalt, then willHalt throws an exception. Okay, so now let Q(p,x) be some other program with two inputs. Let F(x) be a program with the following behavior: if Q(x,x) returns true, then loop forever, if Q(x,x) returns false, then halt. Now, let's run willHalt(F,F). How does willHalt decide whether to throw a "MalignantSelfReferenceException"? -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 19 Oct 2006 09:19 Peter Olcott says... >>>int WillHalt(string SourceCode, string InputData) { >>> if (MalignantSelfReference(SourceCode, InputData)) >>> throw(MALIGNANT_SELF_REFERENCE); >>> if ( TheProgramWillHalt(SourceCode, InputData) ) >>> return TRUE; >>> else >>> return FALSE; >>>} >> >> You are assuming that there is a program >> MalignantSelfReference(SourceCode, InputData) >> which will return true if executing that >> particular source code on that input data >> results in a "malignant self reference". >I am assuming nothing. Yes, you are. You are assuming that MalignantSelfReference(SourceCode,InputData) can detect whether there is a "malignant self reference". There is no such program. Once again, you have your program WillHalt(string SourceCode, string InputData). Now, let Q(p,x) be a function that has exactly the same behavior as WillHalt, but completely different source code. Let f(x) be the following function f(String x) { if (Q(x,x)) { loop(); } } Let #f be the source code for f, and consider the computation WillHalt(#f,#f) On what basis will WillHalt throw a Malignant Self Reference Exception? Step through the computation of MalignantSelfReference(#f,#f), and show how it decides whether to return true or not. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 19 Oct 2006 09:27 Peter Olcott says... >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)) > throw(MALIGNANT_SELF_REFERENCE); > if ( TheProgramWillHalt(SourceCode, InputData) ) > return TRUE; > else > return FALSE; >} > > >LoopIfHalts(LoopIfHalts); The original statement of the halting problem doesn't include "exceptions". Throwing an exception is just one particular way of halting. However, if you want to say that there are three possible results of running a program: (1) The program halts, (2) the program runs forever, or (3) the program throws an exception, then we can recast the halting problem as follows: There is no program throwsException(p,x) such that (1) If the program whose source code is p, when run on input x throws an exception, then throwsException returns true. (2) If the program whose source code is p, when run on input x never throws an exception, then throwsException returns false. There is no program throwsException that works correctly on all inputs. -- Daryl McCullough Ithaca, NY
From: sillybanter on 19 Oct 2006 09:48 In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > So the equivalent of the return value of the Halt() function from > the TM is the integer value that the TM's ReadWrite head rests on > when the TM halts. In this case DOES_NOT_HALT=0 HALTS=1 > MALIGNANT_SELF_REFERENCE=2. This scenario breaks out of the infinite > recursion of the original specification of the problem, and provides > the only possible correct answer. In the standard presentation of the halting problem, there is no recursion, infinite or otherwise. Don't be confused by the fact that the same name of a function is used in the analyzed program and in the analyzer - it's not the same thing, and these two instances of "Halt" are completely separate. That can certainly be confusing, but if you don't understand that then consider it like this: Take the putative Halt procedure and everywhere you see "Halt" just replace that with the name "CopyOfHalt". Now you have something completely equivalent, and you can call "CopyOfHalt" in the "LoopIfHalts" function. There is no requirement in the halting problem proof that CopyOfHalt be recursive (or that it not be recursive for that matter). And CopyOfHalt certainly can't call "LoopIfHalts" or the original "Halt" function, so there's no chance of indirect recursion there either. So now we have something that clearly doesn't have to be recursive in any shape or form, and yet the proof of the halting problem still works out. How does that affect your belief that somehow "infinite recursion" is involved? -- Steve Stringer sillybanter(a)gmail.com
From: sillybanter on 19 Oct 2006 09:53
In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: > That seems to be a very precise English language statement that is > most typically used to describe the results of the HP. It is this > statement that I refute. I may be wrong, I have been wrong before, > but, it is still this specific statement that I refute. The HP can > be decided, yet the answer can not be restricted to YES or NO > because the question is not a YES or NO question. There are certainly problems that are ill-formed, but the halting problem is not one of those. Deal with the real form of the halting problem for a minute - don't try to change the model or anything. Now consider the following statement: Given a TM (or a program in any TM-equivalent language, if you prefer) and an input, when the TM is run with the input it either halts in a finite number of steps or it doesn't. Do you somehow disagree with that? I'm not sure how you could - that seems to partition the space of possibilities quite nicely. Either something happens or it doesn't. Yes or no. Completely well formed. *You* may not know for a particular program/input whether the answer is yes or no, so you might want to add a third choice "I dont' know", but that's a different question - and doesn't negate the fact that there *is* a yes or a no answer. -- Steve Stringer sillybanter(a)gmail.com |