On the Relations Between Dynamical Systems and Boolean Circuits
Pascal Koiran, Centre National de la Recherche Scientifique (CNRS), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme, Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme, Lyon-1 Univ., 69 (France). Lab. de l'Informatique du Parallelisme, Institut Informatique et Mathematiques Appliquees de Grenoble (IMAG), 69 - Lyon (France). Lab. de l'Informatique du Parallelisme · 1992
We study the computational capabilities of dynamical systems defined by iterated functions on [0,1]^n. The computations are performed with infinite precision on arbitrary real numbers, like in the model of analog computation recently proposed by Hava Siegelmann and Eduardo Sontag. We concentrate mainly on the low-dimensional case and on the relations with the Blum-Shub-Smale model of computation over the real numbers.