A Possible "solution" to the Halting Problem
in [Theory]
|
From: on 15 Oct 2006 12:35 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.
From: Aatu Koskensilta on 15 Oct 2006 12:58 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. When exactly does the hypothetical Halt program throw this exception? That is, what is the computable property of the program text the Halt program uses to detect invalid input? Oh well, I guess we're in for another thousand message crank fest. -- Aatu Koskensilta (aatu.koskensilta(a)xortec.fi) "Wovon man nicht sprechen kann, daruber muss man schweigen" - Ludwig Wittgenstein, Tractatus Logico-Philosophicus
From: The Ghost In The Machine on 15 Oct 2006 13:00 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). 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: Peter Olcott on 15 Oct 2006 13:16 <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. What is the value of X?
From: Peter Olcott on 15 Oct 2006 13:27
<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. |