Computability with continuous-time dynamical systems

Slides

In this talk we will review Shannon’s General Purpose Analog Computer (GPAC) Shannon [1941] which was later extended by Pour-El, Lipschitz, and Rubel Lipshitz and Rubel [1987]. This model was corrected in 2003 by Félix Costa and Daniel Graça in Graça and Costa [2003], which introduced polynomial differential equations as the “correct” definition of the GPAC. Here we present the main results about this model, namely its evolution Graça [2003], Graça [2004], connections with standard (type-1) computability Graça et al. [2008], with computable analysis (type-2 computability – computability with real numbers) Bournez et al. [2007], and some undecidability results about these systems Graça et al. [], Graça et al. [2007].

References

Bournez et al. [2007]

O. Bournez, M. L. Campagnolo, D. S. Graça, and E. Hainry. Polynomial differential equations compute all real computable functions on computable compact intervals. J. Complexity, 23 (3): 317–335, 2007.

Graça et al. [2007]

D. Graça, N. Zhong, and J. Buescu. Computability, noncomputability and undecidability of maximal intervals of IVPs. Trans. Amer. Math. Soc., 2007. To appear.

Graça [2003]

D. S. Graça. Computability via analog circuits. In V. Brattka, M. Schröder, K. Weihrauch, and N. Zhong, editors, Proceedings of the International Conference on Computability and Complexity in Analysis (CCA 2003), pages 229–240. FernUniversität in Hagen, 2003.

Graça [2004]

D. S. Graça. Some recent developments on Shannon’s General Purpose Analog Computer. Math. Log. Quart., 50 (4-5): 473–485, 2004.

Graça and Costa [2003]

D. S. Graça and J. F. Costa. Analog computers and recursive functions over the reals. J. Complexity, 19 (5): 644–664, 2003.

Graça et al. []

D. S. Graça, M. L. Campagnolo, and J. Buescu. Computational bounds on polynomial differential equations. Appl. Math. Comput., page to appear.

Graça et al. [2008]

D. S. Graça, M. L. Campagnolo, and J. Buescu. Computability with polynomial differential equations. Adv. Appl. Math., 40 (3): 330–349, 2008.

Lipshitz and Rubel [1987]

L. Lipshitz and L. A. Rubel. A differentially algebraic replacement theorem, and analog computability. Proc. Amer. Math. Soc., 99 (2): 367–372, 1987.

Shannon [1941]

C. E. Shannon. Mathematical theory of the differential analyzer. J. Math. Phys. MIT, 20: 337–354, 1941.

This document was translated from L^AT_EX by H^EV^EA.