A Possible "solution" to the Halting Problem
in [Theory]
|
From: Stephen Harris on 18 Oct 2006 16:08 Peter Olcott wrote: > "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. No, and it is not analogous. You do not understand the halting problem, your conception is fictitious and your posts are irrelevant to the Halting Problem. Your comments are more relevant to what they call automated program checkers which fail with a complex program and that idea is why programmers always have to check their code to see if it performs as intended. Perhaps the idea of self-reference is involved as one needs a program checker, a program checker to check the program checker, a program checker to check the program checker which is checking the program checker which is checking the program checker and so on and so on ... which is the concept of infinite regress. http://pag.csail.mit.edu/~mernst/pubs/generate-specs-issta2002.pdf Your ideas may be correct for what you are talking about, I don't know. But you are not talking about the Halting Problem that other people refer to with that label, you are talking about your own interpretation of what that term means which is based on ignorance. I mean that you don't get to invent your own personal definitions for terms which have and have had a special agreed upon meaning for 70 years, criticize your delusions, and claim that is what other people mean. That is called a strawman argument. I think more likely that your posts are a shabby trick to advertise your website so you get paid for more visits to your website which inflicts popup advertising on the visitor. Perhaps that scenario is not more likely as it gives you too much credit for being clever. You are a disgusting intellectual fraud and stupid. You gave your whole game away when you claim as a qualification, Peter Olcott wrote: 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. ------------------------------------------------- Patricia Shanahan replied: 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 --------------------------------------------------- Peter, I don't think you know what a Turing Machine is. They are not physically realizable (only a subset) and are abstract or ideal machines. In particular they have an unbounded tape (potentially infinite). That means they don't fail because they run out of memory which can be a problem for a physical computer which all have a finite amount of memory which limits the solutions which can be physically computed. There are neither time nor memory constraints for Turing machines which is what I mean by not physically realizable, they are abstract. The reason Turing added the finitely unbounded tape was to eliminate from consideration programs that would complete *if* they had enough memory from programs whose halting is undecidable even if they have as much memory as could ever be needed. Nor is a procedure possible to distinguish "genuine" halting from depletion of available memory. It doesn't appear that you have ever read a paper describing what a Turing machine is, or you certainly did not understand it. Your posts are all imaginary garbage. http://www.earlham.edu/~peters/courses/logsys/turing2.htm
From: Stephen Harris on 18 Oct 2006 16:37 Peter Olcott wrote: > "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: >> >>> "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. > > Explain this proof within the context of the model that I provided. > > http://moonbase.wwc.edu/~aabyan/Theory/Computable.html#halting "The Halting Problem for a programming language. We will use the "C" programming language, yet any language will work. Assumption: There exists a way to write a function named Halts such that: int Halts(char * P, char * I) { /* code that reads the source code for a "C" program, P, determines that P is a legal program, then determines if P eventually halts (or exits) when P reads the input string I, and finally sets a variable "halt" to 1 if P halts on input I, else sets "halt" to 0 */ return halt; } Construct a program called Diagonal.c as follows: int main() { char I[100000000]; /* make as big as you want or use malloc */ read_a_C_program_into( I ); if ( Halts(I,I) ) { while(1){} } /* loop forever, means does not halt */ else return 1; } Compile and link Diagonal.c into the executable program Diagonal. Now execute Diagonal < Diagonal.c. Consider two mutually exclusive cases: Case 1: Halts(I,I) returns a value 1. This means, by the definition of Halts, that Diagonal.c halts when given the input Diagonal.c. BUT! we are running Diagonal.c (having been compiled and linked) and so we see that Halts(I,I) returns a value 1 causes the "if" statement to be true and the "while(1){}" statement to be executed, which never halts, thus our executing Diagonal.c does NOT halt. This is a contradiction because this case says that Diagonal.c does halt when given input Diagonal.c. Well, try the other case. Case 2: Halts(I,I) returns a value 0. This means, by the definition of halts, that Diagonal.c does NOT halt when given the input Diagonal.c. BUT! we are running Diagonal.c (having been compiled and linked) and so we see that Halts(I,I) returns a value 0 causes the "else" to be executed and the main function halts (stops, exits). This is a contradiction because this case says that Diagonal.c does NOT halt when given input Diagonal.c. There are no other cases, Halts can only return 1 or 0. Thus what must be wrong is our assumption "there exists a way to write a function named Halts..." . "
From: trading_jacks on 18 Oct 2006 16:41 William Elliot wrote: > On Sun, 15 Oct 2006, Peter Olcott wrote: > > <mareg(a)mimosa.csv.warwick.ac.uk> wrote in message > > > "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? > > > > What is the value of X? > > > Just like he told you, X doesn't have a value. I am not a normal poster to this group but I stumbled upon this and it seems like maybe we make too much out of things. Isn't there something about amoung multiple possible explinations the most likely is the simplist. That is an ill-formed question. If I have a bucket of beans (like the kind you used to play with at the grocery store when you were a kid) we can determin how many handfuls it would require to empty it. That is division. So the question is "How long will it take to empty this bucket if I take nothing out?" and that sounds like something for Buda, not Comp Science. Forgive me if I am too simplistic.
From: Peter Olcott on 18 Oct 2006 17:41 "Patricia Shanahan" <pats(a)acm.org> wrote in message news:wBpZg.8700$Lv3.4747(a)newsread1.news.pas.earthlink.net... > 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. Can't a UTM modify itself by writing to the tape that contains it? In any case what I mean by self-modification is the fact that the SELF-HALT attempts to modify the determination of DOES-HALT by doing the opposite of this determination. This attempt is defeated by the following code: int WillHalt(string SourceCode, string InputData) { if (MalignantSelfReference(SourceCode, InputData)) throw(MALIGNANT_SELF_REFERENCE); if ( TheProgramWillHalt(SourceCode, InputData) ) return TRUE; else return FALSE; } > > 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: trading_jacks on 18 Oct 2006 17:43
Peter Olcott wrote: > <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. Okay, but at some point the computer must perform the calculation/equation 50/0. Therefore we could say: y = 50/0 x := y And since we can't figure out the first line, how are we to assign the variable? I know there is a difference between assignment and equality, but wouldn't assignment imply an equation exist? |