Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sun-barr!olivea!uunet!zaphod.mps.ohio-state.edu!sample.eng.ohio-state.edu!purdue!haven.umd.edu!umd5!newton.cs.jhu.edu!callahan From: callahan@cs.jhu.edu (Paul Callahan) Newsgroups: comp.theory Subject: Re: Question on halting problem Message-ID: Date: 3 May 91 19:45:08 GMT Lines: 24 In article <1991May3.185947.19929@milton.u.washington.edu> petry@milton.u.washington.edu (David Petry) writes: >In article <4760@osc.COM> jgk@osc.UUCP (Joe Keane) writes: >> >> Given a program >>which takes no input, either it halts or it doesn't. > >Am I the only one that questions the validity of the above assertion? > >It seems reasonable to me to say, for example, that any program must either >halt within one million steps, or not halt within one million steps. But >without some explicit bound, the statement seems to be without meaning. Well, what's wrong with saying "There exists some explicit bound n, such that program P halts in n steps." To say that a program halts implies an existential quantification over all positive integers, and this is completely well defined. In fact, a statement to the effect that "program P halts" is clearly verifiable if it is true (which is why the set of halting programs is recursively enumerable). I don't see any problem at all. -- Paul Callahan callahan@cs.jhu.edu