Peut-on tout calculer ? Toute propriété mathématique est-elle décidable ?
Ces questions ont passionné les mathématiciens bien avant les premiers
ordinateurs. À l'âge de 24 ans, le britannique Alan Mathison Turing,
mathématicien génial, entre autres, imagine un concept de machine
théorique. Il établira une correspondance entre les notions de
calculable et de programmable sur cette machine imaginaire, ainsi
qu'avec celle de décidabilité.
Calcul 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
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
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.
2. Décidabilité et machines de Turing
Une propriété mathématique est dite décidable s'il existe un procédé
mécanique qui détermine, au bout d'un temps fini, si elle est vraie ou
fausse dans n'importe quel contexte possible. Selon cette définition,
la propriété « être divisible par » s'avère décidable pour
tous les couples d'entiers. On connaît en effet un algorithme,
c'est-à-dire une suite finie et non ambiguë d'opérations élémentaires,
qui, étant donnés deux nombres entiers A et B quelconques, dise si A
est ou n'est pas divisible par B.
Les propriétés qui s'expriment en langage mathématique, sont-elles
toutes
décidables ? Autrement dit, est-il possible de construire, pour toute
propriété mathématique explicitement définie, une procédure qui nous
indiquerait, au bout d'un temps fini, si cette propriété est ou n'est
pas vraie ? Telle est la question posée depuis la fin du XIXème siècle
par quelques mathématiciens, dont le très fameux David
Hilbert en
1918, et identifiée sous le nom de « problème de la
décision ». Les « systèmes formels » qui
traduisent, en termes mathématiques, les notions intuitives de
preuve, de démonstration et de théorème, conduisent naturellement à
poser cette question. En effet, si la réponse devait être affirmative,
toutes les propriétés mathématiques valides seraient des théorèmes
dérivables mécaniquement de quelques axiomes dans un système formel.
Existence de propriétés indécidables
En 1931, Kurt Gödel mit un terme à cette interrogation en montrant
qu'il existe des propriétés
mathématiques indécidables dans tous les systèmes d'axiomes définis
pour formaliser l'arithmétique.
Quelques années plus tard, en 1937, cette question reçut grâce à Alan
Turing une
nouvelle formulation. Celle-ci était à la fois plus claire, plus
concrète, du moins pour les informaticiens d'aujourd'hui, et ses
implications pratiques sont plus actuelles. Selon Turing, résoudre le
problème de la décision est équivalent à pronostiquer la terminaison de
l'exécution d'un programme informatique sur une machine de Turing.
Turing a démontré qu'il n'est pas possible de concevoir un algorithme
qui, étant donné un programme quelconque, nous avertisse avec certitude
et au bout d'un temps fini si ce programme doit éventuellement
« tourner en rond » et s'exécuter indéfiniment, sans trouver
jamais la sortie.
L'une des conséquences pratiques les plus essentielles pour les
informaticiens, c'est qu'on ne saurait construire un programme général
capable de prouver la terminaison de n'importe quel programme.
Décidabilité et calculabilité
Notons que la notion de décidabilité doit être rapprochée de celle de
calculabilité, ce qui explique l'emploi des machines de Turing pour
apporter une réponse au problème de la décision. En effet, à toute
propriété mathématique, il est toujours possible d'associer une
fonction numérique. Réciproquement, à toute fonction numérique, on peut
associer une propriété mathématique. Pour s'en convaincre, il suffit de
remarquer qu'une propriété mathématique P(a) est une fonction vers un
ensemble à deux valeurs, {vrai, faux} ou, ce qui est équivalent, {0,
1}. De façon symétrique, à toute fonction y = f(x), on peut
associer une propriété P(x, y) vraie si y = f(x) et fausse
sinon. En conséquence, le problème de la décision, c'est-à-dire la
recherche
d'une procédure qui indique dans chaque contexte, et au bout d'un temps
fini, si une propriété est vraie ou fausse, est équivalent à la
construction d'un algorithme qui calcule pour chaque fonction f et pour
chaque argument x de f, la valeur y telle que y = f(x).
Autrement dit, le problème de la décision est équivalent au problème du
calcul.