A Possible "solution" to the Halting Problem
in [Theory]
|
From: The Ghost In The Machine on 18 Oct 2006 00:01 In sci.logic, Peter Olcott <NoSpam(a)SeeScreen.com> wrote on Mon, 16 Oct 2006 01:40:42 -0500 <OPFYg.7971$eZ4.5217(a)dukeread06>: > > "The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message > news:5geb04-pa.ln1(a)sirius.tg00suus7038.net... >> In sci.logic, Peter Olcott >> <NoSpam(a)SeeScreen.com> >> wrote >> on Sun, 15 Oct 2006 22:40:02 -0500 >> <laDYg.7965$eZ4.1292(a)dukeread06>: >>> >>> "The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message >>> news:e7aa04-32t.ln1(a)sirius.tg00suus7038.net... >>>> In sci.logic, Peter Olcott >>>> <NoSpam(a)SeeScreen.com> >>>> wrote >>>> on Sun, 15 Oct 2006 12:38:39 -0500 >>>> <AmuYg.7908$eZ4.5473(a)dukeread06>: >>>>> >>>>> "The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message >>>>> news:vp2a04-lfs.ln1(a)sirius.tg00suus7038.net... >>>>>> In sci.logic, Peter Olcott >>>>>> <NoSpam(a)SeeScreen.com> >>>>>> wrote >>>>>> on Sun, 15 Oct 2006 09:19:52 -0500 >>>>>> <csrYg.7886$eZ4.2645(a)dukeread06>: >>>>>>> The Halt program throws an "Invalid Input" exception. >>>>>>> This would be analogous to the hardware exception of an attempt to divide >>>>>>> by >>>>>>> zero. >>>>>>> >>>>>> >>>>>> Useful, but slightly irrelevant. >>>>>> >>>>>> For purposes of this exercise I assume arrays of arbitrary >>>>>> objects, similar to Java, with a twist: Java does not >>>>>> have method/function pointers or closures. However, >>>>>> one can always use introspection in Java, in a pinch, >>>>>> or use a language such as LISP (which I'd have to look up >>>>>> the syntax for). >>>>>> >>>>>> The construct >>>>>> >>>>>> void weirdfun(arg) { >>>>>> while(HTest(arg[0], arg) == HALT) >>>>>> ; >>>>>> } >>>>>> >>>>>> appears to be a well-formed function, ready to be introduced >>>>>> as the func parameter in HTest(func, parameters). The second >>>>>> parameter to HTest is simply [weirdfun]. >>>>>> >>>>>> At some point HTest has to determine whether weirdfun([weirdfun]) >>>>>> halts. If weirdfun([weirdfun]) does halt, then HTest(weirdfun,[weirdfun]) >>>>>> returns HALT, and weirdfun([weirdfun]) provably loops in that case, >>>>>> calling HTest() uselessly again and again. >>>>>> >>>>>> If weirdfun([weirdfun]) loops, then HTest(weirdfun,[weirdfun]) will return >>>>>> something other than HALT, and weirdfun([wierdfun]) provably halts. >>>>>> >>>>>> In either case HTest() is computing the answer incorrectly; therefore >>>>>> HTest() cannot compute whether all functions halt (since we found >>>>>> one that it doesn't work on). >>>>> >>>>> HTest() correctly invokes the "Invalid Input" exception and neither returns >>>>> HALT >>>>> nor returns Not(HALT) >>>> >>>> OK. So now it fails the test of being an algorithm and always returning >>>> a correct result -- since it doesn't return any result at all. >>>> >>> In the exact same way and for the same kind of reason that the following >>> assignment statement would fail the criterion measure that you just >>> specified: >>> >>> double X = 50.0 / 0.0; >> >> At least there I can specify when the operation is invalid. If the >> divisor is zero or the quotient overflows then it traps. I'll >> refer you to the relevant literature for the microprocessor in >> question if you want to pursue this further. >> >>> >>>> Can't win that way! Besides, Turing Machines don't have exceptions as >>>> such. Nor have you specified precisely on how it will determine when to >>>> invoke that exception. >>> >>> It will invoke the exception in each and every case where the input is >>> determined to be invalid. >> >> And how is my input invalid? Please indicate the algorithm used to >> determine why my parameters to HTest >> >> HTest(weirdfun, [weirdfun]) >> >> are invalid. >> >>> Since a Turing machine is theoretically capable of >>> executing any computable algorithm (did I say this correctly?) therefore a >>> Turing machine would be capable of duplicating the sequence equivalent to >>> throwing an exception. We could for example adopt the simple protocol of >>> returning zero for Not(HALT) one for HALTS, and two for INVALID_INPUT. >> >> Nice try, but weirdfun() merely tests for HALT in the loop. >> If the algorithm returns any other value (including >> I_HAVE_NO_CLUE) the function will halt. If HTest throws >> an exception weirdfun() does not catch it, but a trivial >> modification: >> >> void weirdfun2(arg) { >> try >> { >> while(HTest(arg[0], arg) == HALT) >> ; >> } >> catch(Throwable t) >> { >> } >> } >> >> takes care of that. ("Throwable" is the root of all exceptions in Java. >> All this does is guarantee that weirdfun2 will not throw an exception, >> but will simply halt.) >> >> And now, of course, what does HTest(weirdfun2, [weirdfun2]) return? >> >> Admittedly, the contradiction is indeed lifted, since HTest() can throw >> an exception in this case -- which is the wrong answer, of course, but >> at least it gets out of contradiction territory. > > It is not the wrong answer, it is the only possible correct answer. It is the equivalent of a fourth-and-punt. Every implementation either halts, or it doesn't (though it may take a very long while in some cases!). We may not know whether it halts; one celebrated problem for instance is to determine whether unsigned CollatzCount(unsigned ix) { if(ix < 2) return 0; else if(ix mod 2 == 0) return 1 + CollatzCount(ix/2); else return 1 + CollatzCount(3*ix+1); } halts on all inputs, assuming indefinitely big unsigned integers. (AFAIK, the answer is currently unknown.) And then there's weirdfun(), of course. Other possibilities include boolean findTwoPrimes(unsigned sum, unsigned & p, unsigned & q) { for(p = 2; 2*p <= sum; p = nextPrime(p)) { q = sum - p; if(isPrime(q)) return true; } return false; } unsigned firstGoldbach() { unsigned e = 4; while(findTwoPrimes(e,p,q)) e += 2; return e; } which basically looks for the first even number that can't be represented as the sum of two primes -- the refutation of the Goldbach conjecture, if it exists. The halting algorithm would have to give an answer on these as well as weirdfun() -- or punt. Some of these we *do* know the answer to: unsigned largestPrime() { unsigned p = 3; while(notLargestPrime(p)) p = nextPrime(p); re
From: The Ghost In The Machine on 18 Oct 2006 00:18 In sci.logic, MoeBlee <jazzmobe(a)hotmail.com> wrote on 17 Oct 2006 17:41:25 -0700 <1161132085.275067.259900(a)e3g2000cwe.googlegroups.com>: > Peter Olcott wrote: >> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >> news:1161129027.125873.82790(a)f16g2000cwb.googlegroups.com... >> > Peter Olcott wrote: >> >> Malignant self-reference is the term that one of the respondents on this >> >> group >> >> provided for the self-reference in the halting problem. It is malignant in >> >> the >> >> sense that it is self-modifying program, that modifies itself in such a way >> >> as >> >> to prevent itself from functioning correctly. >> > >> > Which, has nothing to do with the halting problem. >> > >> > MoeBlee >> > >> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >> Are you saying that the root cause of the "Problem" aspect of the "Halting >> Problem" has nothing to do with self-reference? > > Define 'self-referential', 'malignantly self-referential', > 'self-modifying', and 'functioning correctly' as mathematical > predicates in the theory (or a theory) of which the unsolvability of > the halting probelm is a theorem. In the context of the halting problem the self-reference is in fact a self-meta-reference. Given an alleged implementation of the Halting Predicate HTest(func, args), one constructs a new function void WeirdFun(func) { while(HTest(func, [func]) == HALT) ; } If one prefers, one can use a templated form, which might look like: template <function HTest> void WeirdFun(func) { while(<HTest>(func, [func]) == HALT) ; } which means that for *any* alleged implementation of the halting tester, one can construct a function upon which it will yield an incorrect answer, namely, the call HTest(WeirdFun<HTest>, [WeirdFun<HTest>]). Now Peter has "solved" the Halting Problem by allowing this answer, or by punting. Neither is much of a solution. As for self-modifying -- no evidence of that here. All I've done is defined one function using another as a starting point. > > And please tell me what standard textbook(s) you use as your basic > reference for this subject so that I may consult those textbooks in > order to appreciate your understanding of the theorem and the subject. > > MoeBlee > -- #191, ewill3(a)earthlink.net Useless C++ Programming Idea #992398129: unsigned u; if(u < 0) ... -- Posted via a free Usenet account from http://www.teranews.com
From: Alan Smaill on 18 Oct 2006 05:46 "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > Are you saying that the root cause of the "Problem" aspect of the "Halting > Problem" has nothing to do with self-reference? The "problem" nomenclature is just the same as is used in the Travelling Salesman Problem. en.wikipedia.org/wiki/Traveling_salesman_problem The halting problem, just as with the TSP, is well-posed and unambiguous. -- Alan Smaill
From: Peter Olcott on 18 Oct 2006 08:01 "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message news:87lkneqm4p.fsf(a)bsb.me.uk... > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >> news:87slhmqpxw.fsf(a)bsb.me.uk... >>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>> >>>> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >>>> news:874pu2tqla.fsf(a)bsb.me.uk... >>>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>> >>>>>> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >>>>>> news:878xjetrqw.fsf(a)bsb.me.uk... >>>>>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>>>> >>>>>>>> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >>>>>>>> news:1161118961.027553.142520(a)f16g2000cwb.googlegroups.com... >>>>>>>>> Peter Olcott wrote: >>>>>>>>>> I will frame this in the terms of the Halting Problem because I >>>>>>>>>> understand >>>>>>>>>> computer science much more deeply than math. >>>>>>>>> >>>>>>>>> Say what you want about computer science, but the statement of the >>>>>>>>> unsolvability of the halting problem and the proof of the theorem are >>>>>>>>> perfectly formed mathematics; the statement of the theorem and the >>>>>>>>> proof are not "ill-formed" and is not analogous to division by zero, >>>>>>>>> which has to do with conditional definition and descriptions that do >>>>>>>>> not properly refer.. >>>>>>>>> >>>>>>>>> MoeBlee >>>>>>>>> >>>>>>>> >>>>>>>> The conclusion that a universal halt detector can not be constructed >>>>>>>> is incorrect. The proofs do not show that a universal halt-detector >>>>>>>> can not be constructed. The proofs only show that a universal >>>>>>>> halt-detector can not provide the results of its analysis in the >>>>>>>> case of malignant self-reference where the caller uses the results >>>>>>>> to change the outcome of the analysis. >>>>>>> >>>>>>> I am curious. Do think that repeatedly re-stating your >>>>>>> misunderstanding of the halting problem will persuade anyone? You >>>>>>> have said the same thing in various ways to everyone who has posted, >>>>>>> and they remain unmoved. Is it not time to start thinking that you >>>>>>> may be mistaken? If not, let me ask a deeper question. What *would* >>>>>>> start you thinking that you may be mistaken? >>>>>> >>>>>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>>>>> Are you saying that I am wrong when I am saying that self-reference is >>>>>> the root cause of the "problem" aspect of the "Halting Problem" ?? >>>>> >>>>> No, I did not say anything about that. I thought my questions were >>>>> quite clear. >>>>> >>>>> Now I am curious as to why you have answered so few of the direct >>>>> questions you have been asked. >>>>> >>>> I would have to first know the specific details that you would >>>> consider that I might be wrong about before I could begin to >>>> consider than I might be wrong. In other words it must be an item by >>>> item point for point complete dialogue. Blanket statements are >>>> useless. >>> >>> I'm not going to answer that because I will assume that you would >>> answer the same as I do below. Obviously, let me know if I am wrong >>> about this. >>> >>>> What would it take for you to think that you might be >>>> wrong? >>> >>> An alternate (presumably contradictry) theorem stated and proved. If >>> you have not got that far yet, and are simply unhappy about some other >>> proof, then tell us the theorem you have trouble with and say which >>> axiom or deductive step in its proof is at fault. That is how the >>> subject progresses. Anything less belongs in alt.waffle.computers. >> >> I am not using that model, I am using a model comparable to the above link. > > Ah, OK. I can now see why your are mistaken, but you have still not > answered either of my questions. Would seeing a proper proof of the > halting theorem change your mind? > > -- > Ben. Explain this proof within the context of the model that I provided.
From: Peter Olcott on 18 Oct 2006 08:19
"Patricia Shanahan" <pats(a)acm.org> wrote in message news:AjiZg.10941$Y24.524(a)newsread4.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message >> news:zGdZg.15330$UG4.11773(a)newsread2.news.pas.earthlink.net... >>> MoeBlee wrote: >>>> Peter Olcott wrote: >>>>> The conclusion that a universal halt detector can not be constructed is >>>>> incorrect. The proofs do not show that a universal halt-detector can not >>>>> be >>>>> constructed. The proofs only show that a universal halt-detector can not >>>>> provide >>>>> the results of its analysis in the case of malignant self-reference where >>>>> the >>>>> caller uses the results to change the outcome of the analysis. >>>> The proof is of a mathematical theorem. Whatever that has to do with a >>>> "universal halt detector", I'll leave you to you. Meanwhile, "malignant >>>> self-reference" has nothing to do with the mathematical theorem and >>>> proof. >>> "Malignant self-reference" is also, as far as I know, undefined in >>> computer science. >>> >>> Patricia >> >> Malignant self-reference is the term that one of the respondents on this >> group provided for the self-reference in the halting problem. It is malignant >> in the sense that it is self-modifying program, that modifies itself in such >> a way as to prevent itself from functioning correctly. > > Could you look at http://www.mtnmath.com/whatrh/node49.html and point to > the program that modifies itself? > > Note that the proof of undecidability of halting can be done using > Turing machines, which have separate, non-modifiable, storage for the > program. > > Patricia http://www.cprogramming.com/tutorial/computersciencetheory/halting.html Could you look at the above example, and point out how SELF-HALT is not self modifying? This is the model that I am using in my investigation. I have been a software developer for the last 22 years, but have never focused on the mathematical abstractions. All of my work has been practical application. |