A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 16 Oct 2006 02:40 "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. > > 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.
From: Peter Olcott on 16 Oct 2006 03:32 "Rupert" <rupertmccallum(a)yahoo.com> wrote in message news:1160975938.946169.291050(a)i3g2000cwc.googlegroups.com... > > 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. > It can determine that each and every program that HALTS does indeed HALT, yet can not always provide this determination as a return value. This is not at all the same thing as correctly concluding that its capabilities are inherently limited, only its communication protocol is limited. It knows that the program HALTS, and merely must refrain from saying that the program HALTS, because saying that the program HALTS provides a different execution trace, thus a different program, and therefore a different end result.
From: William Elliot on 16 Oct 2006 04:11 On Mon, 16 Oct 2006, Peter Olcott wrote: > "William Elliot" <marsh(a)hevanet.remove.com> wrote in message > > 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. > So what? Computer programs already check to prevent division by zero.
From: on 16 Oct 2006 04:33 In article <NbuYg.7907$eZ4.275(a)dukeread06>, "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > ><mareg(a)mimosa.csv.warwick.ac.uk> wrote in message >news:egto14$b1d$1(a)wisteria.csv.warwick.ac.uk... >> In article <QSsYg.7900$eZ4.333(a)dukeread06>, >> "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? >> >> Derek Holt. > >It is not an equation, the "=" sign is an assignment operator in computer >science. In that case why not remove the ambiguity by using ":=" ? Since the RHS of the assignment is not defined, the assignment fails. Derek Holt.
From: Peter Olcott on 16 Oct 2006 08:12
"William Elliot" <marsh(a)hevanet.remove.com> wrote in message news:Pine.BSI.4.58.0610160110200.2981(a)vista.hevanet.com... > On Mon, 16 Oct 2006, Peter Olcott wrote: >> "William Elliot" <marsh(a)hevanet.remove.com> wrote in message >> > 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. >> > So what? Computer programs already check to prevent division by zero. It shows that the specified requirements of [the test of being an algorithm] also equally apply to the simple mathematical operation of division. This would mean that if this test is valid, then even the simple operation of division fails [the test of being an algorithm] . Because of this I would conclude that either [the test of being an algorithm] is not a valid test, or the definition of the term [algorithm] may be less useful than presupposed. |