G'day. On Thu, May 08, 2003 at 09:05:25AM +0300, Cagdas Ozgenc wrote:
Is it possible to have a programming language that can be used to produce only the programs that terminate, but at the same time decide all recursive languages? Or does such limitation automatically reduce the class of languages that such a programming language decide to primitive-recursive?
I don't know if this answers your question, but the class of primitive recursive programs is not the largest class of provably terminating programs there is. For example, I can very easily produce a programming language which consists of primitive recursive programs plus these five other specific programs which I happen to know always terminate because I proved it by other means. Cheers, Andrew Bromage