TURING MACHINE DE
Dans l'article « On computable numbers, with an application to the Entscheidungsproblem », publié en 1936 dans les Proceedings of the Mathematical Society, Alan Mathison Turing (1912-1954) montre qu'il existe des nombres définissables qui ne sont pas calculables. Cela implique qu'il n'existe pas de solution au célèbre problème de la décision formulé par David Hilbert. Pour cette démonstration, le jeune fellow du King's College de l'université de Cambridge (Royaume-Uni) définit une machine abstraite qui passe d'un état à un autre en suivant un ensemble de lois précises lorsqu'elle lit un caractère sur une bande magnétique. Cette machine peut imprimer ou effacer des symboles, par exemple la partie décimale d'un nombre réel défini par un processus récursif. Turing montre que la plupart des nombres réels ne sont pas calculables au sens où leurs développements décimaux ne peuvent pas être écrits automatiquement par une telle machine. Anticipant de plusieurs décennies la révolution informatique, Turing résout en logicien une des questions centrales des mathématiques.
La suite de cet article est accessible aux abonnés
- Des contenus variés, complets et fiables
- Accessible sur tous les écrans
- Pas de publicité
Déjà abonné ? Se connecter
Écrit par
- Bernard PIRE : directeur de recherche émérite au CNRS, centre de physique théorique de l'École polytechnique, Palaiseau
Classification
Autres références
-
ALGORITHME
- Écrit par Alberto NAIBO et Thomas SEILLER
- 5 919 mots
- 4 médias
...symboles sur une feuille, que l’on peut supposer divisée en cases comme un cahier d’écolier. » Cette analyse mène Turing à modéliser le calcul au moyen de machines « idéalisées », ce qu’on appelle aujourd’hui les machines de Turing. Elles sont constituées par un ruban infini et divisé en cases, ainsi que... -
COGNITIVES SCIENCES
- Écrit par Daniel ANDLER
- 19 262 mots
- 4 médias
...une sorte d'« espèce naturelle », insensible à de larges variations de définition. Et les calculs auxquels sont soumises les représentations mentales peuvent être par exemple décrits comme ceux qu'exécute une machine de Turing, ou, encore, comme on peut le dire aujourd'hui, un ordinateur numérique. -
INFORMATIQUE - Principes
- Écrit par Jacques HEBENSTREIT
- 3 060 mots
- 2 médias
Les automates définis dès 1936 par le mathématicien anglais Alan Mathison Turing se sont révélés d'excellents modèles abstraits des ordinateurs réalisés à partir de 1943. -
OBJET UNIVERSEL, mathématique
- Écrit par Patrick DEHORNOY
- 1 050 mots
Des objets universels apparaissent dans de multiples contextes mathématiques, mais l'idée de base est commune : un objet universel est un objet à partir duquel tous les autres membres de la famille considérée peuvent se reconstruire. Par conséquent, un objet universel est, quand il existe, le plus grand,...
- Afficher les 8 références
