Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!sdd.hp.com!mips!pacbell.com!pacbell!osc!jgk From: jgk@osc.COM (Joe Keane) Newsgroups: comp.theory Subject: Re: Question on halting problem Summary: I'm just rambling. Keywords: decidable Message-ID: <4765@osc.COM> Date: 8 May 91 02:07:53 GMT References: Reply-To: jgk@osc.COM (Joe Keane) Organization: Versant Object Technology, Menlo Park, CA Lines: 17 In article <4760@osc.COM> jgk@osc.UUCP i write: >Given a program which takes no input, either it halts or it doesn't. In article <1991May3.185947.19929@milton.u.washington.edu> petry@milton.u.washington.edu (David Petry) writes: >Am I the only one that questions the validity of the above assertion? I have to admit i have a certain intuitive uneasiness about assertions like this. Logically, it's simply the law of the excluded middle. However, it may be that neither alternative is provable. In computer science, we would say that you need an oracle to decide the answer. In mathematics, you just use the Axiom of Choice to eliminate the problem. This affirms my opinion that a lot of mathematicians don't understand what's going on. Constructivist mathematicians are of course excluded from the previous comment. -- Joe Keane, amateur mathematician jgk@osc.com (...!uunet!stratus!osc!jgk)