A Possible "solution" to the Halting Problem
in [Theory]
|
From: Chris Menzel on 18 Oct 2006 19:19 On Wed, 18 Oct 2006 17:20:46 -0500, Peter Olcott <NoSpam(a)SeeScreen.com> said: > > "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. So you're saying that these apparent crackpots really *aren't* claiming to have solved the Halting Problem / refuted Cantor's theorem / uncovered the flaw in G?del's proof / <your favorite crackpot project here>? It sure *looks* like that's what they're claiming, since they say things like "The Halting Problem is solvable" and "I have identified the flaw in Cantor's/G?del's proof". But like you say, maybe they mean something by those words other than what people who know what they are talking about mean by those words. > I wish that my 100% completely precise version of the English > language, LUCID existed, Name's taken, dude! That's a shamep. ;-) > 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. Ah, yes, it's all their fault. Thing is, there's no slipping and sliding on nuances of meaning when it comes to the statement and analysis of the Halting Problem. It's a piece of very simple, painfully clear mathematics. Anyone making the sorts of claims you are making simply hasn't done their homework. > 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 for this to be a *precise* English language expression of the proposition you want, you'll have to include, at least, the mathematical definitions of "algorithm", "program", "input", "program ... halts on input ...", and related notions like that of a program execution. If you aren't using those definitions, you're probably either talking nonsense or you've simply changed the subject to something no one cares about.
From: Patricia Shanahan on 18 Oct 2006 19:36 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. Patricia
From: Peter Olcott on 18 Oct 2006 19:47 "Jack Campin - bogus address" <bogus(a)purr.demon.co.uk> wrote in message news:bogus-5894C8.23594918102006(a)news.news.demon.net... > "Peter Olcott" <NoSpam(a)SeeScreen.com> wrote: >> The Halting Problem too, is merely an ill-formed question, nothing more, >> and nothing less. > > How do you deal with the fact that the halting problem for some kinds of > computation *is* solvable? That's what complexity analysis is about. > Any time you make a database query, it will have gone through an optimizer > that solves the halting problem for the database query language (and does > considerably more than that). There is nothing at all ill-formed about > asking how long it will take to get an answer. > > This works because database query languages can't do as much as Turing > machines or unbounded-memory abstract machines programmed in C can. Read > a book and you might see what the relevant difference is. +-----------------------+ | | V | (What is the answer to this quesion?)--+ What is it about the about above question that make it unsolvable? > > ============== j-c ====== @ ====== purr . demon . co . uk ============== > Jack Campin: 11 Third St, Newtongrange EH22 4PU, Scotland | tel 0131 660 4760 > <http://www.purr.demon.co.uk/jack/> for CD-ROMs and free | fax 0870 0554 975 > stuff: Scottish music, food intolerance, & Mac logic fonts | mob 07800 739 557
From: Peter Olcott on 18 Oct 2006 19:49 "MoeBlee" <jazzmobe(a)hotmail.com> wrote in message news:1161212926.838979.168130(a)i3g2000cwc.googlegroups.com... > 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. > > You know it's ill-formed but you don't know anything about the actual > math of it. Right. Gotcha. > > MoeBlee > I know that the UTM form mathematically maps to the form that I provided.
From: Peter Olcott on 18 Oct 2006 19:56
"Chris Menzel" <cmenzel(a)remove-this.tamu.edu> wrote in message news:slrnejddkn.297d.cmenzel(a)philebus.tamu.edu... > On Wed, 18 Oct 2006 17:20:46 -0500, Peter Olcott <NoSpam(a)SeeScreen.com> > said: >> >> "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. > > So you're saying that these apparent crackpots really *aren't* claiming > to have solved the Halting Problem / refuted Cantor's theorem / > uncovered the flaw in G?del's proof / <your favorite crackpot project > here>? It sure *looks* like that's what they're claiming, since they > say things like "The Halting Problem is solvable" and "I have identified > the flaw in Cantor's/G?del's proof". But like you say, maybe they mean > something by those words other than what people who know what they are > talking about mean by those words. > >> I wish that my 100% completely precise version of the English >> language, LUCID existed, > > Name's taken, dude! That's a shamep. ;-) > >> 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. > > Ah, yes, it's all their fault. Thing is, there's no slipping and > sliding on nuances of meaning when it comes to the statement and > analysis of the Halting Problem. It's a piece of very simple, painfully > clear mathematics. Anyone making the sorts of claims you are making > simply hasn't done their homework. > >> 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. 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. > But for this to be a > *precise* English language expression of the proposition you want, > you'll have to include, at least, the mathematical definitions of > "algorithm", "program", "input", "program ... halts on input ...", and > related notions like that of a program execution. If you aren't using > those definitions, you're probably either talking nonsense or you've > simply changed the subject to something no one cares about. > |