on termination

Andrew J Bromage ajb@spamcop.net
Thu, 8 May 2003 16:19:55 +1000


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.

Andrew Bromage