Machine de Blum-Shub-Smale

Une machine de Blum-Shub-Smale (ou machine BSS ou real RAM) est un modèle de calcul utilisé en informatique théorique. Ce genre de machine calcule sur les nombres réels (autrement dit, son alphabet de bande est $\mathbb {R}$). 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 $\mathbb {R}$. Ce modèle a été proposé par Stephen Smale, Michael Shub et Lenore Blum en 1989.

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 $(\mathbb {R} ,+,-,=)$ 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

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 $\mathbb {R}$, le problème « $P=NP$ ? » est équivalent au problème standard^[Quoi ?].

Voir aussi

• Machine de Turing
• NP-complet
• Hypercalcul
• Problème P = NP

Liens externes

• [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)