Les lexicologues nous l'enseignent, le mot « calcul » vient de calculus qui signifie caillou en latin. Pour se convaincre de la pertinence de cette dérivation, il suffit d'évoquer le décompte des nombres à l'aide de petits jetons : le calcul numérique tel que nous le connaissons aujourd'hui a été primitivement une manipulation d'objets matériels selon des règles bien définies. Qu'il se soit ensuite étendu à un décompte mental, avec ou sans support matériel, ou à des programmes informatiques exécutés automatiquement, sans présence humaine, le calcul n'en procède pas moins d'une combinaison réglée de symboles qui peuvent éventuellement être remplacés par des objets du monde matériel comme des cailloux. Nous avons tous l'intuition que de nombreuses fonctions mathématiques sont totalement réductibles à de telles manipulations.

1. De Church à Turing

Calcul et calculabilité

Ainsi, toute multiplication de nombres entiers peut être réduite à des additions successives. De même toute division se ramène à des additions et des soustractions. Quant aux additions et soustractions, elles se convertissent aisément en manipulations de symboles ou de cailloux. En revanche, nous avons l'impression que d'autres fonctions définies formellement semblent difficiles, voire impossibles à « caillouter ». Autrement dit, à décrire uniquement en termes de déplacements de cailloux.

Jusqu'où de telles manipulations peuvent-elles aller ? Quel est l'ensemble des fonctions f, exprimables en termes mathématiques, pour lesquelles il existe une succession de manipulations de symboles déterminant sans ambiguïté l'image de n'importe quelle valeur x par f ? C'est-à-dire un calcul de la valeur y telle que y = f(x) ? Autrement dit, quelle est la classe des fonctions calculables ? Telle est la question qu'aborde la calculabilité.

La thèse de Church

Alonso Church (1903-1995)

Pour y parvenir, des mathématiciens ont tenté, dans les années 1930, de donner une caractérisation mathématique du calcul qui réponde à l'intuition imprécise et vague que nous en avons, ce qui correspond à peu près à la notion de « cailloutage » décrite plus haut. Entre 1932 et 1936, Alonso Church et Stephen Kleene ont identifié, à l'aide de deux approches différentes, une classe de fonctions arithmétiques qui semblait posséder les propriétés intuitives des fonctions calculables. C'est ce qui a conduit Church à énoncer une conjecture appelée depuis « Thèse de Church », selon laquelle la classe de fonctions qu'ils avaient identifiée recouvrait exactement la classe des fonctions calculables au sens intuitif.

L'idée de Turing

Alan Mathison Turing (1912-1954)

Indépendamment, en 1937, Alan Turing a circonscrit, à l'aide du concept de machine de Turing, une autre classe de fonctions répondant elles aussi à l'intuition que l'on se fait des fonctions calculables. Simplification extrême des machines possibles, qu'elles soient réelles, futures, ou simplement concevables, ces machines ressemblent, à s'y méprendre, à des machines à écrire à ruban dont on aurait supprimé le clavier.

Plus précisément, elles se composent toutes d'un ruban infiniment long divisé en petites cases, sur lesquelles sont imprimés des idéogrammes puisés dans une réserve finie donnée par avance. Une petite fenêtre découvre l'une des cases de ce ruban à une tête de lecture, de sorte que la machine soit en mesure d'identifier l'idéogramme qui y est inscrit, de le gommer ou d'en imprimer un autre qui efface le premier. Le ruban peut se mouvoir vers la gauche ou vers la droite, de façon à placer l'une quelconque des cases qu'il contient sous la fenêtre.

La machine de Turing et ses états internes

Outre son ruban, les moteurs qui le déplacent, la petite fenêtre de lecture, d'effacement et d'impression, une machine de Turing possède ce que l'on désigne ici comme des « états internes », que je m'amuse à comparer à ce que les hommes appellent leurs « états d'âme ». Ceux-ci conditionnent les réactions de la machine qui peut être « enjouée », et sauter gaiement d'une case à une autre du ruban, ou être « dépressive » et tout effacer sur son passage, ou encore être « mélancolique » et revenir indéfiniment sur son passé.

Cependant, à la différence des hommes, chez qui les subtiles complexions de l'âme sont en nombre infini, les machines de Turing admettent un nombre fini d'états internes. Chacun conditionne de façon totalement déterministe les réactions de la machine aux nouveaux événements lus sur le ruban.

Enfin, une « table », ou ce qu'en termes modernes nous appellerions aujourd'hui un « programme », décrit, pour chaque état interne, l'action exacte que la machine doit exécuter. Les actions possibles : « déplacement » du ruban vers la gauche ou vers la droite, « lecture, effacement ou impression » d'un idéogramme sur la case du ruban qui se trouve juste sous la fenêtre, et enfin, « arrêt définitif », ainsi que l'état interne qui s'ensuivra.

Calculabilité au sens de Turing

Revenons maintenant aux fonctions calculables : Turing montra, en 1937, que la classe des fonctions calculables, au sens de Church, était équivalente à la classe des fonctions programmables sur les machines imaginaires qu'il avait conçues. En son hommage, ces dernières sont connues depuis sous le nom de machines de Turing.

La notion de fonction calculable au sens de Turing suggère fortement l'existence d'une procédure de calcul, puisqu'elle assimile ces fonctions à celles qui sont exécutables sur une machine de Turing. Certes, les machines de Turing sont d'une complexion étrange et bien abstraite, qui fait fi des limitations de temps et d'espace, ce qui interdit toute réalisation physique de l'une d'entre elles. Mais à chaque instant, leur fonctionnement fait appel à un nombre fini de règles de calcul parfaitement définies et intelligibles, que nous pourrions nous-même exécuter sans difficulté. Les fonctions calculables au sens de Turing sont donc toutes calculables au sens intuitif.

Des fonctions non-calculables

Il existe donc aussi des fonctions qui ne sont pas calculables par un moyen purement automatique. On peut se demander s'il s'agit de fonctions « pathologiques », des monstres qui ne servent à personne, ou bien s'il y a des fonctions utiles qui ne sont pas calculables. Il y en a ; en fait beaucoup de fonctions utiles ne sont pas calculables. On peut en citer deux qui sont utiles et qui sont simples à décrire : vérifier qu'un programme s'arrête quelles que que soient ses entrées ; prouver qu'une formule logique est un théorème.

Certains programmes entrent parfois dans des boucles de calcul dont ils ne peuvent plus sortir. C'est la hantise des étudiants en programmation, et c'est aussi une belle bourde pour un programmeur. Imaginons la fonction qui analyse le texte d'un programme quelconque et détermine si ce programme s'arrête pour toutes les entrées possibles. Elle résout un problème crucial, mais elle n'est pas calculable purement automatiquement pour tous les programmes.

L'autre fonction concerne la logique. Formaliser un problème à l'aide de formules logiques (quel que soit, il existe, implique, et, ou, non...) est censé aider à le résoudre, mais cela conduit invariablement à tenter de démontrer des théorèmes. Il serait vraiment très commode qu'une fonction qui prend une formule en paramètre et détermine si elle est un théorème soit calculable. Cependant, ce n'est pas le cas, et beaucoup d'autres fonctions qui sont très utiles ne sont pas calculables non plus.