A Possible "solution" to the Halting Problem
in [Theory]
|
From: Peter Olcott on 18 Oct 2006 17:44 "Alan Smaill" <smaill(a)SPAMinf.ed.ac.uk> wrote in message news:fwepscp1xz4.fsf(a)collins.inf.ed.ac.uk... > "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 I am using the sort of model that the link provides as my basis, rather than the formal mathematical model. int WillHalt(string SourceCode, string InputData) { if (MalignantSelfReference(SourceCode, InputData)) throw(MALIGNANT_SELF_REFERENCE); if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } This defeats the "problem" aspect of the Halting Problem.
From: Peter Olcott on 18 Oct 2006 17:45 "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message news:87wt6x8yc2.fsf(a)bsb.me.uk... > "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. Or perhaps they are a way to make a model that only seems to correspond to the actuality, with slight errors of the precise mathematical mapping, thus creating the fallacy of equivocation.
From: Peter Olcott on 18 Oct 2006 17:51 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:oYrZg.11120$Y24.7883(a)newsread4.news.pas.earthlink.net... > The Ghost In The Machine wrote: >> 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. >> >> 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. >> > > I was thinking of going a little further. > > Suppose the implementation language for LoopIfHalts is language X. Pick > any TM-equivalent language Y. Write a language Y interpreter in X, and > an X to Y compiler. LoopIfHalts gets fed as SourceCode the interpreter, > bundled with the compiled version of LoopIfHalts as the interpreted program. > > Language Y could be designed after WillHalt has been written. The only > information WillHalt gets about language Y is the language X > implementation of a Y interpreter. > > Perhaps we should just stick to Turing machines? WillHalt has to able to > deal with analyzing a TM program, because Turing machine is a possible > language Y. > > Patricia So the equivalent of the return value of the Halt() function from the TM is the integer value that the TM's ReadWrite head rests on when the TM halts. In this case DOES_NOT_HALT=0 HALTS=1 MALIGNANT_SELF_REFERENCE=2. This scenario breaks out of the infinite recursion of the original specification of the problem, and provides the only possible correct answer.
From: Peter Olcott on 18 Oct 2006 17:58 "Paul E. Black" <p.black(a)acm.org> wrote in message news:eh5k9g02mma(a)news3.newsguy.com... > On Tuesday 17 October 2006 14:36, Peter Olcott wrote: >> My primary point is based on the subtle distinction between your precise >> statement of the conclusions that can be drawn from the HP, and the actual >> correct conclusions that can actually be drawn. ... >> >> The HP does not show any limitation what-so-ever to the capability to >> determine the halting status of any program. All that the HP shows ... > > In my personal experience I find that the unsolvability of the Halting > Problem is a real limit (not just a problem in, say, definition) and > that the theorem is useful. > > From time to time we would have trouble "writing" some powerful > routines. We would think we had a solution, only to find we > overlooked something, and we'd try to generalize to solve the > *real* problem. Not infrequently after the second or third attempt, > we'd ponder and realize that the problem was equivalent to solving the > Halting Problem. With that we were satisfied with heuristics. > > Because of these experiences and the proofs I've seen, I am skeptical > of purported solutions to the Halting Problem. True, the Halting > Problem may be redefined such that there is a solution, but I've never > found the redefined problem applicable in the real world. > > Sincerely, > -paul- > -- > Paul E. Black (p.black(a)acm.org) The conclusion of the Halting Problem is that it purports to show that some things are not computable. If one treats English as a mathematical formalism, one sees that this conclusion is flatly incorrect. The Halting problem does not show that the correct halting status of every element in the set of all programs can not be determined. int WillHalt(string SourceCode, string InputData) { if (MalignantSelfReference(SourceCode, InputData)) throw(MALIGNANT_SELF_REFERENCE); if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } This function breaks out of the infinite recursive self reference of the HP thus defeating the conclusions drawn from the HP. It knows whether or not the program under test halts, Since it KNOWS this therefore it HAS DETERMINED THIS.
From: Peter Olcott on 18 Oct 2006 18:05
"Dr A. N. Walker" <anw(a)maths.nott.ac.uk> wrote in message news:eh5kf7$dj8$1(a)oyez.ccc.nottingham.ac.uk... > In article <Jo9Zg.9173$eZ4.2688(a)dukeread06>, > Peter Olcott <NoSpam(a)SeeScreen.com> wrote: >>I thought that the "problem" part of the term "Halting Problem" was directly >>referring to the existence of this case of malignant self-reference such that >>it >>appears to defeat attempts to determine whether or not any program in the set >>of >>all programs, halts. > > What you are calling "malignant self-reference" is nothing at all > to do with the HP itself, nor with whether it is solvable, nor with the > fact that it isn't. Rather, it arises in one specific proof that the HP > is unsolvable. There are other ways to show the basic result, including > a simple one based on the "busy beaver" idea. There is also no need for > the HP to refer to programs *at all*; Then what would it be that we are attempting to test the halting of? It would seem that you must be wrong here. If there are no programs, then there is no halting, thus no "Halting Problem" is possible, merely mathematical abstractions that falsely call themselves the HP. > there is a simple equivalent > formulation entirely in terms of data [eg as supplied to a UTM]. A UTM is essentially defined as being a program. > >>The HP does not show any limitation what-so-ever to the capability to >>determine >>the halting status of any program. > > The HP is merely a problem; as such it doesn't show anything at > all. However, the proof that it is unsolvable does show a limitation; > viz that there is no program that solves it. This is quite different > from, for example, the syntax analysis problem, for it is quite usual > for people to write syntax checkers, or the convex-hull-of-a-set-of- > points-in-N-dimensions problem, or the search-data-for-a-specified-string > problem, or many other potentially interesting problems. [But it is > similar to many other interesting but, sadly, unsolvable problems.] > >> All that the HP shows is that there exists >>some cases of malignant self-reference where this determination can not be >>provided as a return value to a caller. > > No, it doesn't show that. No matter how MSR your program may be, > there are programs out there that will show whether or not your program > with its data will halt. But this is a game of "you show me yours and Not when the result of this determination is structured as listed below: http://www.cprogramming.com/tutorial/computersciencetheory/halting.html > I'll show you mine". Given your program/data, I have a tester that will > investigate it; but given my tester, you can write a program/data that > busts it. It's important who is made to show his hand first. > > -- > Andy Walker, School of MathSci., Univ. of Nott'm, UK. > anw(a)maths.nott.ac.uk |