A Possible "solution" to the Halting Problem
in [Theory]
|
From: The Ghost In The Machine on 16 Oct 2006 01:00 In sci.logic, Peter Olcott <NoSpam(a)SeeScreen.com> wrote on Sun, 15 Oct 2006 22:53:48 -0500 <fnDYg.7967$eZ4.986(a)dukeread06>: > > "Peter Olcott" <NoSpam(a)SeeScreen.com> wrote in message > news: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; > > P.S. although this is typically implemented at the CISC assembly language level > as a single machine instruction, there are numerous micro code instructions that > implement this instruction, thus it would be construed as an algorithm. Point taken but mostly irrelevant for the halting problem. :-) > >> >>> 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. 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. >> >>> >>>> >>>>> >>>>> If one doesn't like mu-loops, an alternate formulation is: >>>>> >>>>> weirdfun(arg) { >>>>> if(HTest(arg[0], arg) == HALT) >>>>> weirdfun(arg); >>>>> } >>>>> >>>>> which is almost identical except that the stack gets arbitrarily large >>>>> during execution. >>>>> >>>>> Perhaps you have an idea as to how "Invalid Input" can be implemented? >>>>> Best I can do is to have HTest() look for self-references, but that >>>>> won't help much as one can make a trivial modification to HTest(), >>>>> yielding HTest'(), by e.g. declaring an extra local variable which >>>>> is uninvolved in the algorithm, or printing out extra debug statements. >>>>> >>>>> Same operation, different function, HTest() lets the wight in, and >>>>> fails. >>>>> >>>>> -- >>>>> #191, ewill3(a)earthlink.net >>>>> Useless C++ Programming Idea #992381111: >>>>> while(bit&BITMASK) ; >>>> >>>> >>> >>> >>> -- >>> #191, ewill3(a)earthlink.net >>> Useless C++ Programming Idea #7878218: >>> class C { private: virtual void stupid() = 0; }; >> >> > > -- #191, ewill3(a)earthlink.net Evil? Were I evil, I'd eat you *first*. :-)
From: William Elliot on 16 Oct 2006 01:14 On Sun, 15 Oct 2006, Peter Olcott wrote: > <mareg(a)mimosa.csv.warwick.ac.uk> wrote in message > > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >>X = 50.0 / 0.0 > >>Is this an unsolvable problem or an ill-formed problem? > > > > I cannot see a problem there at all, just an equation with an undefined RHS. > > What is the problem exactly? > > What is the value of X? > Just like he told you, X doesn't have a value.
From: Rupert on 16 Oct 2006 01:18 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. The set of programs which the program claimed to halt, the set of programs which the program claimed to not halt, and the set of programs for which the program threw the exception would all have to be recursive. Hopefully the program would be sound, so that all the programs which the program claimed to halt would actually halt. So the set of programs which the program claimed to halt would be a recursive subset of the set of programs which do actually halt. This would mean there are some programs which do actually halt, but the program can't tell this.
From: Peter Olcott on 16 Oct 2006 02:30 "William Elliot" <marsh(a)hevanet.remove.com> wrote in message news:Pine.BSI.4.58.0610152213330.1333(a)vista.hevanet.com... > On Sun, 15 Oct 2006, Peter Olcott wrote: >> <mareg(a)mimosa.csv.warwick.ac.uk> wrote in message >> > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> >>X = 50.0 / 0.0 >> >>Is this an unsolvable problem or an ill-formed problem? >> > >> > I cannot see a problem there at all, just an equation with an undefined >> > RHS. >> > What is the problem exactly? >> >> What is the value of X? >> > Just like he told you, X doesn't have a value. Which is the same result obtained from Halt() when it throws the INVALID_INPUT exception. It neither returns HALTS, nor NOT_HALTS.
From: Peter Olcott on 16 Oct 2006 02:37
"The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message news:uheb04-pa.ln1(a)sirius.tg00suus7038.net... > In sci.logic, Peter Olcott > <NoSpam(a)SeeScreen.com> > wrote > on Sun, 15 Oct 2006 22:53:48 -0500 > <fnDYg.7967$eZ4.986(a)dukeread06>: >> >> "Peter Olcott" <NoSpam(a)SeeScreen.com> wrote in message >> news: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; >> >> P.S. although this is typically implemented at the CISC assembly language >> level >> as a single machine instruction, there are numerous micro code instructions >> that >> implement this instruction, thus it would be construed as an algorithm. > > Point taken but mostly irrelevant for the halting problem. :-) It shows the simple mathematical operation of division, also It shows that your specified requirements of [the test of being an algorithm] also equally applies to the simple mathematical operation of division. > >> >>> >>>> 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. 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. >>> >>>> >>>>> >>>>>> >>>>>> If one doesn't like mu-loops, an alternate formulation is: >>>>>> >>>>>> weirdfun(arg) { >>>>>> if(HTest(arg[0], arg) == HALT) >>>>>> weirdfun(arg); >>>>>> } >>>>>> >>>>>> which is almost identical except that the stack gets arbitrarily large >>>>>> during execution. >>>>>> >>>>>> Perhaps you have an idea as to how "Invalid Input" can be implemented? >>>>>> Best I can do is to have HTest() look for self-references, but that >>>>>> won't help much as one can make a trivial modification to HTest(), >>>>>> yielding HTest'(), by e.g. declaring an extra local variable which >>>>>> is uninvolved in the algorithm, or printing out extra debug statements. >>>>>> >>>>>> Same operation, different function, HTest() lets the wight in, and >>>>>> fails. >>>>>> >>>>>> -- >>>>>> #191, ewill3(a)earthlink.net >>>>>> Useless C++ Programming Idea #992381111: >>>>>> while(bit&BITMASK) ; >>>>> >>>>> >>>> >>>> >>>> -- >>>> #191, ewill3(a)earthlink.net >>>> Useless C++ Programming Idea #7878218: >>>> class C { private: virtual void stupid() = 0; }; >>> >>> >> >> > > > -- > #191, ewill3(a)earthlink.net > Evil? Were I evil, I'd eat you *first*. :-) |