French
DeutschMachine de Blum-Shub-Smale — Wikipédia
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
Pour les articles homonymes, voir BSS.
Une machine de Blum-Shub-Smale (ou machine BSS ou real RAM) est un modèle de calcul utilisé en informatique théorique, en particulier en calculs en nombres réels. Ce genre de machine calcule sur les nombres réels (autrement dit, son alphabet de bande est ). Elle manipule les réels comme des entités atomiques (c'est-à-dire sans s'intéresser à leur structure interne) et les opérations et tests qu'elle peut réaliser en temps unitaire correspondent respectivement aux fonctions et aux relations dont on dispose sur . Ce modèle a été proposé par Stephen Smale, Michael Shub et Lenore Blum en 1989[1].
En pratique, on ne munit pas les machines BSS de toutes les opérations possibles sur les réels. Au contraire, on s'intéresse généralement à des structures comme où les deux opérations possibles sont l'addition et l'opposition, et où seuls des tests d'égalité sont possibles.
Intérêt des machines BSS
[modifier | modifier le code]Les machines BSS fournissent un véritable modèle de calcul sur les nombres réels, où l'on ne se soucie pas des problèmes d'arrondi dus à la précision limitée des représentations booléennes que manipulent, par exemple, les machines de Turing « traditionnelles ». Mais le modèle de Blum, Shub et Smale ouvre également de nouvelles perspectives d'approche du problème P = NP dans la mesure où, sur certaines structures de , le problème « ? » est équivalent au problème standard[Quoi ?].
Voir aussi
[modifier | modifier le code]Liens externes
[modifier | modifier le code]- [PDF] E. Grädel. Finite Model Theory and Descriptive Complexity. In Finite Model Theory and Its Applications, pp. 125–230. Springer-Verlag, (2007)
- [PDF] L. Blum, M. Shub, and S. Smale, On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines, Bull. Am. Math. Soc., 21, 1 (1989)
Notes et références
[modifier | modifier le code]- (en) Stephen Smale, Michael Shub et Lenore Blum, « On a theory of computation and complexity over the real numbers: NP-completeness, recursive functions and universal machines », Bulletin of the AMS, vol. 21, no 1, , p. 1-46.
