Computation and complexity
Real number computation and dynamical systems
Complexity of dynamical systems can be analyzed by theory of computation embedding Turing machines into symbolic dynamics of corresponding dynamical systems. C. Moore showed that an universal Turing machine can be embedded into a two-dimensional piecewise-linear maps and studied undecidability of dynamical systems[1]. A three-dimensional classical billiard system gives a physical example of such dynamical systems. Problems of real number computation arise from relationship between chaotic dynamical systems and algorithmic complexity. L. Blum and colleagues give Blum-Shub-Smale machine that can operate real number to analyze complexity of Julia sets and the Mandelbrot set[2]. These are dynamical systems studies which are in contrast to classical theory of computation[3]. There are number of open questions in this research area.
[1] C. Moore, Phys. Rev. Lett., 64, p2354–2357, (1990);C. Moore, 1991 Nonlinearity, 4, p199, (1991).
[2] L. Blum, M. Shub, and S. Smale, Bull. Amer. Math. Soc., 21(1), p1, (1989); L. Blum, F.Cucker, M. Shub, S. Smale, "Complexity and Real Computation," Springer, (1997).
[3] A. M. Turing, Proc. London Math. Soc., 2-42, p230, (1936);
M. B. Pour-El, J. I. Richards, "Computability in Analysis and Physics," Springer, (1989).
