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.
Bernard PIRE
Retour en haut
