A Possible "solution" to the Halting Problem
in [Theory]
|
From: Patricia Shanahan on 18 Oct 2006 21:53 Peter Olcott wrote: .... > What it boils down to is this, (at least within the scope of the HP) it is not > that there exists some problems too difficult to be solved by computation, it is > merely the case that some ill-formed questions have no correct answer. > > I might agree with that formulation if you presented an algorithm for deciding if something is an ill-formed question. I've asked for it often enough, without result, that by now I'm convinced you do not have any algorithm for identifying what you call an ill-formed question, or distinguishing them from questions you consider well-formed. I'm not surprised, because I strongly suspect that even if you defined what you consider to be an ill-formed question, deciding the set of ill-formed questions would still be halting-problem equivalent, and cannot depend on the existence of an ill-formed question decider. How are we supposed to avoid asking ill-formed questions, or to find out that we have asked one, without an algorithm for deciding if a question is ill-formed? Patricia
From: MoeBlee on 18 Oct 2006 21:56 Peter Olcott wrote: > it is > merely the case that some ill-formed questions have no correct answer. There is no "ill-formed question" involved in the theorem that, to quote a standard textbook, "there exists a Turing machine whose halting problem is recursively unsolvable." Whatever else goes in informal discussion about that theorem, you at least do recognize that the above is a description of a theorem (and that there's nothing such as an "ill formed question") in the proof of such mathematical theorems, right? MoeBlee
From: Barb Knox on 18 Oct 2006 21:57 In article <pUyZg.11247$Y24.7075(a)newsread4.news.pas.earthlink.net>, Patricia Shanahan <pats(a)acm.org> wrote: > Peter Olcott wrote: > > "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message > > news:1161210790.800534.60930(a)h48g2000cwc.googlegroups.com... > >> Peter Olcott wrote: > >>> What is the > >>> official precise English language conclusion drawn from the results of > >>> the > >>> mathematical analysis of the Halting Problem? > >> Why not start by at least informing yourself of an exact mathematical > >> statement of the theorem and its proof? > >> > >> MoeBlee > >> > > > > That is not within my purpose. My purpose is to show that the Halting > > Problem is > > really nothing more than an ill-formed question. > > The whole Halting Problem? There are large classes of computations that > provably halt. Indeed, there are algorithms that are known to halt for > every input. On the other hand, there are computations that can be > proved to not halt. Not only is the question interesting and > well-formed, it is frequently answered. > > In between, there is a set of computations for which neither halting nor > not-halting has been proved. > > The non-decidability of the halting problem tells us that we can never > reduce that set to the empty set. > > As far as I can tell, you agree with that conclusion. You don't seem to > have contributed anything interesting, such as an algorithm for deciding > whether a computation is one that can never be proved to halt or not-halt. <pedantry> A proof that there is no proof that some computation halts implies that the computation in fact does not halt. </pedantry> And IMO, you are very unlikely to provoke any entertaining fallacies from PO. > Patricia
From: Chris Menzel on 18 Oct 2006 21:37 On Wed, 18 Oct 2006 18:56:21 -0500, Peter Olcott <NoSpam(a)SeeScreen.com> said: >> ... >>> 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"? >> >> Why say "every element in the set of all programs" when you could just >> say "every program"? But no, that's not right, since, among lots of >> other things, it makes no reference to input. Better is something along >> these lines: There is no algorithm for determining, for every program P >> and input I, whether or not P halts on I. > > But that is NOT what the halting proof shows. Well, 'fraid it is (modulo mathematically precise definitions of the relevant concepts). The Halting Problem is this: for any given program P and input I, to decide whether P halts on I. And what has been proved is this: the Halting Problem is unsolvable; there is no decision procedure that solves this problem. > My whole point is that the above conclusion can not be correctly drawn > from the results of the Halting Problem. What the Halting Problem > shows, and the English conclusions that are drawn from what the > Halting Problem shows do not precisely correspond. If that is your point, then you understand neither the Halting Problem nor the proof of its unsolvability. But the great thing is, you can! There's lots of interesting texts where you can learn about it. Don't you want to understand what you think you're talking about? Cuz right now you don't. Really. I am not kidding.
From: Daryl McCullough on 18 Oct 2006 22:00
Peter Olcott says... >What it boils down to is this, (at least within the scope of the HP) >it is not that there exists some problems too difficult to be solved >by computation, it is merely the case that some ill-formed questions >have no correct answer. I'm afraid to ask, but what is ill-formed about the question: Does polynomial equation P have any positive integer solutions? The halting problem is provably equivalent to that problem. For example, the polynomial equation x^2 + y^2 = z^2 has infinitely many integer solutions, for example x=3, y=4, z=5. In contrast, the equation x^3 + y^3 = z^3 has no positive integer solutions. It would be nice if we had a computer program that whenever it is given a polynomial equation, returns "true" if the equation has integer solutions, and returns "false" if it does not. What is ill-formed about the question "Does this polynomial equation have any positive integer solutions?" Well, it is provably the case that there is no deterministic computer program that can solve this problem. This problem is provably equivalent to the halting problem. -- Daryl McCullough Ithaca, NY |