A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 20 Oct 2006 18:30 "Jens Auer" <jens.muaddib(a)googlemail.com> wrote in message news:1161379085.191236.24700(a)e3g2000cwe.googlegroups.com... > Peter Olcott schrieb: > >> I have already said this quite a few times in the ANALYTICAL COMMENTARY. Why >> don't you point out the precise point within the exact phrase of this >> ANALYTICAL >> COMMENTARY that you either fail to understand, or disagree with. >> >> WillHalt() performs the same sort of simulated execution trace that a human >> would use to unequivocally determine that it WILL indeed HALT. From this same >> sort of simulated execution trace it can obviously see (in the same way that >> a >> person can see) that providing this decision back to its caller is corrupted >> by >> its caller to change the result of the decision. > So, you can obviously see if a program terminates on any input? This is > great, I can't and if I need to show it, I have to prove it by hand (or > with the help of some semi-automated verification tool), but this is > not as simple as looking at it. > >> Because it can see this (in the same way that a person can see this), it can >> determine (in the same way that a person can determine) that even though it >> knows full well that it will halt, (thus is not undecidable) it can not >> provide >> this result back to its caller without the result becoming corrupted by the >> caller. > >> // 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. > So, if I get this correctly (without a precise in terms of source code > definition of MalignantSelfReference() this is more guessing than > reasoning.), WillHalt checks the source code it is given as argument > whether it is called somewhere, and the result is used to form the > contradiction. By this, you hope to avoid the constructed > counter-example. > But what do you do if I feed in the source code of LoopIfHalts, where I > replaced the call to WillHalt with another function (as a source code > entity, not a mathematical function) which has the same behaviour (in > computational terms, both program compute the same function)? Can your > magic function MalignantSelfReference() detect this? It makes no sense at all to attempt to generalize any point that is not yet made. I must restrict all of my responses to the single isolated example that I have provided, because of the inherent prerequisite order of my points. Only after this example is fully analyzed would it make any sense to proceed beyond this example. If I can't prove my point within the context of this single isolated example, then every other point becomes completely moot. > > Still, I would like to see a definition of MalignantSelfReference, even > as pseudo-code or as a mathematical definition for the set of programs > it decides. This would ease talking very much. >
From: Peter Olcott on 20 Oct 2006 18:53 <sillybanter(a)gmail.com> wrote in message news:oF5_g.21$A27.19(a)trnddc08... > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> <sillybanter(a)gmail.com> wrote in message news:TDYZg.3794$4T6.1422(a)trnddc02... >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> >> >> <sillybanter(a)gmail.com> wrote in message >> >> news:bnLZg.5347$NK5.1822(a)trnddc08... >> >> > In comp.theory Peter Olcott <NoSpam(a)seescreen.com> wrote: >> >> > >> >> >> So the equivalent of the return value of the Halt() function from >> >> >> the TM is the integer value that the TM's ReadWrite head rests on >> >> >> when the TM halts. In this case DOES_NOT_HALT=0 HALTS=1 >> >> >> MALIGNANT_SELF_REFERENCE=2. This scenario breaks out of the infinite >> >> >> recursion of the original specification of the problem, and provides >> >> >> the only possible correct answer. >> >> > >> >> > In the standard presentation of the halting problem, there is no >> >> > recursion, infinite or otherwise. Don't be confused by the fact that >> >> > the same name of a function is used in the analyzed program and in the >> >> > analyzer - it's not the same thing, and these two instances of >> >> > "Halt" are completely separate. >> >> >> >> See the ANALYTICAL COMMENTARY of this example mentioned below to see my >> >> current >> >> point. >> > >> >> ... >> > >> >> // 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. >> >> >> >> Therefore WillHalt() can determine that the question: >> >> "Does LoopIfHalts(LoopIfHalts) halt?" has no correct YES or NO >> >> answer, and is thus erroneously formed because it is asking a >> >> YES or NO question that has no correct YES or NO answer. >> > >> > Except that it, of course, DOES have a correct YES or NO answer. > >> So which of the correct YES or NO answers can WillHalt() provide >> such that it has provided the correct YES or NO answer? If you are >> correct, then you MUST be able to correctly select one of these, >> otherwise YOU ARE INCORRECT!!! THERE EXISTS NO CORRECT YES OR NO >> ANSWER THAT WillHalt() CAN POSSIBLY PROVIDE, THUS THIS HALTING >> PROBLEM IS MERELY THE CASE OF THE INABILITY TO CORRECTLY ANSWER AN >> ILL-FORMED QUESTION ENTIRELY DUE TO THE FACT THAT THE QUESTION >> ITSELF IS ILL-FORMED!!! > > If you really think about what you yourself just wrote there, you > would see that you've exactly described the contradiction that is the > heart of the halting problem proof, and hence you have proved that the > halting problem is undecidable. Right there is the error. This reasoning has not shown that the HP is undecidable. There is a subtle but crucial distinction between deciding the correct answer to a question, and providing a correct answer to a question. It is very possible to provide a correct answer without knowing it (guessing is possible), and it is also possible to know the correct answer without providing it. There is nothing at all that prevents WillHalt() from deciding the correct answer. > > Let me try to point this out as clearly as I can - you say "which of > the correct YES or NO answers can WillHalt() provide such that it has > provided the correct YES or NO answer?" The answer is NEITHER. That > doesn't mean that the answer doesn't exist just that this particular > algorithm (WillHalt) is wrong. That WillHalt doesn't "provide the > correct YES or NO answer" in no way, shape, or form implies that the > answer doesn't exist - just that this particular algorithm can't > determine it. > > You say "THERE EXISTS NO CORRECT YES OR NO ANSWER THAT WillHalt() CAN > POSSIBLY PROVIDE" - you're absolutely correct that WillHalt will > never, ever provide the correct input on this particular input. So > what? *Other* algorithms could take this exact same input (with the > WillHalt source code) and PROVIDE THE CORRECT ANSWER (we're typing in > all caps now I see). But they'll give the wrong answer on *other* > inputs. > > Here's another attempt at explaining it: we agree that WillHalt > doesn't return the right YES or NO answer. There are really only two > possibilities: > > 1) The problem is ill-formed and there is no correct answer. > 2) The problem is well-formed and WillHalt is wrong. > > The reason WillHalt fails is precisly because of #2. You argue that > the problem is ill-formed *because* WillHalt fails - that's a > completely bogus argument because of the (correct) possibility of #2. > > If the problem is ill-formed, then you should be able to describe why > that is so, without talking about how one particular algorithm > behaves. That algorithm not behaving well on a particular input just > means that the algorithm is wrong on that input. Other algorithms are > correct on that input, and so the problem is not ill-formed. > > So here's your specific challenge: try to argue that the problem is > ill-formed without relying on how one particular algorithm behaves on > one particular input, because that's falacious reasoning. I will make no attempt to generalize the single isolated example that I provided, because it would be fruitless to attempt to generalize any point not yet made. > > -- > > Steve Stringer > sillybanter(a)gmail.com >
From: Peter Olcott on 20 Oct 2006 18:55 "Chris Menzel" <cmenzel(a)remove-this.tamu.edu> wrote in message news:slrnejhtaf.297d.cmenzel(a)philebus.tamu.edu... > On Fri, 20 Oct 2006 08:27:32 -0500, Peter Olcott <NoSpam(a)SeeScreen.com> > said: >> >> <sillybanter(a)gmail.com> wrote in message >> news:nGYZg.3795$4T6.1868(a)trnddc02... >>>> Iff (if and only if) I can reach a consensus on this >>>> point, I will proceed to a UTM version of the same problem, and >>>> attempt to show the mathematical mapping from the prior example to >>>> the UTM example. I will not do this unless or until I have reached a >>>> consensus on my prior point. >>> >>> You will not get consensus on this point, because you're wrong, and >>> pretty much everyone here except you sees that quite clearly. >> >> Or, pretty much everyone here does not 100% completely grasp every >> subtle nuance of the complete meaning of my statements. > > Or not. :-) What are the odds, dude? > I think that the odds that the fundamental concept of truth is broken are far less than the odds of many people being confused for many decades.
From: Peter Olcott on 20 Oct 2006 18:59 "Daryl McCullough" <stevendarhyl3016(a)yahoo.com> wrote in message news:ehakta02j4r(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. > >>I have proven that it does > > No, you haven't. The way you described it, WillHalt will throw > a "MalignantSelfReferenceException", which is not correctly answering > the question. > If you were WillHalt() what correct answer would you provide? If someone corrupted your output mechanism by tying you up and taping your mouth shut, what correct answer would you provide? Does tying you up, and taping your mouth shut make the problem undecidable? > -- > Daryl McCullough > Ithaca, NY >
From: Patricia Shanahan on 20 Oct 2006 19:56
Peter Olcott wrote: > "Chris Menzel" <cmenzel(a)remove-this.tamu.edu> wrote in message > news:slrnejhtaf.297d.cmenzel(a)philebus.tamu.edu... >> On Fri, 20 Oct 2006 08:27:32 -0500, Peter Olcott <NoSpam(a)SeeScreen.com> >> said: >>> <sillybanter(a)gmail.com> wrote in message >>> news:nGYZg.3795$4T6.1868(a)trnddc02... >>>>> Iff (if and only if) I can reach a consensus on this >>>>> point, I will proceed to a UTM version of the same problem, and >>>>> attempt to show the mathematical mapping from the prior example to >>>>> the UTM example. I will not do this unless or until I have reached a >>>>> consensus on my prior point. >>>> You will not get consensus on this point, because you're wrong, and >>>> pretty much everyone here except you sees that quite clearly. >>> Or, pretty much everyone here does not 100% completely grasp every >>> subtle nuance of the complete meaning of my statements. >> Or not. :-) What are the odds, dude? >> > I think that the odds that the fundamental concept of truth is broken are far > less than the odds of many people being confused for many decades. There is nothing about the fundamental concept of truth that is broken by proof of undecidability of the Halting problem. Suppose we are given an arbitrary decision algorithm A. We don't know what A does. Maybe someone thinks it is a Halting problem decision algorithm. Maybe it was intended to decide if its input describes the combination of a traveling salesman problem and the total weight for a solution. Maybe we have no idea what, if anything, it was designed to do. We can supply an input that proves A is not a Halting problem decision algorithm. The input is the description of a computation (program and input). If that computation halts, it is an input A rejects. If that computation loops for ever, it is an input A accepts. We can do that for any decision algorithm A, so most of us deduce that there is no decision algorithm for the Halting problem. If you take the existence of a decision algorithm for the Halting problem as an axiom, while retaining the normal axioms that ultimately underly theory of computation, you end up with an inconsistent system of axioms. Even then, it is the set of axioms that is broken, not the fundamental concept of truth. Patricia |