Machine de Blum-Shub-Smale
- Machine de Blum-Shub-Smale
-
Une machine de Blum-Shub-Smale (ou machine BSS) est une machine de Turing calculant 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 de et aux relations dont on dispose sur . 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 
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 de la question « P = NP ? » dans la mesure où, sur certaines structures de , le problème « P = NP ? » est équivalent au problème standard.
Voir aussi
Liens externes
Wikimedia Foundation.
2010.
Contenu soumis à la licence CC-BY-SA. Source : Article Machine de Blum-Shub-Smale de Wikipédia en français (auteurs)
Regardez d'autres dictionnaires:
Blum-Shub-Smale machine — In computation theory, the Blum Shub Smale machine, or BSS machine, is a model of computation introduced by Lenore Blum, Michael Shub and Stephen Smale, intended to describe computations over the real numbers. Essentially, a BSS machine is a… … Wikipedia
Machine De Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise … Wikipédia en Français
Machine de turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise … Wikipédia en Français
Machine de Turing — Pour les articles homonymes, voir Turing (homonymie). Une machine de Turing est un modèle abstrait du fonctionnement des appareils mécaniques de calcul, tel un ordinateur et sa mémoire, créé par Alan Turing en vue de donner une définition précise … Wikipédia en Français
Lenore Blum — Pour les articles homonymes, voir Blum. Fichier:Lenore Blum.jpeg Lenore Blum Lenore Blum (1942 ) est une mathématicienne américaine, dont les recherches portent entre autres sur la théorie des modèles, les corps différentiels et la complexité de… … Wikipédia en Français
Michael Shub — est un mathématicien ayant participé à l élaboration de l algorithme Blum Blum Shub en 1986. Voir aussi Article connexe Machine de Blum Shub Smale Lien externe Page personnelle … Wikipédia en Français
Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants … Wikipédia en Français
Real computation — In computability theory, the theory of real computation deals with hypothetical computing machines using infinite precision real numbers. They are given this name because they operate on the set of real numbers. Within this theory, it is possible … Wikipedia
Super-recursive algorithm — In computer science and computability theory, super recursive algorithms are algorithms that are more powerful, that is, compute more, than Turing machines. The term was introduced by Mark Burgin, whose book Super recursive algorithms develops… … Wikipedia
Projet:Mathématiques/Liste des articles de mathématiques — Cette page n est plus mise à jour depuis l arrêt de DumZiBoT. Pour demander sa remise en service, faire une requête sur WP:RBOT Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou… … Wikipédia en Français
