Alan Turing : du calculable à l’indécidable  

2. Décidabilité et machines de Turing

Décidabilité

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.

David Hilbert (1862-1943)

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

Kurt Gödel (1906-1978)

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.