Introduction
Alan Turing est généralement connu en informatique et en logique pour avoir conçu le modèle de calcul aujourd’hui appelé « machine de Turing » [Turing 1936]. La machine de Turing occupe en effet une place centrale dans ces deux domaines. En informatique, la machine de Turing est le modèle théorique des ordinateurs modernes, tandis qu’en logique, elle est la formalisation de la notion de fonction calculable.
On considère généralement qu’une fonction est calculable lorsque l’on dispose d’une méthode qui permet de la calculer. Une telle méthode, appelée en logique « procédure effective », définit précisément une séquence d’opérations, de sorte que chaque opération soit explicitement définie et que l’exécution de la séquence se termine dans un temps fini. Ainsi, pour montrer qu’une fonction est calculable, il suffit d’exhiber une procédure effective qui permet de la calculer. En revanche pour déterminer si une fonction n’est pas calculable, il ne suffit pas de tester l’ensemb...
