Emmanuel Hainry (Nancy), Computable Analysis: Computability and complexity over the reals
Schedule
- Jan. 31, 2012, 14:30 - 16:00
Abstract
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.
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.