On Computable Numbers
Plus d'infos
- Créé par
- Alan Turing
- Année
- 1936
- Type
- Article scientifique
L'article d'Alan Turing de 1936, qui a inventé l'ordinateur en tant qu'objet mathématique avant que quiconque n'en ait construit un.
Titre complet : On Computable Numbers, with an Application to the Entscheidungsproblem. Turing avait 23 ans ; il le soumit en mai 1936 et le fit publier dans les Proceedings of the London Mathematical Society. Le sujet était le problème de la décision de Hilbert : existe-t-il une procédure mécanique qui détermine si un énoncé mathématique arbitraire découle des axiomes ? Pour y répondre, il fallait d'abord définir ce que « procédure mécanique » veut dire, ce que Turing fit en décrivant une machine imaginaire dotée d'un ruban infini, d'une tête de lecture et d'une table d'états.
Tout le reste découle de cette définition : une machine universelle capable de simuler n'importe quelle autre machine à partir de sa description sur le ruban, une preuve qu'aucune machine ne peut décider si une machine arbitraire s'arrête un jour, et donc une réponse négative à Hilbert. Alonzo Church était parvenu à la même conclusion quelques mois plus tôt avec le λ-calcul, ce qui faillit faire échouer la publication — Turing dut ajouter un appendice démontrant l'équivalence des deux formulations. Le véritable héritage de l'article n'est pourtant pas la preuve, mais l'incise sur la machine universelle : une machine dont le programme est une donnée.