A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 19 Oct 2006 21:20 Peter Olcott says... "Daryl McCullough" wrote >> You described a MalignantSelfReference detector that works >> by checking if LoopIfHalts makes calls to WillHalt. >> If instead LoopIfHalts uses a program that is different from, >> but has the same behavior as WillHalt, then your detector >> will not work. > >So then you admit that I have solved a halting problem, 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. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 19 Oct 2006 21:27 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. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 19 Oct 2006 21:29 Peter Olcott says... >"Daryl McCullough" wrote >> On the contrary, there is nothing ill-formed about the question: >> >> Does the program LoopIfHalts halt when it is fed its own source >> code as input. > >There is nothing ill-formed about this question until one adds >the specific context of the LoopIfHalts() program. Still there is nothing ill-formed about the question. As you've defined it, the answer is "yes". LoopIfHalts halts (after raising an exception) when given its own source code as an input. >There are many questions that are not ill-formed until adding a specific >context. Perhaps, but this is not one of them. -- Daryl McCullough Ithaca, NY
From: Peter Olcott on 19 Oct 2006 22:05 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh989902chq(a)drn.newsguy.com... > Peter Olcott says... > > "Daryl McCullough" wrote > >>> You described a MalignantSelfReference detector that works >>> by checking if LoopIfHalts makes calls to WillHalt. >>> If instead LoopIfHalts uses a program that is different from, >>> but has the same behavior as WillHalt, then your detector >>> will not work. >> >>So then you admit that I have solved a halting problem, > > 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, 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? If not, then exactly and precisely, point by point detail by detail what is it that you disagree with, the precisely stated conclusion formed above? > > -- > Daryl McCullough > Ithaca, NY >
From: Daryl McCullough on 19 Oct 2006 21:51
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. 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. -- Daryl McCullough Ithaca, NY |