A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 19 Oct 2006 22:11 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh98ll02di5(a)drn.newsguy.com... > Peter Olcott says... > > "Daryl McCullough" wrote > >>> There is nothing ill formed about the question: >>> >>> Does LoopIfHalts halt when given its own source code as an input? >>> >>> Your program WillHalt fails to answer that question, but there is nothing >>> ill formed about the question. >>> >>>>Iff (if and only if) I can reach a consensus on this point >>> >>> Your point is false. There is nothing ill-formed about the question. >> >>When we add the context that the program always changes the >>result of any answer that is provided, then, the quesion >>become ill-formed. > > No, it's not. As you described it, LoopIfHalts *halts* (after > raising an exception) if given its own source code as input. > So the correct answer to the question is: Yes, LoopIfHalts > halts when given its own source code as input. > > The answer is "true". It's *always* true. There is nothing > ill-defined about the question. It's just that WillHalts > fails to give the correct answer. Yet again you fail to get the precise context correctly, (don't feel bad most everyone had made this same mistake for many decades). The correct answer to the question, also depends on the context of whom is being asked. When you are asked the question there is a different correct answer than when WillHalt() is asked this same question. If I ask you the name of your wife, I get one answer, if I ask your wife the exact same question, "What is the name of your wife?" I get a different answer. Context is everything. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 19 Oct 2006 22:19 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh9a3l02het(a)drn.newsguy.com... > Peter Olcott says... > >>"Charlie-Boo" <shymathguy(a)gmail.com> wrote > >>>> That is not within my purpose. My purpose is to show that the >>>> Halting Problem is really nothing more than an ill-formed question. >>> >>> Ill-formed in what sense? The problem is that it is inconsistent - >>> regarding whether a program that runs the program being specified >>> against its input as both program and input, when run against itself >>> halts or not. >> >>Inconsistent in the sense of the ANALYTICAL COMMENTARY mentioned below > > Your commentary doesn't show that the halting problem is an > ill-formed question. Yet another case of the lack of precision on your taking the meaning that I am specifying. I am not yet even beginning to talk about THE Halting Problem, I am only talking about one specific instance of A halting problem. > If a program is deterministic, then whether > it halts or not is a meaningful question. The fact that WillHalt > is unable to correctly answer question doesn't make the question > ill-formed. In the specific instance of WillHalt() indeed it does. In the specific instance of WillHalt() it can see than any answer that it provides is corrupted. You think that you can see what the true answer is, and WillHalt() can not see this. This is not the case. WillHalt() can determine the correct answer, the same way that you can determine the correct answer. It merely can not provide this correct answer in the form of a Boolean, because its output path is intentionally corrupted. It can see that its output path is intentionally corrupted, and thus there is no possible correct Boolean answer that it can provide, so it simply calls the game on the count of cheating. > > -- > Daryl McCullough > Ithaca, NY >
From: Daryl McCullough on 19 Oct 2006 22:21 Peter Olcott says... >"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> No, you have done no such thing. To solve the halting >> problem means to have a program which, given *any* >> program p and any input x, returns true if p halts on >> x, and returns false otherwise. Your program WillHalt >> doesn't do that. > >See that now I wasn't 100% exact and precise in the choice of my words. >I did not really "solve" a halting problem, You didn't solve anything, Peter. You just wrote down a couple of programs in pseudo-code. >what I did was show that the only reason that the example of a >halting problem that I provided could not be solved >because the problem itself was merely an ill-formed question. >Would you agree with that? No, there is nothing ill-formed about the question: Does LoopIfHalts halt when given its own source code as input? >If not, then exactly and precisely, point by point detail >by detail what is it that you disagree with What I disagree with is the claim that the question "Does LoopIfHalts halt when given its own source code as input?" is ill-formed. It's perfectly well-formed, and it has a perfectly clear answer: Yes! If WillHalt and MalignantSelfReference behave as advertised, then LoopIfHalts(LoopIfHalts) halts by raising an exception. -- Daryl McCullough Ithaca, NY
From: Peter Olcott on 19 Oct 2006 22:52 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh9bqr02m8o(a)drn.newsguy.com... > Peter Olcott says... > >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote > >>> No, you have done no such thing. To solve the halting >>> problem means to have a program which, given *any* >>> program p and any input x, returns true if p halts on >>> x, and returns false otherwise. Your program WillHalt >>> doesn't do that. >> >>See that now I wasn't 100% exact and precise in the choice of my words. >>I did not really "solve" a halting problem, > > You didn't solve anything, Peter. You just wrote down a couple > of programs in pseudo-code. > >>what I did was show that the only reason that the example of a >>halting problem that I provided could not be solved >>because the problem itself was merely an ill-formed question. >>Would you agree with that? > > No, there is nothing ill-formed about the question: Does > LoopIfHalts halt when given its own source code as input? > >>If not, then exactly and precisely, point by point detail >>by detail what is it that you disagree with > > What I disagree with is the claim that the question > "Does LoopIfHalts halt when given its own source code as input?" > is ill-formed. It's perfectly well-formed, and it has a perfectly > clear answer: Yes! If WillHalt and MalignantSelfReference behave > as advertised, then LoopIfHalts(LoopIfHalts) halts by raising > an exception. Yes, except you ignored the fact that WillHalt() can see that its output path is corrupted. If your output path was corrupted, you would have the same problem. The error that everyone makes on this problem is concluding that WillHalt() can not determine whether or not LoopIfHalts(LoopIfHalts) will halt. WillHalt() CAN DETERMINE that LoopIfHalts(LoopIfHalts) HALTS!!! It merely can not provide the result of this determination using its intentionally corrupted output path. Thus it is not undecidable at all!!! > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 19 Oct 2006 18:31
"Patricia Shanahan" <pats(a)acm.org> wrote in message news:1KSZg.9408$Lv3.7227(a)newsread1.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message >> news:r1NZg.15912$UG4.2273(a)newsread2.news.pas.earthlink.net... >>> The Ghost In The Machine wrote: >>>> In sci.logic, Patricia Shanahan >>>> <pats(a)acm.org> >>>> wrote >>>> on Wed, 18 Oct 2006 22:22:10 GMT >>>> <mOxZg.15598$UG4.10415(a)newsread2.news.pas.earthlink.net>: >>>>> Peter Olcott 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. >>>>> OK, so now we are down to a well-defined environment. Perhaps >>>>> you can explain how you define a MALIGNANT_SELF_REFERENCE in a Turing >>>>> machine computation? >>>>> >>>>> Patricia >>>> It can always be true, which leads to a Halt() function >>>> that always throws an exception. This is a valid if >>>> pointless solution. >>> Whether it is a valid solution depends on the definition of >>> MALIGNANT_SELF_REFERENCE. If it is just equivalent to the I_GIVE_UP >>> exception, then always throwing it is valid but pointless. >> >> It is equivalent to saying that no correct answer exists to the question, >> "How tall are you green or blue?" because the question itself is ill-formed. >> It is not at all equivalent to I_GIVE_UP. > > There is a very big difference. Whether there is a correct answer to > "How tall are you, x or y" depends on whether the set {x,y} includes > your height. That is decidable: measure the person in question, look at > all elements of {x,y} that represent lengths, and see if any of them > match the height. How tall are you blue or green (where blue and green are colors and no possible numerical quantity) can not possibly be correctly answered entirely due to the ill-form of the question itself. The particular and specific example of a halting problem, is only a problem for this exact same sort of reason. It is 100% completely impossible to correctly decide between the alternatives of blue and green to select one of these alternatives that provides the correct numerical quantity representing one's height. This problem is undecidable. > > Similarly, whether a division involves division by zero is decidable: > Compare the divisor to zero. If it is equal, there is a division by zero. The question is not "Is there division by zero?" int double X = 50.0 / 0.0; The question is what is the numerical quantity of this specific instance of division by zero? This question is undecidable. > > Whether a program uses the result of a given function call to control > whether to loop forever or to halt is not decidable. > > Patricia That is obviously completely decidable, (within the specific example that I provided) just look at the source code, and you can see whether or not this is occurring. |