A Possible "solution" to the Halting Problem
in [Theory]
|
From: Ben Bacarisse on 17 Oct 2006 23:10 "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message > news:874pu2tqla.fsf(a)bsb.me.uk... >> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >> >>> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >>> news:878xjetrqw.fsf(a)bsb.me.uk... >>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>> >>>>> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >>>>> news:1161118961.027553.142520(a)f16g2000cwb.googlegroups.com... >>>>>> Peter Olcott wrote: >>>>>>> I will frame this in the terms of the Halting Problem because I >>>>>>> understand >>>>>>> computer science much more deeply than math. >>>>>> >>>>>> Say what you want about computer science, but the statement of the >>>>>> unsolvability of the halting problem and the proof of the theorem are >>>>>> perfectly formed mathematics; the statement of the theorem and the >>>>>> proof are not "ill-formed" and is not analogous to division by zero, >>>>>> which has to do with conditional definition and descriptions that do >>>>>> not properly refer.. >>>>>> >>>>>> MoeBlee >>>>>> >>>>> >>>>> 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. >>>> >>>> I am curious. Do think that repeatedly re-stating your >>>> misunderstanding of the halting problem will persuade anyone? You >>>> have said the same thing in various ways to everyone who has posted, >>>> and they remain unmoved. Is it not time to start thinking that you >>>> may be mistaken? If not, let me ask a deeper question. What *would* >>>> start you thinking that you may be mistaken? >>> >>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>> Are you saying that I am wrong when I am saying that self-reference is >>> the root cause of the "problem" aspect of the "Halting Problem" ?? >> >> No, I did not say anything about that. I thought my questions were >> quite clear. >> >> Now I am curious as to why you have answered so few of the direct >> questions you have been asked. >> > I would have to first know the specific details that you would > consider that I might be wrong about before I could begin to > consider than I might be wrong. In other words it must be an item by > item point for point complete dialogue. Blanket statements are > useless. I'm not going to answer that because I will assume that you would answer the same as I do below. Obviously, let me know if I am wrong about this. > What would it take for you to think that you might be > wrong? An alternate (presumably contradictry) theorem stated and proved. If you have not got that far yet, and are simply unhappy about some other proof, then tell us the theorem you have trouble with and say which axiom or deductive step in its proof is at fault. That is how the subject progresses. Anything less belongs in alt.waffle.computers. -- Ben.
From: Peter Olcott on 17 Oct 2006 23:26 "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message news:87slhmqpxw.fsf(a)bsb.me.uk... > "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > >> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >> news:874pu2tqla.fsf(a)bsb.me.uk... >>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>> >>>> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >>>> news:878xjetrqw.fsf(a)bsb.me.uk... >>>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>> >>>>>> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >>>>>> news:1161118961.027553.142520(a)f16g2000cwb.googlegroups.com... >>>>>>> Peter Olcott wrote: >>>>>>>> I will frame this in the terms of the Halting Problem because I >>>>>>>> understand >>>>>>>> computer science much more deeply than math. >>>>>>> >>>>>>> Say what you want about computer science, but the statement of the >>>>>>> unsolvability of the halting problem and the proof of the theorem are >>>>>>> perfectly formed mathematics; the statement of the theorem and the >>>>>>> proof are not "ill-formed" and is not analogous to division by zero, >>>>>>> which has to do with conditional definition and descriptions that do >>>>>>> not properly refer.. >>>>>>> >>>>>>> MoeBlee >>>>>>> >>>>>> >>>>>> 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. >>>>> >>>>> I am curious. Do think that repeatedly re-stating your >>>>> misunderstanding of the halting problem will persuade anyone? You >>>>> have said the same thing in various ways to everyone who has posted, >>>>> and they remain unmoved. Is it not time to start thinking that you >>>>> may be mistaken? If not, let me ask a deeper question. What *would* >>>>> start you thinking that you may be mistaken? >>>> >>>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>>> Are you saying that I am wrong when I am saying that self-reference is >>>> the root cause of the "problem" aspect of the "Halting Problem" ?? >>> >>> No, I did not say anything about that. I thought my questions were >>> quite clear. >>> >>> Now I am curious as to why you have answered so few of the direct >>> questions you have been asked. >>> >> I would have to first know the specific details that you would >> consider that I might be wrong about before I could begin to >> consider than I might be wrong. In other words it must be an item by >> item point for point complete dialogue. Blanket statements are >> useless. > > I'm not going to answer that because I will assume that you would > answer the same as I do below. Obviously, let me know if I am wrong > about this. > >> What would it take for you to think that you might be >> wrong? > > An alternate (presumably contradictry) theorem stated and proved. If > you have not got that far yet, and are simply unhappy about some other > proof, then tell us the theorem you have trouble with and say which > axiom or deductive step in its proof is at fault. That is how the > subject progresses. Anything less belongs in alt.waffle.computers. > > -- > Ben. I am not using that model, I am using a model comparable to the above link.
From: Ben Bacarisse on 18 Oct 2006 00:32 "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: > "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message > news:87slhmqpxw.fsf(a)bsb.me.uk... >> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >> >>> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >>> news:874pu2tqla.fsf(a)bsb.me.uk... >>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>> >>>>> "Ben Bacarisse" <ben.usenet(a)bsb.me.uk> wrote in message >>>>> news:878xjetrqw.fsf(a)bsb.me.uk... >>>>>> "Peter Olcott" <NoSpam(a)SeeScreen.com> writes: >>>>>> >>>>>>> "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message >>>>>>> news:1161118961.027553.142520(a)f16g2000cwb.googlegroups.com... >>>>>>>> Peter Olcott wrote: >>>>>>>>> I will frame this in the terms of the Halting Problem because I >>>>>>>>> understand >>>>>>>>> computer science much more deeply than math. >>>>>>>> >>>>>>>> Say what you want about computer science, but the statement of the >>>>>>>> unsolvability of the halting problem and the proof of the theorem are >>>>>>>> perfectly formed mathematics; the statement of the theorem and the >>>>>>>> proof are not "ill-formed" and is not analogous to division by zero, >>>>>>>> which has to do with conditional definition and descriptions that do >>>>>>>> not properly refer.. >>>>>>>> >>>>>>>> MoeBlee >>>>>>>> >>>>>>> >>>>>>> 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. >>>>>> >>>>>> I am curious. Do think that repeatedly re-stating your >>>>>> misunderstanding of the halting problem will persuade anyone? You >>>>>> have said the same thing in various ways to everyone who has posted, >>>>>> and they remain unmoved. Is it not time to start thinking that you >>>>>> may be mistaken? If not, let me ask a deeper question. What *would* >>>>>> start you thinking that you may be mistaken? >>>>> >>>>> http://www.cprogramming.com/tutorial/computersciencetheory/halting.html >>>>> Are you saying that I am wrong when I am saying that self-reference is >>>>> the root cause of the "problem" aspect of the "Halting Problem" ?? >>>> >>>> No, I did not say anything about that. I thought my questions were >>>> quite clear. >>>> >>>> Now I am curious as to why you have answered so few of the direct >>>> questions you have been asked. >>>> >>> I would have to first know the specific details that you would >>> consider that I might be wrong about before I could begin to >>> consider than I might be wrong. In other words it must be an item by >>> item point for point complete dialogue. Blanket statements are >>> useless. >> >> I'm not going to answer that because I will assume that you would >> answer the same as I do below. Obviously, let me know if I am wrong >> about this. >> >>> What would it take for you to think that you might be >>> wrong? >> >> An alternate (presumably contradictry) theorem stated and proved. If >> you have not got that far yet, and are simply unhappy about some other >> proof, then tell us the theorem you have trouble with and say which >> axiom or deductive step in its proof is at fault. That is how the >> subject progresses. Anything less belongs in alt.waffle.computers. > > I am not using that model, I am using a model comparable to the above link. Ah, OK. I can now see why your are mistaken, but you have still not answered either of my questions. Would seeing a proper proof of the halting theorem change your mind? -- Ben.
From: Patricia Shanahan on 18 Oct 2006 00:45 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
From: The Ghost In The Machine on 18 Oct 2006 00:09
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. -- #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 |