A Possible "solution" to the Halting Problem
in [Theory]
|
From: Patricia Shanahan on 19 Oct 2006 18:34 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message .... >> I strongly disagree with any idea of using the term "halting problem" >> for this, because the Halting Problem is a decision problem. It asks >> whether its input is, or is not, a member of a specific language, and >> the only possible answers are to accept or reject the input. > > http://www.cprogramming.com/tutorial/computersciencetheory/halting.html That page indeed deals, at least informally, with the halting problem. However, you seem to have failed to grasp the fact that changing the rules of the game to allow three results from your function, instead of the two possible answers from a decision procedure, also changes the correct design of the calling program in the non-existence proof. That page is completely irrelevant to your revised problem. I've already presented one possible replacement program that takes into account the new rules, as far as I've been able to discover them. Patricia
From: Daryl McCullough on 19 Oct 2006 18:23 Peter Olcott says... >> 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. 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. It's a perfectly sensible question to ask, and your program WillHalt fails to give a correct answer. Instead, your program raises an exception. It gives up, rather than answering the question. -- Daryl McCullough Ithaca, NY
From: Daryl McCullough on 19 Oct 2006 18:26 Peter Olcott says... >I think that I have shown in my prior response to you at least one example of a >halting problem, that is only a problem because it is ill formed. No, you did not. 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. -- Daryl McCullough Ithaca, NY
From: Peter Olcott on 19 Oct 2006 18:47 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:b4TZg.11664$Y24.2730(a)newsread4.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message > ... >>> I strongly disagree with any idea of using the term "halting problem" >>> for this, because the Halting Problem is a decision problem. It asks >>> whether its input is, or is not, a member of a specific language, and >>> the only possible answers are to accept or reject the input. >> >> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > > That page indeed deals, at least informally, with the halting problem. > > However, you seem to have failed to grasp the fact that changing the > rules of the game to allow three results from your function, instead of > the two possible answers from a decision procedure, also changes the > correct design of the calling program in the non-existence proof. It shows that the original limitation to the two possible Boolean values was artificially contrived to create a problem where none truly existed. What is more plausible, there is something fundamentally wrong with the most basic conception of truth, or a large number of fallible human beings became confused about the fundamental conception of truth for many decades? The fundamental concept of truth is not broken, it retains its full integrity regardless of fallible human misconceptions. > > That page is completely irrelevant to your revised problem. > > I've already presented one possible replacement program that takes into > account the new rules, as far as I've been able to discover them. > > Patricia I missed that.
From: Daryl McCullough on 19 Oct 2006 18:30
Peter Olcott says... > > >"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote >> Yes, you are. You are assuming that >> MalignantSelfReference(SourceCode,InputData) >> can detect whether there is a "malignant self >> reference". There is no such program. > >I provided the detailed steps of the design of such a program >for this specific instance of a halting problem TWICE !!! 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. -- Daryl McCullough Ithaca, NY |