Accueil Publimath  Aide à la recherche   Recherche Avancée   Aidez-nous à améliorer cette fiche 
Certification IDDN Valid HTML 4.01 Transitional
Auteur(s) : Turing Alan ; Girard Jean-Yves ; Basch Julien. Trad. ; Blanchard Patrice. Trad.

Titre : La machine de Turing.

Editeur : Editions du Seuil Paris, 1995 Collection : Sources du savoir
Format : 14 cm x 20,6 cm, 177 p. ISBN : 2-02-013571-X EAN : 9782020135719  ISSN : 1144-6676

Type : ouvrage (au sens classique de l'édition) Langue : Français Support : papier

Public visé : chercheur, élève ou étudiant, enseignant Niveau : licence Age : 18, 19, 20

Résumé :

Cet ouvrage s'insère dans une collection dont le but est de remettre en circulation les textes fondamentaux sources du savoir. Il comporte quatre parties :

La première intitulée "La machine de Turing : de la calculabilité à la complexité" est rédigée par le logicien contemporain Jean-Yves Girard. Dans cette partie, il rappelle et décrit rapidement en termes modernes (mais non techniques) les notions, maintenant bien connue par ceux qui s'intéressent aux fondements logiques des mathématiques, de "calculabilité", "décidabilité", "fonctions récursives", "incomplétude" etc. ; polémique contre la "gödélite" des années 60 ; décrit la machine de Turing selon les canons actuels -sans tenir compte de l'article de Turing de la seconde partie- et enfin conclu sur la notions de complexité (et de problèmes P-NP) qui selon lui est la véritable postérité de Turing.

La seconde partie intitulée : "Théorie des nombres calculables suivie d'une application aux problèmes de la décision" est le célèbre article publié par Turing en 1936 dans lequel il expose pour la première fois dans l'histoire de la logique et des mathématiques la notion de "machine à calculer appelée depuis machine de Turing qui, grosso modo, peut être interprété comme le modèle d'un ordinateur théorique calculant à l'aide d'un programme ("machine à calculer universelle"). Ce mémoire est divisé en dix articles suivis d'un appendice (publié en août 36) et d'une note du traducteur.
L'introduction rappelle le contexte historique dans lequel le mémoire est publié : celui des travaux d'Hilbert, Gödel, Church sur "le problème de la décision" (Entscheidungsproblem).
Les articles 1 à 4 décrivent la "machine à calculer" selon Turing à l'aide des notions de "bandes divisées en cases" où l'on peut "écrire" ou "inspecter" des "symboles", ainsi que celle de "m-configuration" comme ensemble fini d'"états" caractérisant le comportement de la machine, lequel peut être décrit à l'aide de "tables" (l'équivalent moderne en serait l'écriture d'un programme en langage machine pour un certain type d'ordinateur. Turing donne alors des exemples de "séquences calculables" par une machine, ces séquences s'interprétant comme le développement infini en base deux d'un réel compris entre 0 et 1 : on obtient ainsi le concept de réel calculable au sens de Turing.
Les articles 5 à 7 sont très importants et montrent qu'en codant (à la manière de Gödel) chaque machine particulière à l'aide d'un entier naturel (noté ND) caractérisant la table associée à la machine (notée DS) on peut construire une "machine à calculer universelle" qui se comporte comme n'importe quelle machine particulière.
Les articles 8 à 10 sont des "applications" de cette machine universelle pour monter qu'il existe des séquences non calculables ; que la calculabilité de Turing est "pertinente" et qu'elle peut exprimer la notion de fonction récursive au sens de Hilbert-Gödel (démonstration très technique d'un point de vue logique) et enfin que le problème de la décision posé par Hilbert n'a pas de solution.
L'appendice est un rajout (publié plus tard en 1936) qui donne une esquisse de l'équivalence entre la calculabilité au sens de Turing et le lambda-calcul de Church (qui a abouti à une conclusion négative similaire sur le problème de la décision en 1935).

La troisième partie intitulée : "Intelligence artificielle et logique naturelle" est rédigée par Jean-Yves Girard. Elle introduit très succinctement la quatrième partie de l'ouvrage sans reprendre la question de l'intelligence des machines comme Turing l'a envisagée. Cette partie fait le bilan des problèmes logiques posés par l'I.A. à notre époque et montre que la logique classique (y compris la logique intuitionniste) est insuffisante pour résoudre ces problèmes et qu'aucune autre logique performante (y compris la "logique linéaire") n'a pu à ce jour combler ce manque.

La quatrième partie : "Les ordinateurs et l'intelligence" est un article rédigé par Turing en 1950 dans un style très lisible proche d'une vulgarisation scientifique ou l'auteur se pose la question de l'"intelligence des machines". Il remplace cette question très générale par une autre : "un ordinateur peut-il jouer au jeu de l'imitation ?". Après avoir décrit la notion d'ordinateur, Turing, tout en tenant compte de nombreuses objections possibles semble répondre positivement à cette question.

Notes :
Cet ouvrage a été publié en 1991 par : The London Mathematical Society pour les deux articles de Turing, par : Champ-Vallon pour la traduction française de "Computing Machinary and Intelligence" et mai 1995 pour la traduction française de "On Computable Numbers", les textes de Jean-Yves Girard et la composition du volume.

Mots clés :


© ADIREM-APMEP -2003- ISSN 1292-8054 Mise à jour 09/06/2018
Accueil Publimath  Aide à la recherche   Recherche Avancée   Aidez-nous à améliorer cette fiche 
Certification IDDN