A Possible "solution" to the Halting Problem
in [Theory]
|
From: Antti Valmari on 24 Oct 2006 09:20 I wrote: > Perhaps a week ago I posted in comp.theory a "no halting tester" proof > that goes along entirely different lines of thought from what has been > discussed. . . . Peter Olcott replied: > My recent response to Daryl presents my currently updated position within the > context of TM's. You say that the question Input: A Turing machine T and a character string S. Output: "yes" or "no" Question: Does T halt, if T is run given S as its input? is ill-formed. You say that "yes" and "no" do not suffice as the possible answers, there must be a third possibility. You came to this conclusion because of the trouble that a certain self-referencing construction caused. If the Turing machines under consideration are given no input (or are given the empty string as input), then self-reference is no more possible. Does the question remain ill-formed, in your opinion, if the Turing machine is given no input? That is, is the following question ill-formed: Input: A Turing machine T. Output: "yes" or "no" Question: Does T halt, if T is run given the empty string as its input? --- Antti Valmari ---
From: Peter Olcott on 24 Oct 2006 20:34 "Antti Valmari" <ava@.c.s...t.u.t...f.i.invalid> wrote in message news:ehl3ui$jsa$1(a)news.cc.tut.fi... > > I wrote: >> Perhaps a week ago I posted in comp.theory a "no halting tester" proof >> that goes along entirely different lines of thought from what has been >> discussed. . . . > > Peter Olcott replied: >> My recent response to Daryl presents my currently updated position within the >> context of TM's. > > You say that the question > > Input: A Turing machine T and a character string S. > Output: "yes" or "no" > Question: Does T halt, if T is run given S as its input? > > is ill-formed. You say that "yes" and "no" do not suffice as the > possible answers, there must be a third possibility. You came to this > conclusion because of the trouble that a certain self-referencing > construction caused. > > If the Turing machines under consideration are given no input (or > are given the empty string as input), then self-reference is no more > possible. Does the question remain ill-formed, in your opinion, if the > Turing machine is given no input? That is, is the following question > ill-formed: > > Input: A Turing machine T. > Output: "yes" or "no" > Question: Does T halt, if T is run given the empty string as its input? > > --- Antti Valmari --- > > Here is my most recently updated position: int WillHalt(string SourceCode, string InputData) { if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } void LoopIfHalts(string SourceCode) { if ( WillHalt(SourceCode, SourceCode) == TRUE ) while (TRUE) // loop forever ; else return; } LoopIfHalts(LoopIfHalts); An ill-formed question is defined as any question that does not have a correct answer in its required solution set. The question "How tall are you Blue or Green?" is ill-formed because neither Blue nor Green represent the (Numeric Quantity/Unit of Measure) pair required to correctly answer the question. The above representation of the Halting Problem also derives an ill-formed question because both possible return values of WillHalt() produce an incorrect result, and WillHalt() its solution set restricted to to these two machine states. This same problem can be stated in the form of a UTM that halts on one of two states, equivalent to the return value pair mentioned above. Conclusion: At least statements of the Halting Problem that directly correspond to the above methods derive nothing more than ill-formed questions.
From: Daryl McCullough on 24 Oct 2006 22:19 Peter Olcott says... >Here is my most recently updated position: > >int WillHalt(string SourceCode, string InputData) { > if ( TheProgramWillHalt(SourceCode, InputData) ) > return TRUE; > else > return FALSE; >} > >void LoopIfHalts(string SourceCode) { > if ( WillHalt(SourceCode, SourceCode) == TRUE ) > while (TRUE) // loop forever > ; > else > return; >} > >LoopIfHalts(LoopIfHalts); > >An ill-formed question is defined as any question that does not have a >correct answer in its required solution set. Part of the problem here, Peter, is that you are an idiot. You've been told, over and over again, that the correct answer to the question: Does LoopIfHalts(LoopIfHalts) halt is *FALSE* (under the assumption that WillHalt is partially correct). That's the *correct* answer. So there is a correct answer. You can even write a program that *gives* this correct answer. I gave you such a program: boolean WillHalt2(String p, String x) { if p=LoopIfHalts and x=LoopIfHalts then return FALSE otherwise return WillHalt(p,x) } That's a program that returns the correct answer. Why do you keep saying that the question doesn't have a correct answer? Yes, you can come up with another program, LoopIfHalts2, such that WillHalt2 fails to provide the right answer. But that's a *different* question. One question is: Does LoopIfHalts(LoopIfHalts) halt? The correct answer (assuming WillHalt is partially correct) is false. WillHalt fails to produce the answer, but WillHalt2 *correctly* produces it. Another question is: Does LoopIfHalts2(LoopIfHalts2) halt? The correct answer again is false. Neither WillHalt nor WillHalt2 correctly answers this question, but we can easily construct a third program, WillHalt3, which gets it right. -- Daryl McCullough Ithaca, NY
From: Charlie-Boo on 9 Nov 2006 21:50
Patricia Shanahan wrote: > Charlie-Boo wrote: > > Peter Olcott wrote: > >> The Halt program throws an "Invalid Input" exception. > >> This would be analogous to the hardware exception of an attempt to divide by > >> zero. > > > > Are you aware of the fact that the Clay Institute offers a $1 million > > reward for anyone who solves the Halting Problem? Alan Turing wasn't > > able to and nobody has ever solved it since (except when using a > > Computationally Based Logic). > > I was not aware of that. The list of millennium challenge problems at > http://www.claymath.org/millennium/ is: > > * Birch and Swinnerton-Dyer Conjecture > * Hodge Conjecture > * Navier-Stokes Equations > * P vs NP > * Poincaré Conjecture > * Riemann Hypothesis > * Yang-Mills Theory That's the list circulated to the average person. There is also an "advanced" list that only the most elite see, that contains much more difficult problems e.g. the Halting Problem. Turing admitted that he could not solve it, saying that for him the problem has been unsolvable. If you collect the reward, are you aware of the fact that I get a "finder's fee"? C-B > Patricia |