A Possible "solution" to the Halting Problem
in [Theory]
|
From: Patricia Shanahan on 18 Oct 2006 18:09 Peter Olcott wrote: .... > Can't a UTM modify itself by writing to the tape that contains it? Nope. The UTM itself is not on any tape. The program it is running is on a tape. However, if a UTM-like program allowed self-modification by the program it is running, it would not be a UTM, because it would not be accurately simulating Turing-machine behavior. It would be simulating some form of Von Neumann machine, in which the program is part of the data. > 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: No, it merely uses the result of a DOES-HALT call to decide what it is going to do next. > > int WillHalt(string SourceCode, string InputData) { > if (MalignantSelfReference(SourceCode, InputData)) > throw(MALIGNANT_SELF_REFERENCE); > if ( TheProgramWillHalt(SourceCode, InputData) ) > return TRUE; > else > return FALSE; > } You still have not defined a malignant self reference, or explained how to calculate it in the face of program transformations, including translations into other languages. To me, the problem seems insurmountable. The MalignantSelfReference function has to make a determination that appears to me to be the sort of test that is halting-problem equivalent. Of course, I can't prove that until you define what it does. Patricia
From: Peter Olcott on 18 Oct 2006 18:20 "Chris Menzel" <cmenzel(a)remove-this.tamu.edu> wrote in message news:slrnejcnv9.297d.cmenzel(a)philebus.tamu.edu... > On Wed, 18 Oct 2006 12:21:08 -0400, Paul E. Black <p.black(a)acm.org> > said: >> >> Because of these experiences and the proofs I've seen, I am skeptical >> of purported solutions to the Halting Problem. > > It's definitely a good thing to be skeptical of purported solutions to > provably unsolvable problems! > >> True, the Halting Problem may be redefined such that there is a >> solution, > > You can't redefine the Halting Problem; it is what it is. The most you > can do is decide to use the words "the Halting Problem" to mean some- > thing other than what everyone else means by them. Many unsolvable > problems have been "solved" in this manner in this newsgroup. :-) > Everyone else is taking them to mean something that they do not in fact mean. I wish that my 100% completely precise version of the English language, LUCID existed, then I could explain what I mean once, and everyone would see. Because this language does not exist, people slip and slide subtle nuances of meaning, and miss my point from their slight equivocations of meaning. What is the official precise English language conclusion drawn from the results of the mathematical analysis of the Halting Problem? Isn't it something along the lines of "It is impossible to determine the halting status of every element in the set of all programs"?
From: Patricia Shanahan on 18 Oct 2006 18:22 Peter Olcott wrote: .... > 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. OK, so now we are down to a well-defined environment. Perhaps you can explain how you define a MALIGNANT_SELF_REFERENCE in a Turing machine computation? Patricia
From: Peter Olcott on 18 Oct 2006 18:29 "Stephen Harris" <cyberguard-1048(a)yahoo.com> wrote in message news:XfwZg.17632$6S3.2843(a)newssvr25.news.prodigy.net... > 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
From: Peter Olcott on 18 Oct 2006 18:32
"trading_jacks" <MARKFERGASON(a)gmail.com> wrote in message news:1161204118.392679.269780(a)i3g2000cwc.googlegroups.com... > > 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. > Actually it would seem that you are the only one that has completely understood what I am saying. You even formed the same atypical conclusion that I formed about what division by zero really means, as opposed to and contrast with conventional wisdom. The Halting Problem too, is merely an ill-formed question, nothing more, and nothing less. |