A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 18 Oct 2006 08:22 "Alan Smaill" <smaill(a)SPAMinf.ed.ac.uk> wrote in message news:fwezmbu0xdj.fsf(a)collins.inf.ed.ac.uk... > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >> Are you saying that the root cause of the "Problem" aspect of the "Halting >> Problem" has nothing to do with self-reference? > > > The "problem" nomenclature is just the same as is used in > the Travelling Salesman Problem. > > en.wikipedia.org/wiki/Traveling_salesman_problem > > The halting problem, just as with the TSP, is well-posed and unambiguous. > > -- > Alan Smaill http://www.cprogramming.com/tutorial/computersciencetheory/halting.html None-the-less it is this mode that I am using in my investigation. I understand Turing Machines, and UTM's, both of these would mathematically map to this alternative model.
From: Peter Olcott on 18 Oct 2006 08:31 "The Ghost In The Machine" <ewill(a)sirius.tg00suus7038.net> wrote in message news:10mg04-kc6.ln1(a)sirius.tg00suus7038.net... > In sci.logic, Peter Olcott > <NoSpam(a)SeeScreen.com> > wrote > on Tue, 17 Oct 2006 11:32:53 -0500 > <UA7Zg.8314$eZ4.3841(a)dukeread06>: >> >> "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. >> > > OK. And what's to prevent LoopIfHalts from using a nearly exact *copy* of > TheProgramWillHalt() in its implementation? There's an indefinite > number of modifications to a program that can be contemplated -- if > nothing else, one can assign an arbitrary number to an unused local > variable. Only the outmost WillHalt() function needs to throw the INVALID_INPUT exception. This exception could also be called MALIGNANT_SELF_REFERENCE_DETECTED. In any case WillHalt() will know that itself halts, and when it does halt, it does provide the only possible correct answer. The only possible correct answer equally applies, regardless of what its caller does with this answer. > > But there are a fair number of other modification methods: loop > unrolling, variable name changes, using an int where a boolean > would be sufficient, exchanging leftshift and * or rightshift and /, > bitflipping > > v2 = v XOR 2^n > > versus > > if(floor(v / 2^n) mod 2 == 0) then v2 = v + 2^n; else v2 = v - 2^n; > > etc. > > -- > #191, ewill3(a)earthlink.net > Useless C++ Programming Idea #992398129: > unsigned u; if(u < 0) ... > > -- > Posted via a free Usenet account from http://www.teranews.com >
From: Patricia Shanahan on 18 Oct 2006 09:02 Peter Olcott wrote: > "Patricia Shanahan" <pats(a)acm.org> wrote in message > news:AjiZg.10941$Y24.524(a)newsread4.news.pas.earthlink.net... >> Peter Olcott wrote: >>> "Patricia Shanahan" <pats(a)acm.org> wrote in message >>> news:zGdZg.15330$UG4.11773(a)newsread2.news.pas.earthlink.net... >>>> MoeBlee wrote: >>>>> Peter Olcott wrote: >>>>>> The conclusion that a universal halt detector can not be constructed is >>>>>> incorrect. The proofs do not show that a universal halt-detector can not >>>>>> be >>>>>> constructed. The proofs only show that a universal halt-detector can not >>>>>> provide >>>>>> the results of its analysis in the case of malignant self-reference where >>>>>> the >>>>>> caller uses the results to change the outcome of the analysis. >>>>> The proof is of a mathematical theorem. Whatever that has to do with a >>>>> "universal halt detector", I'll leave you to you. Meanwhile, "malignant >>>>> self-reference" has nothing to do with the mathematical theorem and >>>>> proof. >>>> "Malignant self-reference" is also, as far as I know, undefined in >>>> computer science. >>>> >>>> Patricia >>> Malignant self-reference is the term that one of the respondents on this >>> group provided for the self-reference in the halting problem. It is malignant >>> in the sense that it is self-modifying program, that modifies itself in such >>> a way as to prevent itself from functioning correctly. >> Could you look at http://www.mtnmath.com/whatrh/node49.html and point to >> the program that modifies itself? >> >> Note that the proof of undecidability of halting can be done using >> Turing machines, which have separate, non-modifiable, storage for the >> program. >> >> Patricia > > http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > Could you look at the above example, and point out how SELF-HALT is not self > modifying? This is the model that I am using in my investigation. I have been a > software developer for the last 22 years, but have never focused on the > mathematical abstractions. All of my work has been practical application. > > Are we looking at the same place? The SELF-HALT I found there definitely does not modify itself, unless the DOES-HALT algorithm involves self modification: SELF-HALT(program) { if(DOES-HALT(program, program)) infinite loop else halt } Note that in the actual proof "program" is an integer that encodes the code for the program, so nobody is operating on the running copy. You can also, less formally, think of it as being the ASCII encoding of the program source code. It is just a string. In any case, the proof can be done using Turing machines, which are inherently incapable of self-modification, so it does not in any way depend on self-modification. I don't see the relevance of the length of time you have been a software developer to the validity of your ideas. Normally, quality of thinking and writing matters far more than background in newsgroups. Patricia
From: Alan Smaill on 18 Oct 2006 10:48 "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > "Alan Smaill" <smaill(a)SPAMinf.ed.ac.uk> wrote in message > news:fwezmbu0xdj.fsf(a)collins.inf.ed.ac.uk... >> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >> >>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>> Are you saying that the root cause of the "Problem" aspect of the >>> "Halting Problem" has nothing to do with self-reference? >> >> The "problem" nomenclature is just the same as is used in >> the Travelling Salesman Problem. >> >> en.wikipedia.org/wiki/Traveling_salesman_problem >> >> The halting problem, just as with the TSP, is well-posed and unambiguous. >> >> -- >> Alan Smaill > > http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > None-the-less it is this mode that I am using in my investigation. I > understand Turing Machines, and UTM's, both of these would mathematically > map to this alternative model. You can do what you want in your own work, obviously. What is the relevance of the link you just cited to my observation about the normal use in computer science? In that link, the word "problem" is used as I suggested. -- Alan Smaill
From: Ben Bacarisse on 18 Oct 2006 10:58
"Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message > news:87lkneqm4p.fsf(a)bsb.me.uk... >> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >> <big snip> >>>>>>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > Explain this proof within the context of the model that I provided. No thanks. More formal methods are the only way to avoid these vague, hand-waving arguments. -- Ben. |