A Possible "solution" to the Halting Problem
in [Theory]
|
From: Ben Bacarisse on 20 Oct 2006 02:01 "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > The Halt program throws an "Invalid Input" exception. > This would be analogous to the hardware exception of an attempt to divide by > zero. For those of you joining this giant thread, I offer a summary, Please correct my inevitable misunderstandings. The OP suggests only a possible "solution" (note the quotes) because I suspect he does not believe it either. All discussion has been obliged to avoid mathematics as this is so precise that it introduces inaccuracies when the results are mapped to the "real world". After several heroic attempts to get his ideas pinned down (by others), it seems to me that he has, possibly[1], solved another problem which I will call the Peter Olcott Problem (POP): Given a program P and input I, return one of {yes, no, <third way>}. "Yes" (and "no") are only to returned when P halts (or not) on input I. The <third way> is not yet entirely resolved. Regular readers will not be surprised by this, as it is well know that POP is solvable. In fact there are an infinity of programs (we are obliged to avoid the formality of Turing Machines) that can solve it, ranging from the trivial: HALTish(P, I) return maybe; through versions for with "maybe" is returned for fewer and fewer (P, I) pairs. No interesting claim has yet been made about the measure of the set of (P, I) for which "maybe" is returned ("empty" and "finite" would both be worth a paper). Oh, and we should not feel to bad about being wrong. Lots of people have been wrong about this over the past 70 years. [1] I say possibly because without any formal definitions it almost impossible to say. -- Ben.
From: Jens Auer on 20 Oct 2006 03:51 Peter Olcott schrieb: > // ANALYTICAL COMMENTARY > WillHalt() is provided with the source code of LoopIfHalts(), as > input, so 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. Would you be so kind and show us how WillHalt accomplishes this, in a more precise form than a verbal comment? It all comes down to you definition of MalignantSelfReference, which I believe is itself undecidable.
From: Patricia Shanahan on 20 Oct 2006 04:27 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
From: Jack Campin - bogus address on 20 Oct 2006 06:11 "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. ============== j-c ====== @ ====== purr . demon . co . uk ============== Jack Campin: 11 Third St, Newtongrange EH22 4PU, Scotland | tel 0131 660 4760 <http://www.purr.demon.co.uk/jack/> for CD-ROMs and free | fax 0870 0554 975 stuff: Scottish music, food intolerance, & Mac logic fonts | mob 07800 739 557
From: Aatu Koskensilta on 20 Oct 2006 06:37
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. -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus |