A Possible "solution" to the Halting Problem
in [Theory]
|
From: Aatu Koskensilta on 21 Oct 2006 01:31 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. -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: Jens Auer on 21 Oct 2006 04:44 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, 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.
From: Jens Auer on 21 Oct 2006 04:55 Peter Olcott schrieb: > int Greater(int X, int Y) { > if (X > Y) > return 1; // decided and provided > return 0; // decided and provided > } > > void Greater(int X, int Y) { > if (X > Y) > ; // decided, yet not provided > } You really should read some book about theoretical computer science and look up the basics. A decision function for a set, in this case the set Greater = {(x,y) | x > y} is a boolean function return true for all sets (x,y) \in Greater and false for all sets \not \in greater. Your second function is nothing. In fact, the decision function is the function ">", defined somehwhere else.
From: Jón Fairbairn on 21 Oct 2006 06:51 Patricia Shanahan <pats(a)acm.org> writes: > 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. I think this illustrates why reasoned argument is futile in this thread. The OP /does/ take the existence of a decision algorthm for the halting problem as an axiom. Consequently, working from his axioms he can reach any conclusion he wishes. -- Jón Fairbairn Jon.Fairbairn(a)cl.cam.ac.uk
From: Markus Triska on 21 Oct 2006 07:16
"Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > Specifically calling the HP undecidable, is the error. It least that terminology is a bit unfortunate, since HP is semi-decidable. An error would be to infer from its not being "totally" undecidable (like totality problem for TMs) that it's decidable. Best wishes! Markus Triska |