Machine de Blum-Shub-Smale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

Une machine de Blum-Shub-Smale (ou machine BSS) 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[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 (\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[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 \mathbb{R}, le problème « P=NP ? » est équivalent au problème standard.

Voir aussi[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. (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,‎ 1989, p. 1-46