A Possible "solution" to the Halting Problem
in [Theory]
|
From: Daryl McCullough on 20 Oct 2006 07:18 Aatu Koskensilta says... > >Jack Campin - bogus address wrote: >> "Peter Olcott" <NoSpam(a)SeeScreen.com> wrote: >>> if (MalignantSelfReference(SourceCode, InputData)) >> >> This isn't code, it's wishful thinking. You haven't proved that >> any such function as MalignantSelfReference can exist, you haven't >> programmed it, and you haven't proved that it always returns a value. >> >> For that matter you haven't even *specified* it. > >He has said something to the effect that a program contains "malignant >self-reference" if it has a call to Halt with its own source as an argument. I seem to remember an article from long ago in which Peter suggested that tight computer security could be used to solve the halting problem. The idea is that you keep the source code for Halt secret, so that nobody can ever use it to generate a logical contradiction. -- Daryl McCullough Ithaca, NY
From: Aatu Koskensilta on 20 Oct 2006 07:53 Daryl McCullough wrote: > I seem to remember an article from long ago in which Peter suggested > that tight computer security could be used to solve the halting > problem. The idea is that you keep the source code for Halt secret, > so that nobody can ever use it to generate a logical contradiction. That was one of his sillier ideas, yes. It appears he didn't follow my earlier suggestion and read up on recursive functions so as to be able to show how to implement "protected memory" and what not in terms of those. -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Peter Olcott on 20 Oct 2006 08:36 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:uL%Zg.16267$UG4.9344(a)newsread2.news.pas.earthlink.net... > Peter Olcott wrote: >> "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 Peter > ">" from me > >>> WillHalt() is provided with the source code of LoopIfHalts(), as input, so >> >> Not necessarily. It can be provided with the source code of any program >> that is equivalent to LoopIfHalts in the sense of halting on SoureCode >> if, and only if, SourceCode itself does so: >> >> if ( WillHalt(ObfuscateHorribly(SourceCode),SourceCode) == True ) >> >> For example, ObfuscateHorribly may translate SourceCode to Snobol, and >> wrap it up with a Snobol interpreter. >> >> >>> WillHalt() can see exactly how the return value of the invocation of itself >>> under test will be used to toggle the result of the analysis of the >>> invocation of itself under test. WillHalt() can see that LoopIfHalts() is >>> toggling the result of the invocation of itself under test to invalidate the >>> analysis of the invocation of itself under test. >> >> How does it recognize programs equivalent, but not identical, to itself? >> >> Moreover, you need to consider far more complicated LoopIfHalts >> implementations. The result of the WillHalt test may be run through all >> sorts of calculations before ultimately controlling a halt or loop decision. >> >> The loop can be far subtler. It might, for example, be a search for the >> largest prime number. > > ******************************* > > So, how does WillHalt work if the program it is given is a Snobol > interpreter bound with a Snobol program that may, or may not, be > halting-equivalent to the program calling WillHalt? > > Or, for that matter, an interpreter for some new, unpublished, > programming language bound with a program in that language that may, or > may not, be halting-equivalent to the calling program? > > Patricia I will only proceed beyond this example, iff you agree that I have made my point with this example.
From: Peter Olcott on 20 Oct 2006 08:37 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh9gpc093(a)drn.newsguy.com... > Peter Olcott says... > >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote > >>> 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. > > No, it doesn't. > > -- > Daryl McCullough > Ithaca, NY > I have proven that it does, if you don't think that it does, then prove that it does not.
From: Peter Olcott on 20 Oct 2006 08:40
"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:eh9h070n5(a)drn.newsguy.com... > Peter Olcott says... > >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote > >>> 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). > > I don't feel bad, it's just that what you are saying > is wrong. > >>The correct answer to the question, also depends on the context >>of whom is being asked. > > No, it does not. > >>When you are asked the question there is a different correct >>answer than when WillHalt() is asked this same question. > > No, there is not. > >>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. > > Yes, there are questions whose answer depends on the > context, but the halting problem is not one of them. Merely an empty unsupported statement. I have proven my point, and you have failed to correctly point out the specific error of it. Now you are not even bothering to point out any errors, and have resorted to mere unsupported statements. > > -- > Daryl McCullough > Ithaca, NY > |