A Possible "solution" to the Halting Problem
in [Theory]
|
From: Jens Auer on 21 Oct 2006 07:34 Peter Olcott schrieb: > > 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. It makes no sense discussing about a solution to a mathematically formulated problem without having the proposed solution completely available. If you want to solve the halting problem, formulate a function which correctly decides if any program terminates on all inputs. This must work with all programs, not just one example! Anyway, as others remarked, the prove that you cannot implement halt is not dependant on a specific halt-function but just assumes that there is one and shows that this leads to a contradiction.
From: Peter Olcott on 21 Oct 2006 09:26 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:ehc8vi0mee(a)drn.newsguy.com... > Peter Olcott says... > >>No you are wrong, this is not what the specification of the >>problem entails. LoopIfHalts() is never making any predictions >>what-so-ever. The reason that you are not seeing what I am >>saying is that you continue to make these tiny little >>errors, that make your whole conclusion come out wrong. > > No, I have no trouble seeing what you are saying, but I > see that it is nonsense. You really don't know what you > are talking about, Peter. See that you just did it again. You don't even try to understand what I am saying, you merely glance at a few words before forming your refutation. If you really attempted to understand what I was saying you would not make such a foolish mistake as saying that LoopIfHalts() predicts anything. I won't bother to read any of the rest of what you said until you address this single point. We must proceed exactly one micro point at a time, and refrain from diverging into tangents. > > The original proof of the unsolvability of the halting > problem was about Turing machines. It's not really important > that it be about Turing machines, but the clearest statement > uses programs that are *functional*. That means that the output > is a deterministic function of the inputs. No matter how the > function is called, it *always* returns the same outputs given > the same inputs. > > Such a functional program is not allowed to throw exceptions, > and it is not allowed to have its output depend on the context > in which it is called. > > It is clear that your trick cannot possibly work for such > programs. There can be no deterministic program Halt(p,x) such > that > > If p is the source code for a program that halts on input x, > then Halt(p,x) returns true. Otherwise, Halt(p,x) returns false. > > You agree with that right? The usual proof shows clearly that there > is no functional program Halt(p,x) that solves the halting problem? > Right? > > Now, what you are proposing is a *non-functional* program. > It does *not* return the same output given the same inputs. > The output that it produces depends on the context in which > it is called. So the usual proof doesn't apply to your type > of program. > > HOWEVER, it is clearly true that with ordinary programming languages, > anything that can be deterministically computed using non-functional > programs can also be computed using functional programs. The basic > idea is just to make all the dependencies of the non-functional > program explicit as arguments. So if there is no solution to the > halting problem using functional programs, then there is no solution, > period. Your excursion into nonfunctional programs makes *no* difference. > It makes the analysis more complicated, but it doesn't change the result. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 21 Oct 2006 09:33 "Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote in message news:ehc5st0fmv(a)drn.newsguy.com... > Peter Olcott says... > >>"Daryl McCullough" <stevendaryl3016(a)yahoo.com> wrote > >>> WillHalt is being asked to predict the behavior of another program, >>> LoopIfHalts. But what is LoopIfHalt doing? It's trying to predict >>> the behavior of WillHalt, so that it can do the opposite. Nobody >> >>No you are wrong, this is not what the specification of the problem >>entails. > > I'm talking about the normal statement and proof of the unsolvability > of the halting problem. That is off-topic, we can not correctly proceed to that topic until this topic has been fully addressed. There is a required prerequisite order. > In that proof, we assume that there is a program > Halt(p,x) which is purported to have the following behavior: > > If p is the code of a program which halts on input x, then > Halt(p,x) outputs true. Otherwise, Halt(p,x) outputs false. > > So clearly Halt is being asked to predict the behavior of program p. > > The way that LoopIfHalts is defined is as follows: > > LoopIfHalts(x) checks if Halt(x,x) returns false. If > Halt(x,x) returns true, then LoopIfHalts goes into > an infinite loop. > > So clearly, LoopIfHalts is dependent on the behavior of Halt, > and vice-versa. Which is not at all the same thing as saying that LoopIfHalts() itself is predictive. The only possible way for you to begin to understand what I am saying is if we both begin to use English as if it was itself a mathematical formalism. If we don't do this, then the truth will slip right past the otherwise imprecision of natural language. > >>LoopIfHalts() is never making any predictions what-so-ever. > > That's not true. It *first* must figure out whether WillHalt > returns true or false. You defined LoopIfHalts in terms of > WillHalt. The behavior of LoopIfHalts() is tied to the historical behavior of WillHalt() after the fact of the execution of WillHalt(), thus not predictive at all. Predictiveness is not transitive. > > -- > Daryl McCullough > Ithaca, NY >
From: Peter Olcott on 21 Oct 2006 09:35 "Aatu Koskensilta" <aatu.koskensilta(a)xortec.fi> wrote in message news:Egi_g.10440$SA.1402(a)reader1.news.jippii.net... > Peter Olcott wrote: >> In order to make it possible for me to make my point, I must insist that the >> conversation never digresses to tangents until the prerequisite point is >> made. I have already shown, and it is completely obvious that there is no >> possible correct YES or NO answer that WillHalt() can possibly provide. > > Sure. I agree. > > Let's dance. So can you see how this equally applies to the UTM versions of the HP? > > -- > 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 21 Oct 2006 10:00
"Jens Auer" <jens.muaddib(a)googlemail.com> wrote in message news:1161420276.228408.324100(a)h48g2000cwc.googlegroups.com... > > Peter Olcott schrieb: > >> > But then your MalignantSelfReference() is useless, since it would not >> >> No its not is proves the one prerequisite point so that we can then proceed >> to >> the next step. Once my point is proven within the specific context is this >> single isolated example, thenn (then and only then) we can proceed to >> generalize >> this point. There is no sense in generalizing any point that is not yet made. > Sorry, I am confused. What is your prerequisite point? I thought you > want to give a solution to the halting problem. The Halting Problem is > defined to give an answer for all programs, not just to recognize one > function and say YES or NO for this function. > Nevertheless, I am still waiting for your complete code with > MalignantSelfReference. Giving just a verbal story describing the > function is not enough. I am quite sure that such a funciton cannot > exist, If your claim is that you do not see how such a function could be written in generally, then this question would be off topic until the prerequisite point is fully made, meaning a consensus of agreement on the correct conclusion drawn from this single isolated example, otherwise: If you claim to not see that within the context of the single isolated example that I provided, it is completely obvious that the problem is specified such that LoopIfHalts() toggles the result of WillHalt() to falsify the result of WillHalt() (Malignant-Self-Reference (MSR)) you would either be dishonest or lack sufficient knowledge to effectively communicate on this topic. If you are going to require me to write a parser and knowledge base showing that a program could be written to determine the case of malignant self-reference just described, then I must ask you to first provide a map of your brain showing exactly how each neuron in said brain derives this absurd requirement. > and many people have given examples for funciton where your > magical MalignantSelfReference fails, which you ignored. > > PS: If it help, make the assumption your point is taken (I don't > comply, but it doesn't matter) and generalize MalignantSelfReference > and show us your definition. > |