Rappel de l'épisode précédent : Turing et Church ont chacun leur définition de ce que l'on peut calculer. Le premier utilise de petites machines à états qui écrivent sur des bouts de papier, le second des équations mathématiques qui font peur (un peu). Aucun des deux n'a de preuve. Lequel a raison ?
Comprenez bien pourquoi ni l'un ni l'autre n'avait de preuve de ce qu'ils avançaient : une fonction calculable, ça ne se trouve pas dans la rue. On ne peut pas dire ce que c'est avant de l'avoir définie. En fait, leur vrai problème, c'était de savoir si leur définition correspondait à l'intuition que nous avons des fonctions que l'on sait calculer.
Comment être sûr qu'il ne manquait pas un petit truc dans leur définition ? C'est là qu'est venue l'idée de génie : les deux définitions, celle de Turing et celle de Church, sont exactement équivalentes. Les machines de Turing, avec leur bout de papier infini et leurs états, sont capables de calculer exactement les même fonctions que les équations de Church qui font des noeuds dans la tête.
Qu'est-ce que ça change ? Imaginez qu'ils se soient trompés : cela voudrait dire qu'ils se sont trompés tous les deux exactement de la même manière. Alors même que leurs définitions n'ont rien, mais alors rien à voir ! (D'ailleurs, ce n'est pas facile de montrer qu'elles sont équivalentes.)
C'est ce que l'on appelle la thèse de Church-Turing. Notez bien que ce n'est pas un théorème, ni une propriété. C'est une thèse, une théorie si vous préférez. Comme ces deux définitions traduisent chacune une intuition des fonctions calculables (Turing, l'intuition des opérations faites sur un bout de papier par un humain ; Church, celle des mathématiciens), et comme elles sont équivalente, on a décidé de les prendre comme une définition de ce qui est calculable.
Et les ordinateurs dans tout ça ? Eh bien, croyez-le ou non, mais vos bêtes de courses technologiques tétracore quadricanaux ne sont rien de plus que des machines de Turing. Elles ont une mémoire (la RAM) à la place du papier, un processeur à la place des états, mais elles ne font rien de plus.
Et il y a des fonctions non calculables, alors ? Oui. Par exemple, donnez à un ordinateur le code d'une programme informatique en entrée, et demandez-lui de vous répondre 0 si le programme s'arrête, et 1 si le programme ne s'arrête jamais. Le mieux qu'il pourra faire, c'est lancer le programme et voir s'il s'arrête. Donc, si la réponse est 0, il la donnera un jour (peut-être dans longtemps). Par contre, si la réponse est 1, il n'a aucun moyen de le savoir (pour être plus précis, il peut le savoir parfois, mais en général, il n'a pas de moyen de répondre). C'est ce qu'on appelle une fonction semi-calculable, ou un problème semi-décidable (parce qu'on peut répondre dans la moitié des cas seulement).
Vous remarquerez que le fait qu'un programme ne s'arrête jamais peut être considéré comme un bug. Il faut donc se résigner : il est impossible de décider mécaniquement si un programme informatique quelconque contient des bugs, aussi simplement qu'on ferait une addition. C'est pour cela que les chercheurs en informatique essayent de développer d'autres techniques pour s'assurer que les programmes n'ont pas de bugs (par exemple, démontrer mathématiquement que les programmes sont corrects, comme j'en ai parlé dans un billet précédent, mais cela ne peut donc pas être fait totalement automatiquement).