Path: utzoo!utgpu!news-server.csri.toronto.edu!rpi!zaphod.mps.ohio-state.edu!wuarchive!rex!caesar!fs From: fs@caesar.cs.tulane.edu (Frank Silbermann) Newsgroups: comp.theory Subject: Re: Question on halting problem Keywords: recursive Message-ID: <7277@rex.cs.tulane.edu> Date: 2 May 91 19:52:59 GMT References: <18974@crdgw1.crd.ge.com> <4760@osc.COM> Sender: news@rex.cs.tulane.edu Organization: Computer Science Dept., Tulane Univ., New Orleans, LA Lines: 16 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? Frank Silbermann fs@cs.tulane.edu Tulane University New Orleans, Louisiana USA