A Foundation for Real Recursive Function Theory

Jose Felix Costa

(Lisboa (visiting Swansea))

The class of recursive functions over the reals, denoted by REC(R), was
introduced by Cristopher Moore in his seminal paper written in 1995. Since
then many subsequent investigations brought new results: the class REC(R)
was put in relation with the class of functions generated by the General
Purpose Analog Computer of Claude Shannon; classical digital computation was
embedded in several ways into the new model of computation; restrictions of
REC(R) where seen to represent different classes of recursive functions, e.g.,
recursive, primitive recursive and elementary functions, and structures such
as the Ritchie and the Grzergorczyk hierarchies. The class of real recursive
functions was then stratified in a natural way, and REC(R) and the analytic
hierarchy were recently recognized as two faces of the same mathematical

In this new seminar, we bring a strong foundational support to the Real
Recursive Function Theory, rooted in Mathematical Analysis, in a way that
the reader can easily recognize both its intrinsic mathematical beauty and
its extreme simplicity. The new paradigm is now robust and smooth enough to
be taught. To achieve such a result some concepts had to change and some new
results were added.

(Joint work with Bruno Loff and Jerzy Mycka.)

Thursday 8th May 2008, 14:00
Robert Recorde Room
Department of Computer Science