Computable Analysis and its Applications

Course Contents

The course introduces basic concepts of computable analysis such as computable real numbers, computable functions, operators and functionals. The subject of the course represents a marriage between classical mathematical analysis and computability. It is useful to know, at least theoretically, which computations in analysis are possible and which are not. We will introduce a framework for investigating computability and non computability of standard processes in mathematical analysis. In this course we consider and compare different approaches to computability on the reals: machine-oriented and domain-theoretic approaches. We will also consider some applications of computable analysis to the theory of hybrid systems.

About the Lecturer

Margarita Korovina received her PhD in 1996 from Sobolev Institute of Mathematics, Novosibirsk, Russia. Her thesis, "Generalized computability on the real numbers", presents a theory of computation of real-valued functions, functionals and operators of finite types. Her current research interests include computable analysis, definability and computability theories, domain theory and hybrid systems. Margarita joined BRICS in 2001.

Programme

Tuesday April 23, 2002, 15:15-17:00 in Auditorium D4

Introduction, basic definitions and examples.

Thursday April 25, 2002, 15:15-17:00 in Auditorium D4

Comparative analysis of different approaches to computability on the reals.

Tuesday April 30, 2002, 15:15-17:00 in Auditorium D4

Computable functionals and operators. Applications of computable analysis to the theory of hybrid systems.

References

• M.B. Pour-El, J. Ian Richards, Computability in Analysis and Physics, Perspectives in Mathematical Logic, Springer, Berlin, 1989
• Ker-I Ko, Complexity Theory of real functions, Progress in Theoretical Computer Science, Birkhauser, Boston, 1991
• K. Weihrauch, Computable analysis. An Introduction, Springer-Verlag, 2000.

Papers:

• A. Edalat and P. Snderhauf. A domain-theoretic approach to computability on the real line. TCS, 210:73-98, 1999.
• M.V. Korovina, O.V. Kudinov, Semantic Characterisations of Second-order Computability Over the Real Numbers , LNCS 2142, 160-173, 2001.
• M.V. Korovina, O.V. Kudinov, Generalised Computability and applications to hybrid systems, Proceedings of PSI-01, LNCS 2244, p. 494-500, 2001.
• M.V. Korovina, O.V. Kudinov, Formalisation of Computability of Operators and real-Valued Functional Via domain Theory, Proceedings of CCA-2000, LNCS, 2064, pp 146-168, 2001.
• A.Nerode, W. Kohn, Models for Hybrid Systems: Automata, Topologies, Controllability, Observability, LNCS 736, pp 317-357, 1993.