On the relations between dynamical systems and boolean circuits.

Pascal Koiran (1)

1 LIP - Laboratoire de l'Informatique du Parallélisme

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.

Nous étudions la puissance de calcul de systèmes dynamiques définis par des itérations de fonctions sur [0,1]^n. Les calculs effectués en précision infinie sur des nombres réels quelconques, comme dans le modèle de calcul analogique récemment proposé par Hava Siegelmann et Eduardo Sontag. Nous insistons surtout sur l cas des systèmes en petites dimensions sur les relations avec le modèle de calcul sur les nombres réels de Blum, Shub & Smale.

Mots clés: Analog Computation; Dynamical Systems; Non-Uniform Complexity

Mots clés: Calcul analogique; Complexité non uniforme; Systèmes dynamiques

Domaines: Informatique [cs]

Pascal Koiran. On the relations between dynamical systems and boolean circuits.. [Research Report] LIP RR-1993-01, Laboratoire de l'informatique du parallélisme. 1992, 2+13p. ⟨hal-02101931⟩