Emmanuel Hainry (Nancy), Computable Analysis: Computability and complexity over the reals


  • Jan. 31, 2012, 14:30 - 16:00


Computing over continuous domains, in particular on the reals is quite important for example to simulate physical, biological, mathematical phenomena. Various models and various machines for computing on such domaines exist but there is no such thing as a Church-Turing thesis for computing on the reals, some models staying in the Turing-complete class, some using reals to answer the halting problem. We will concentrate on one model: Recursive Analysis which is well accepted and has a long history as it was already present in Turing's 1936 paper and even hinted at by Borel in 1912.

We will present the recursive analysis model, including some explanations on why some choices were made and introduce fundamental results on computability in recursive analysis. We will also show recent results on the characterization of classes of computable real functions.

Then, we will enter the complexity field. What does complexity mean when the size of the input is infinite and the computation is not terminating? We will answer this question, present basic tools to analyse the complexity of functions and a framework that allows us to translate characterizations of discrete complexity classes into characterizations of the analog real complexity class, and use it to give a characterization of the class of real functions computable in polynomial time.