A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 17 Oct 2006 11:05 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:zRXYg.10503$Y24.7729(a)newsread4.news.pas.earthlink.net... > Peter Olcott wrote: >> "Patricia Shanahan" <pats(a)acm.org> wrote in message >> news:_FWYg.7998$Lv3.6750(a)newsread1.news.pas.earthlink.net... >>> Peter Olcott wrote: >>>> "Patricia Shanahan" <pats(a)acm.org> wrote in message >>>> news:hHTYg.7886$Lv3.7266(a)newsread1.news.pas.earthlink.net... >>>>> Peter Olcott wrote: >>>>>> "Patricia Shanahan" <pats(a)acm.org> wrote in message >>>>>> news:qfOYg.14496$UG4.1437(a)newsread2.news.pas.earthlink.net... >>>>>>> Peter Olcott wrote: >>>>>>> .... >>>>>>>> To frame the exception handling mechanism within the historical context >>>>>>>> of a Turing Machine we only need to establish three integer values >>>>>>>> mapped to three different semantic meanings: >>>>>>>> 0=NOT_HALTS 1=HALTS 2= INVALID_INPUT. The input is invalid in each >>>>>>>> and every case where providing the result of the determination of >>>>>>>> halting derives a different execution trace, thus changing the result. >>>>>>> Yes, but what is the algorithm for determining whether the result of the >>>>>>> determination of halting derives a different execution trace? >>>>>> You have it incorrectly, the result does not provide a different >>>>>> execution trace. It is the act of providing this result that derives the >>>>>> different execution trace. Halt() can determine that the test program >>>>>> will halt, it merely can not provide the results of this determination to >>>>>> the caller in this case. Halt() determines that providing the results of >>>>>> its correct and complete analysis is used to alter the execution trace, >>>>>> thus forming a different execution trace than the one that is the subject >>>>>> of the test. >>>>> Are you saying that the behavior of the algorithm depends on what its >>>>> caller is going to do with the result? If so, that is a far bigger change >>>>> in the concept of algorithm than merely adding exceptions. >>>> The difficulty of the Halting Problem is that because of its infinitely >>>> recursive structure it is very difficult to see that the typical common >>>> sense assumptions that apply to nearly every other algorithm do not apply >>>> to this one. One of the most significant aspects of this atypical case, is >>>> that in the very unusual case of the Halting Problem, a function can see >>>> exactly how it is being called, and the effects of any actions that it >>>> takes upon its own caller. >>>> >>>> Within the specification of the Halting Problem, the Halt() function and >>>> its caller combined together form the program under test. In this case the >>>> behavior of one of the constituent parts (the Halt() function) forms the >>>> basis for the behavior of the other constituent part (the caller). Since >>>> this structure is directly presented to the Halt() function as input, the >>>> Halt() function can see exactly what its caller intends to do with any >>>> result that it provides (or actions that it takes). >>>> >>>> So the Halt() function breaks out of this otherwise infinitely recursive >>>> structure and provides the only possible correct answer given the >>>> specification of this problem: it throws the INVALID_INPUT exception. The >>>> Turing Machine equivalent of this would be halting with the ReadWrite Head >>>> of its tape positioned at a token indicating the semantic meaning of >>>> INVALID_INPUT. >>> I'm not sure whether all that means "yes" or "no". >> >> >> Are you saying that the behavior of the algorithm depends on what its caller >> is going to do with the result? >> >> Yes! In the atypical instance of the Halting Problem the called can know in >> advance both that its actions will effect the caller, and exactly how its >> actions will effect the caller. Because it has this information in advance it >> can decide what to do about it, and thereby effect the total outcome. > > HOW does h know "exactly how its actions will affect this caller"? All > it knows is its caller has fed it a number, and asked "Is this the > Goedel number of a computation that halts?". We know that the TM in that > computation uses a copy of h as part of its source code, but it could be > obfuscated. // // To make the problem more clear we are assuming: // (a) a purely interpreted language // (b) function call syntax results in inline expansion, // thus specifying the name of a function specifies // the body of the function. // void LoopIfHalts(string SourceCode) { if ( WillHalt(SourceCode, SourceCode) == TRUE ) while (TRUE) // loop forever ; else return; } int WillHalt(string SourceCode, string InputData) { if (NotValid(SourceCode, InputData)) throw(INVALID_INPUT); if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } LoopIfHalts(LoopIfHalts); Within the context of this framework WillHalt() can see how it will be called when the SourceCode of LoopIfHalts is fed to it as input, and thus see in advance how its return value will used for malignant self-reference. Because it can see this in advance, it can decide in advance what to do about it. > > >> >>> To try to understand, I'd like to nail down some terminology and program >>> names. http://www.mtnmath.com/whatrh/node49.html contains a simplified >>> version of the proof. >>> >>> Could you explain, in the terminology of that page, how h would detect a >>> situation in which it should throw the exception. >>> >>> Patricia >>
From: Charlie-Boo on 17 Oct 2006 12:14 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. Are you aware of the fact that the Clay Institute offers a $1 million reward for anyone who solves the Halting Problem? Alan Turing wasn't able to and nobody has ever solved it since (except when using a Computationally Based Logic). (I think Chaitin came closest by using a special number that vaporizes as soon as you so much as think about it. Bit # N = whether or not I will prove that I am not thinking about Chaitin at point in time N in the future. (I hope I get all zeros.)) C-B -HALT(I,J)* The Halting Problem is Unsolvable 1. NO(x,x) Known 2. HALT(I,J)* PREMISE 3. HALT(I,I)* SUB 2 4. ~HALT(I,I)* NOT 3 5. ~HALT(X,X) TRUE (THM) Peano 4 6. NO(X,X)v~HALT(X,X) UNION 1,5 7. ~YES(X,X) LIne 6 given CONS qed -~YES(x,x) is the Incompleteness Axiom - more generally -~P/P where general CBL is M # P / Q and the Theory of Computation is - X / YES : output all non-r.e. sets. Also X / YES : Output all r.e. sets. -~YES(x,x) The set of programs that don't halt yes on themselves is not r.e. 1. ~YES(x,x) Premise 2. M # ~YES(x,x) There must be a program that enumerates the set. 3. YES(M,a) , ~YES(a,a) A1 expr => DEF (syntax) 4. YES(M,M) , ~YES(M,M) SUB 3 5. P , ~P SUB 4 qed -P,~P is a basic axiom.
From: Peter Olcott on 17 Oct 2006 12:32 "Charlie-Boo" <shymathguy(a)gmail.com> wrote in message news:1161101671.273314.18520(a)h48g2000cwc.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. > > Are you aware of the fact that the Clay Institute offers a $1 million > reward for anyone who solves the Halting Problem? Alan Turing wasn't > able to and nobody has ever solved it since (except when using a > Computationally Based Logic). > > (I think Chaitin came closest by using a special number that vaporizes > as soon as you so much as think about it. Bit # N = whether or not I > will prove that I am not thinking about Chaitin at point in time N in > the future. (I hope I get all zeros.)) > > C-B > > -HALT(I,J)* The Halting Problem is Unsolvable > 1. NO(x,x) Known > 2. HALT(I,J)* PREMISE > 3. HALT(I,I)* SUB 2 > 4. ~HALT(I,I)* NOT 3 > 5. ~HALT(X,X) TRUE (THM) Peano 4 > 6. NO(X,X)v~HALT(X,X) UNION 1,5 > 7. ~YES(X,X) LIne 6 given CONS > qed > > -~YES(x,x) is the Incompleteness Axiom - more generally -~P/P where > general CBL is M # P / Q and the Theory of Computation is - X / YES : > output all non-r.e. sets. Also X / YES : Output all r.e. sets. > > -~YES(x,x) The set of programs that don't halt yes on themselves is > not r.e. > 1. ~YES(x,x) Premise > 2. M # ~YES(x,x) There must be a program that enumerates the set. > 3. YES(M,a) , ~YES(a,a) A1 expr => DEF (syntax) > 4. YES(M,M) , ~YES(M,M) SUB 3 > 5. P , ~P SUB 4 > qed > > -P,~P is a basic axiom. > Here is my closest approximation so far. // // To make the problem more clear we are assuming: // (a) a purely interpreted language // (b) function call syntax results in inline expansion, // thus specifying the name of a function specifies // the text body of the function. // void LoopIfHalts(string SourceCode) { if ( WillHalt(SourceCode, SourceCode) == TRUE ) while (TRUE) // loop forever ; else return; } int WillHalt(string SourceCode, string InputData) { if (NotValid(SourceCode, InputData)) throw(INVALID_INPUT); if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } LoopIfHalts(LoopIfHalts); The INVALID_INPUT exception indicates that WillHalt() has detected a case of malignant self-reference where the result of its analysis is fed back into the analysis to change the result. This does not indicate that WillHalt() is unable to correctly derive the halt status of the universal set of programs. It only means that there exists at least one malignant case of self-reference where it can not provide the results of its correct and complete analysis as a return value.
From: Dr A. N. Walker on 17 Oct 2006 12:23 In article <Vt5Zg.8306$eZ4.1179(a)dukeread06>, Peter Olcott <NoSpam(a)SeeScreen.com> wrote: > [...] If one takes the historical definition of the problem >artificially constrained to providing a Boolean result, then one can correctly >conclude that a case can be constructed such that a Halt() function can not >provide a correct Boolean result. It can not provide a correct Boolean result >specifically because of the malignant self referential structure of the problem. It isn't the Halting Problem itself that is "malignant" or "self- referential", not anyway in its usual formulation or the related proofs. Rather, it is one *specific* instance of a very similar problem, constructed so as to "bust" a *specific* purported "Halt()" function. For each potential "Halt()" function, there exists a corresponding buster; the conclusion is that no such function can be correct. >The inability to provide a correct Boolean result has been misconstrued to mean >that there are some problems that can never be solved, because there exists a >case of malignant self-reference where a correct Boolean result can not be >provided. There is no specific instance of the HP that can never be solved, for an emulator that ran for sufficiently long would solve it; sadly, "sufficiently long" is not computable by means of a fixed, specific algorithm [otherwise the HP would be solvable]. Also there is no great difficulty in providing the correct results for the "buster" instances. The problem is that the "busted" solver cannot itself do this; and if you write bigger and better solvers that can, then they in turn have bigger and better "busters" that they cannot resolve. Whether allowing more results is interesting or helpful is quite another matter. But it is not going to resolve the fundamental problem underlying the HP -- that there is only a limited amount of information that a specific program/algorithm [within the limitations of computing and programming as usually understood] can determine about programs in general, and that this information cannot reliably include such things as whether or not the program halts, whether control ever passes to line 123, whether it ever prints "Hello, world!", whether it ever reads from its input [in the usual, not the Turing Machine, sense], and so on. This is quite different from asking about some specific program, for which these questions [in particular] can all be answered. Indeed, they can all be answered by a quite simple program. But you may, in practice, have to wait beyond the heat death of the Universe -- not a problem for mathematics, only for mathematicians [and other real people]. -- Andy Walker, School of MathSci., Univ. of Nott'm, UK. anw(a)maths.nott.ac.uk
From: Patricia Shanahan on 17 Oct 2006 12:55
Charlie-Boo wrote: > 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. > > Are you aware of the fact that the Clay Institute offers a $1 million > reward for anyone who solves the Halting Problem? Alan Turing wasn't > able to and nobody has ever solved it since (except when using a > Computationally Based Logic). I was not aware of that. The list of millennium challenge problems at http://www.claymath.org/millennium/ is: * Birch and Swinnerton-Dyer Conjecture * Hodge Conjecture * Navier-Stokes Equations * P vs NP * Poincar? Conjecture * Riemann Hypothesis * Yang-Mills Theory Patricia |