Machine de Blum-Shub-Smale

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher
Ce modèle est-il pertinent ? Cliquez pour en voir d'autres.
Cet article ne cite pas suffisamment ses sources (mars 2013).

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 » (modifier l'article, comment ajouter mes sources ?).

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 ). 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.

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