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 ».
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
modifierNotes
modifier- (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
modifier- Klaus Weihrauch, A Simple Introduction to Computable Analysis, (lire en ligne)
- 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, no 3, , p. 317–335 (DOI 10.1016/j.jco.2006.12.005
, hdl 10400.1/1011 )
- Scott Aaronson, NP-complete Problems and Physical Reality, ACM SIGACT News, Vol. 36, No. 1. (March 2005), pp. 30–52.
Voir aussi
modifierBibliographie
modifier- Lenore Blum, Felipe Cucker, Michael Shub, and Stephen Smale, Complexity and Real Computation, (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,
- 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, (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, no 1, , p. 132–150 (DOI 10.1006/jcss.1995.1013, MR 1322637, lire en ligne)
