Rebuilding Moore's real recursion theory

Informal seminar of Theory group, University of Toronto, January 2007.

Journal version: “Differential recursion”

Abstract

Analog computers, in which both state and time are continuous, were once considered another plausible computing mechanism until digital dominance became clear in the fifties. Recently, theoretical models of such computers enjoy resurgence of interest with the aim to understand computation carried out by non-artificial systems. We study one such model, Moore's real (primitive) recursive functions. These classes of real functions are defined as the closure under certain operators, including what are supposed to be real-number versions of primitive recursion and minimization. We give a sound foundation to his theory by removing technical inaccuracies in the original work, and study the analytic properties of the class. It turns out, contrary to common belief, that there are real primitive recursive functions which are not differentially algebraic. We also discuss the relationship between Moore's classes and the standard (digital) Computability Theory.