Forms of Recursion

Harold Simmons

(Manchester University)

Recursion theory as currently understood is concerned with the analysis of Turing degrees. In this topic any two Turing computable functions are deemed to be equivalent. However, there is an earlier, less expensive, set of material which is concerned with recursion and is in danger of being forgotten.

Some of the better know forms of recursion go by the names `Primitive recursion', `Course of value recursion', `Tail recursion', and the like. These are all concerned with converting given natural number functions into natural number functions. However, there are many other kinds of recursion, not all concerned with natural number functions, and some concerned with higher order functions.

In this talk I will try to put these method into a general setting, and suggest ways that this material could be turned into at least one course that could be taught at a postgraduate level (and perhaps earlier).

Some jokes, both pc and non-pc, may be included, but CZJ will not be mentioned.
Tuesday 6th May 2003, 14:00
Robert Recorde Room
Department of Computer Science