A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 15 Oct 2006 13:38 "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) > > 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) ;
From: The Ghost In The Machine on 15 Oct 2006 15:00 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. 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. > >> >> 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; };
From: Peter Olcott on 15 Oct 2006 23:40 "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; > 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; };
From: Peter Olcott on 15 Oct 2006 23:53 "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. > >> 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; }; > >
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: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. Of course, one implementation of HTest() is a simple one: enum {HALT, LOOP} HTest(function, arguments) throws CannotDetermineException { throw new CannotDetermineException(function + "(" + arguments + ")"); } which is about as useful as a tricycle with three broken wheels, but does satisfy the criteria for a limited halting function. So precisely which problem are you trying to solve here? > >> >>> >>>> >>>> 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 Linux. Because vaporware only goes so far. |