Calculs en nombres réels

En informatique théorique, et en théorie de la calculabilité la théorie des calculs réels est un sujet d'étude qui traite des machines à calculer (ordinateurs) hypothétiques utilisant des nombres réels de précision infinie. Elles portent ce nom parce qu'elles opèrent sur l'ensemble des nombres réels. Dans le cadre de cette théorie, il serait possible de prouver des énoncés tels que « le complément de l'ensemble de Mandelbrot n'est que partiellement décidable ».

Schéma électrique d'un calculateur analogique servant à intégrer une fonction donnée. La théorie des calculs en nombres réels recherche les propriétés d'un tel système avec un précision infinie hypothétique.

Ces machines à calculer hypothétiques peuvent être considérées comme des ordinateurs analogiques idéalisés qui opèrent sur des nombres réels, alors que les ordinateurs numériques sont limités aux nombres calculables. Ils peuvent être subdivisés en modèles différentiels et algébriques (dans ce contexte, les ordinateurs numériques doivent être considérés comme topologiques, du moins en ce qui concerne leur fonctionnement sur les nombres réels calculables[1]).

Selon le modèle choisi, cela peut permettre aux ordinateurs réels de résoudre des problèmes inextricables pour les ordinateurs numériques (par exemple, concernant les réseaux neuronaux de Hava Siegelmann (en)...) ou vice versa. Ainsi l'ordinateur analogique idéalisé de Claude Shannon ne peut résoudre que des équations différentielles algébriques, alors qu'un ordinateur numérique peut également résoudre certaines équations transcendantes. Toutefois, cette comparaison n'est pas tout à fait juste car dans l'ordinateur analogique idéalisé de Claude Shannon, les calculs sont effectués immédiatement, c'est-à-dire en temps réel[2].

Un modèle canonique de calcul sur les réels est la machine de Blum-Shub-Smale.

Si le calcul réel était physiquement réalisable, on pourrait l'utiliser pour résoudre des problèmes NP-complets, et même des problèmes P-complets, en temps polynomial. Les nombres réels de précision illimitée dans l'univers physique sont interdits par le principe holographique et la limite de Bekenstein[3].

Notes et références

Notes

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Real computation » (voir la liste des auteurs).

Références

1. Klaus Weihrauch, A Simple Introduction to Computable Analysis, 1995 (lire en ligne)
2. O. Bournez, M. L. Campagnolo, D. S. Graça et E. Hainry, « Polynomial differential equations compute all real computable functions on computable compact intervals », Journal of Complexity, vol. 23, n^o 3,‎ juin 2007, p. 317–335 (DOI 10.1016/j.jco.2006.12.005 , hdl 10400.1/1011 )
3. Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.

Voir aussi

Bibliographie

• Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, Complexity and Real Computation, 1998 (ISBN 0-387-98281-7)
• Manuel Lameiras Campagnolo, Computational complexity of real valued recursive functions and analog circuits, Universidade Técnica de Lisboa, Instituto Superior Técnico, juillet 2001
• Natschläger, Thomas, Wolfgang Maass, Henry Markram, The "Liquid Computer" A Novel Strategy for Real-Time Computing on Time Series (lire en ligne)
• Hava Siegelmann, Neural Networks and Analog Computation: Beyond the Turing Limit, décembre 1998 (ISBN 0-8176-3949-7)
• Hava T. Siegelmann et Eduardo D. Sontag, « On the computational power of neural nets », Journal of Computer and System Sciences, vol. 50, n^o 1,‎ 1995, p. 132–150 (DOI 10.1006/jcss.1995.1013, MR 1322637, lire en ligne)

Articles connexes

• Liste de publications importantes en informatique théorique