Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!samsung!olivea!uunet!mcsun!hp4nl!alchemy!raymond From: raymond@cs.ruu.nl (Raymond Hoofman) Newsgroups: comp.theory Subject: Re: Question on halting problem Keywords: recursive Message-ID: <1991May03.061340.29357@cs.ruu.nl> Date: 3 May 91 06:13:40 GMT References: <18974@crdgw1.crd.ge.com> <4760@osc.COM> <7277@rex.cs.tulane.edu> Organization: Utrecht University, Dept. of Computer Science Lines: 32 In <7277@rex.cs.tulane.edu> fs@caesar.cs.tulane.edu (Frank Silbermann) writes: >We have concluded that the halting problem >is decidable for any specific input-free program P. > >Proof: >Consider algorithms A & B such that >algorithm A reads in a program and returns YES; >algorithm B reads in a program and returns NO. >One of these algorithms solves the halting problem for P. > >Is there any program P for which it has been proven that >we can never know which of these two algorithms, A and B, >is the right one? It is not possible to prove such a statement about a program P. Suppose P is a program for which it has been proven that we can never know which of these algorithms, A and B, is the right one. Now let P run on a computer. If P halts, say after n units of time, then we know after n units of time that A solves the halting problem for P. Because this is in contradiction with our assumption about P, we must conclude that P does not halt. Hence the existence of a proof of the fact that we can never know which of A,B decides P, implies the fact that P does not terminate, and hence it implies the fact that B decides P. Contradiction. -- ---------------------------------------------------------------------------- | Raymond Hoofman | "Love without pain is like | | raymond@cs.ruu.nl | pain without love." | ----------------------------------------------------------------------------