# on termination

**Peter Gammie
**
peteg@cse.unsw.EDU.AU

*Thu, 8 May 2003 18:07:44 +1000 (EST)*

>* That's a good example. So how much can we expand this class? Is it possible
*>* to cover all recursive languages, or is there a theorem that says this is
*>* not possible?
*
The class of recursive (total) functions is not recursively enumerable,
i.e. not acceptable by a Turing machine. This result can be found in any
textbook on recursive function theory (ask me off list and I'll dig up a
reference).
More interestingly, it is possible to (uniformly) define classes of total
functions that are strictly larger than the primitive recursive class - in
particular, this is what type theorists spend a lot of time doing. (See,
for example, Simon Thompson's book on Type Theory and Functional
Programming.)
Now, a question of my own: is it possible to uniformly define a class of
functions that have a non-trivial decidable halting predicate? The notion
of "uniform" is up for argument, but i want to rule out examples like
Andrew's that involve combining classes in trivial ways.
cheers
peter