Je voudrais à nouveau tenter un
peu de vulgarisation autour de la calculabilité, cette fois-ci pour
parler du problème de Post dont je regrette qu'il soit trop
mal connu des matheux et informaticiens. Bon, déjà le nom
pose une difficulté, parce qu'il y a
deux choses différentes connues sous le nom de problème de Post
(pas totalement sans rapport, toutes les deux du domaine de la
calculabilité et liées au problème de l'arrêt, mais néanmoins bien
distinctes). Celle dont je ne veux pas parler est
le problème
de correspondance de Post
: comme ce dernier est nettement
plus connu que le problème de Post dont il est question ici, cela
cause un certain nombre de confusions désagréables. Une autre
difficulté tient de façon plus générale à la terminologie du domaine
(comme
le faisait
remarquer il n'y a pas longtemps mon ami David Monniaux) : ce
qu'on appelle problème décidable
s'appelle aussi ensemble
récursif
(et problème semi-décidable
aussi ensemble
récursivement énumérable
). Bref, essayons d'y voir plus
clair.
D'abord, il faut expliquer ce qu'on entend par un problème de
décision : en bref, c'est une question mathématique bien définie
et dont la réponse doit être oui
ou non
. En un peu plus
précis, c'est un problème qui prend en entrée une donnée
finie (c'est-à-dire, par exemple, un entier, ou une chaîne finie
de caractères, ou une donnée combinatoire finie par exemple un graphe)
et qui doit répondre à une question mathématiquement précise sur cette
donnée. Un exemple de tel problème serait : le nombre p
que voici (la donnée du problème) est-il un nombre premier ? Ou
encore : exise-t-il
un circuit
hamiltonien dans le graphe que voici ? Il est toujours possible —
c'est même la définition ce que j'entends par donnée finie
— de
coder[#] la donnée sous la forme
d'un entier naturel (par exemple, une chaîne de caractères peut se
coder comme une suite finie d'entiers, et une suite finie d'entiers
peut elle-même se coder sous la forme d'un entier par exemple en
utilisant la décomposition en facteurs premiers ou diverses
manipulations sur l'écriture binaire ou décimale). À cause de
ça[#2], on peut tout simplement
considérer qu'un problème de décision est un ensemble d'entiers
naturels : le problème est alors simplement de savoir si tel ou tel
entier donné appartient ou non à l'ensemble. On peut aussi préférer
considérer — de la même manière — qu'on a affaire à un ensemble de
chaînes (finies) de caractères, ce qu'on appelle
un langage : les notions de problème de décision,
d'ensemble d'entiers naturels, ou de langage, sont essentiellement
équivalentes.
On dit qu'un problème de décision est décidable (oui, la
terminologie est épouvantable…) lorsqu'il existe un algorithme pour le
résoudre : c'est-à-dire qu'il prend en entrée la donnée du problème,
effectue des calculs bien définis, et termine toujours en temps fini
en répondant soit oui
soit non
à la question posée.
Lorsque je dis effectue pendant un temps fini des calculs bien
définis
, la formalisation sous-jacente est celle de la
calculabilité au sens de Church-Turing (définie par
une machine de
Turing ou par
le λ-calcul non
typé ou par
le langage
FlooP). Comme je le disais plus haut, on parle aussi
d'ensemble récursif
(on peut considérer ce terme comme synonyme
de problème décidable
) si on préfère voir le problème comme un
ensemble d'entiers.
Je souligne que la notion de problème décidable ne fait aucune hypothèse sur le temps passé à résoudre la question — à part qu'il soit toujours fini. Ainsi, à l'intérieur des problèmes décidables, il y a tout ce qui concerne la complexité, entre les ensembles primitifs récursifs dont je parlais il y a quelque jour, les problèmes polynomiaux, et tout le reste du zoo. Notamment, le problème de trouver un circuit hamiltonien dans un graphe, il est peut-être difficile du point de vue de la complexité (NP-complet), mais il est certainement décidable : il suffit par exemple d'énumérer toutes les permutations des sommets du graphe et voir si l'une d'elles place de façon adjacente des sommets reliés par une arête.
Il existe beaucoup d'exemples en mathématiques de problèmes de
décision qui ne sont pas décidables. Par exemple celui-ci :
donné un énoncé mathématique dans le langage de l'arithmétique
formelle du premier ordre, déterminer si cet énoncé est vrai
ou non (on peut parler du problème de la vérité arithmétique
).
Ou encore celui-ci (qu'on a parfois par erreur tendance à considérer
comme équivalent) : donné un tel énoncé, déterminer si cet énoncé est
ou non un théorème de
l'arithmétique de
Peano (ou de tout autre système formel, mais je prends Peano comme
exemple pour rester dans le cadre de l'arithmétique). Il se trouve
que, dans un certain sens, ce second problème (décider
la théorémitude
) est beaucoup plus
facile[#2b] que le
premier (décider la vérité), mais les deux sont indécidables.
Une classe plus étendue que les problèmes décidables, et qui
recouvre quasiment tous les problèmes de décision intéressants en
mathématiques, est constituée des
problèmes semi-décidables. Ceci signifie qu'il existe un
algorithme qui prend en entrée la donnée du problème et qui : si la
réponse est oui
, finit toujours par répondre oui
en
temps fini, mais si la réponse est non
peut soit
répondre non
en temps fini soit continuer éternellement à
tourner sans jamais fournir de réponse (c'est cette dernière
possibilité qui fait la différence ; je souligne qu'elle n'est permise
que quand la vraie réponse est non
: autrement dit, comme dans
l'Administration française, l'absence éternelle de réponse est
interprétée comme une décision de refus).
Un exemple de tel problème semi-décidable est celui, que je
mentionnais plus haut, de savoir si un énoncé donné est un théorème
(disons, de l'arithmétique de Peano) : il suffit d'énumérer
systématiquement toutes les démonstrations possibles (en
explorant systématiquement toutes les applications possibles de toutes
les règles de la logique et toutes les instances des axiomes) : si on
finit par en trouver une qui termine sur l'énoncé recherché, on peut
répondre oui
, dans le cas contraire on ne répondra jamais (et
la vraie réponse est non
). Le problème de la vérité
arithmétique, en revanche, n'est même pas semi-décidable.
Un autre exemple de problème semi-décidable important est le
problème de la résolubilité des équations diophantiennes
(ou dixième problème de Hilbert) : ce problème prend en
entrée une équation diophantienne, c'est-à-dire une équation
polynomiale — à plusieurs variables — à coefficients entiers, dont on
cherche des solutions entières, et répond oui
ou non
selon qu'il existe des solutions entières. Le problème est bien
semi-décidable car on peut tester systématiquement toutes les valeurs
entières possibles (même si l'équation a plusieurs variables il n'est
pas difficile d'énumérer systématiquement tous les multiplets de
valeurs), et répondre oui
si l'une satisfait les équations,
tandis que si celles-ci n'ont pas de solution l'algorithme ne
terminera jamais.
Encore un autre exemple de problème semi-décidable est le problème de correspondance de Post, celui dont je ne parle ici, mais que je dois bien mentionner au passage. (Il s'agit d'un problème sur les mots : Wikipedia vous en dira plus.)
On peut remarquer, par ailleurs, que si un
problème est semi-décidable et que son complémentaire l'est aussi (où
le complémentaire
est le problème dans lequel les
réponses oui
et non
ont été échangées), alors les deux
sont en fait décidables : il suffit en effet de lancer en parallèle
les deux algorithmes, celui qui semi-décide le problème initial et
celui qui semi-décide le complémentaire — comme l'un finira toujours
par terminer, on aura la réponse voulue.
Parmi les problèmes semi-décidables (également appelés ensembles
récursivement énumérables
), il y en a un particulièrement
important, c'est celui qu'on appelle le problème de
l'arrêt, et pour insister je dirai même problème de
l'arrêt général (ou universel) : il s'agit du
problème qui prend en entrée un algorithme (de nouveau, au sens de
Church-Turing : disons, un programme dans un langage de programmation
idéalisé comme FlooP) et éventuellement une entrée à cet algorithme,
et qui répond oui
si l'algorithme terminera en temps fini
(i.e., s'arrête).
Il est assez clair que ce problème de l'arrêt général (A) est bien
semi-décidable et (B) permet de résoudre n'importe quel autre problème
semi-décidable. Pour ce qui est (A), il suffit d'exécuter
l'algorithme fourni et de répondre oui
si celui-ci finit par
terminer (et, s'il ne termine jamais, le méta-algorithme qui l'exécute
ne termine jamais non plus, ce qui compte comme réponse non
).
Pour ce qui est de (B), ce que je veux dire c'est que si on avait un
dispositif magique — un oracle — qui réponde
infailliblement au problème de l'arrêt, on pourrait s'en servir pour
répondre à n'importe quel problème semi-décidable : il suffit
d'interroger l'oracle sur l'algorithme qui semi-décide le problème
posé — si l'oracle répond que l'algorithme ne termine pas, on sait que
la réponse au problème posé est non
, tandis que si l'oracle
répond que l'algorithme termine, on n'a plus qu'à l'appliquer pour
avoir la réponse voulue.
Ce que je viens de dire là, c'est que le problème de l'arrêt général est, en gros, le plus difficile possible des problèmes semi-décidables, en ce sens que tout autre problème semi-décidable peut se ramener à lui (on dit que tout autre problème semi-décidable lui est Turing-réductible). Il serait a priori imaginable que le problème de l'arrêt général fût décidable : auquel cas tout problème semi-décidable serait, en fait, décidable ; mais Turing a montré que ce n'est pas le cas, donc la distinction n'est pas inutile. (Il y a une certaine analogie avec la question de savoir si P=NP, sauf que, justement, celle-ci est une question ouverte tandis qu'en calculabilité l'indécidabilité du problème de l'arrêt est assez facile à démontrer par un procédé diagonal.)
Une autre façon[#3] de voir
les choses est que, en fait, tout problème semi-décidable peut se
ramener à un problème d'arrêt particulier, c'est-à-dire celui
d'un algorithme bien précis (à savoir celui qui exécute l'algorithme
servant à semi-décider le problème et qui, si jamais ce dernier
termine en répondant non
, effectue une boucle infinie pour être
sûr de ne pas terminer). Donc, en un certain sens, tous les problèmes
semi-décidables sont des problèmes d'arrêt particuliers (et il est
évident que le problème de l'arrêt général est le plus difficile
possible).
Il existe quantité de problèmes mathématiques qui sont semi-décidables et qui sont en fait Turing-équivalents au problème de l'arrêt général, en ce sens que si on savait les résoudre alors on saurait résoudre n'importe quel problème semi-décidable (si on dispose d'un oracle qui répond au problème considéré, alors il existe un algorithme utilisant cet oracle et qui résout le problème de l'arrêt général — ou n'importe quel autre problème semi-décidable donné). Parmi ceux que je mentionnais plus haut, le problème de décider si un énoncé donné est un théorème est de la sorte (c'est assez facile à prouver), et il en va de même du problème de la résolubilité des équations diophantienne (c'est le théorème de Davis-Matiâsevič-Putnam-Robinson). Comme je l'ai expliqué, ceci signifie encore que ce sont des problèmes d'arrêt particuliers qui sont aussi difficiles que le problème de l'arrêt général.
Mais la question posée par Post en 1944 demande le
contraire : y a-t-il des problèmes semi-décidables qui ne sont
ni décidables ni équivalents au problème de l'arrêt ?
Autrement dit, sachant que les problèmes décidables sont les plus
« faciles » possibles et que le problème de l'arrêt est le plus
« difficile » parmi les problèmes semi-décidables, y a-t-il des degrés
strictement intermédiaires ? Ou, pour dire les choses encore
autrement, y a-t-il des problèmes d'arrêt particuliers
(c'est-à-dire des algorithmes particuliers dont on cherche à décider
s'ils terminent ou non selon l'entrée fournie) qui ne soient pas
décidables mais dont un oracle les résolvant ne permettrait pas non
plus de résoudre le problème de l'arrêt général ?
(Explicitement dit, on cherche à écrire un programme P
prenant une entrée x tel que la question
(★) P termine-t-il sur la valeur x ?
soit
indécidable comme fonction de x, mais que même si on
disposait d'un oracle permettant de répondre magiquement à cette
question (★) le problème de l'arrêt général resterait indécidable —
i.e., il subsisterait des programmes Q tels que la
question Q termine-t-il sur la valeur x ?
reste indécidable même en utilisant l'oracle.) C'est là le problème
de Post.
Emil Post lui-même a proposé quelques pistes pour résoudre la question, et les a utilisées pour résoudre une variante plus faible de son problème (où la réduction de Turing est remplacée par la réduction many-to-one, voir la note #3). Mais il est mort juste un peu avant d'avoir la réponse — positive — à son problème, qui a été apportée indépendamment en 1956 par Albert Mučnik et en 1957 par Richard Friedberg : il existe des problèmes semi-décidables de difficulté strictement intermédiaire entre le décidable et le problème de l'arrêt général.
On parle de degrés de Turing pour les classes des parties de ℕ modulo la réduction de Turing réciproque (c'est-à-dire qu'on identifie deux problèmes qui sont Turing-équivalents au sens où chacun est décidable au moyen d'un oracle qui répond à l'autre). Au sein des degrés de Turing on distingue les degrés r.é. qui sont les degrés des ensembles récursivement énumérables (=problèmes semi-décidables). Ceux-ci sont partiellement ordonnés pour la réduction de Turing : le plus petit degré r.é. (qui est aussi le plus petit degré de Turing tout court) est le degré 0 des problèmes décidables, et le plus grand degré r.é. est le degré 0′ du problème de l'arrêt général des machines de Turing. Le théorème de Friedberg-Mučnik affirme plus précisément qu'il existe des degrés r.é. a et b qui soient incomparables (on n'a ni a<b ni a>b), donc en particulier aucun d'entre eux n'est égal à 0 ni à 0′. Il y a quantité de théorèmes considérablement plus fins qui ont été montrés depuis : par exemple, que si a<b sont deux degrés r.é. strictement ordonnés, il en existe toujours un troisième c tel que a<c<b (théorème de densité de Sacks, 1964)[#4]. Ou encore qu'il existe un degré r.é. a tel que a>0 mais vérifiant a′=0′, où a′ désigne le [degré du] problème de l'arrêt général relativement à a, c'est-à-dire pour les machines de Turing disposant de [n'importe quel ensemble ayant pour degré] a comme oracle (un degré tel que a′=0′ est dit bas, et il est nécessairement <0′ puisque 0″>0′).
Je devrais insister sur le fait que la solution par
Friedberg-Mučnik du problème de Post (comme les autres variantes
citées en petits caractères ci-dessus, par exemple l'existence d'un
ensemble r.e. de degré bas) est tout à fait explicite : on écrit
vraiment un programme qui énumère un ensemble de nombres de tel sorte
que déterminer si un nombre donné sera énuméré soit un problème
indécidable (par définition semi-décidable), mais strictement plus
facile que le problème de l'arrêt général. Ce programme est, bien
sûr, hautement artificiel, mais en principe on doit pouvoir le coder
vraiment dans un langage quelconque — ce serait peut-être un exercice
amusant, d'ailleurs, même si l'exécution en serait démesurément
inintéressante. La technique utilisée s'appelle technique de la
blessure finie
(finite injury method) : on
énumère un certain nombre d'exigences sur ce qu'on veut mettre et ne
pas mettre dans l'ensemble (pour l'empêcher d'être récursif, et
empêcher qu'il résolve le problème de l'arrêt), on met sur ces
contraintes un ordre de priorité, et chaque contrainte imposte des
restrictions à toutes les contraintes moins prioritaires et peut être
« blessée » par une contrainte plus prioritaire auquel cas elle doit
s'adapter. Si vous êtes sages, un jour je vous expliquerai les
détails (qui sont moins compliqués que ce résumé vaseux le laisse
suggérer), au moins sur un cas très simple. On peut se rapporter à
l'excellent livre de Robert Soare, Recursively
Enumerable Sets and Degrees.
Mais il y a surtout une chose que je veux faire remarquer, c'est qu'on ne connaît aucun exemple d'un problème mathématique naturel (c'est-à-dire, non fait exprès pour) qui soit semi-décidable mais intermédiaire (i.e., ni décidable ni équivalent au problème de l'arrêt général), autrement dit, la solution au problème de Post est hautement artificielle et on ne connaît aucun problème naturel qui apporte une telle solution. Ceci peut s'interpréter de deux manières : soit que tous les problèmes mathématiques semi-décidables naturels sont vraiment décidables ou équivalents au problème de l'arrêt ; soit, de façon plus subtile, qu'il existe des problèmes intermédiaires naturels mais qu'on ne sait pas le montrer parce que la seule technique utilisée pour montrer qu'un problème semi-décidable est indécidable c'est justement d'y ramener le problème de l'arrêt général.
Par exemple, un problème ouvert notoire au confluent de la géométrie arithmétique et de la logique est celui de la résolubilité des équations polynomiales sur les rationnels (voyez ici pour une discussion) : contrairement au cas des entiers qui est traité par le théorème de Davis-Matiâsevič-Putnam-Robinson, le cas des rationnels n'est pas connu — on ne sait pas si ce problème (manifestement semi-décidable) est décidable ou non. Il est possible qu'il existe un algorithme (il est même possible qu'on connaisse déjà l'algorithme, en fait : le tout est de savoir s'il termine toujours) ; il est possible qu'il n'en existe pas parce qu'on pourrait y ramener le problème de l'arrêt. Mais il est aussi possible a priori que ce soit un exemple naturel d'un problème intermédiaire, et que la raison pour laquelle cette question résiste est que, justement, le problème ne serait ni décidable ni équivalent au problème de l'arrêt. Si c'était le cas, une preuve dans ce sens serait à mes yeux un des résultats les plus spectaculairement remarquables des mathématiques (et je trouverais ça beaucoup plus impressionnant qu'une preuve de l'hypothèse de Riemann).
[#] Évidemment, il faut aussi que ce codage soit lui-même raisonnable (par exemple, primitif récursif).
[#2] Il y a une chose
que je passe un peu sous silence, et qui mériterait peut-être pourtant
d'être discutée, c'est la question des données implicites, ou des
problèmes sans données. Formellement, l'argument est que si le
problème de décision n'a aucune donnée en entrée, la réponse est
soit oui
, soit non
, et il n'y a rien à dire de plus
(peut-être qu'on ne connaît pas la réponse, mais elle existe et ne
dépend de rien, donc il n'y a que deux tels problèmes sans données :
le problème-dont-la-réponse-est-oui et le
problème-dont-la-réponse-est-non, qui sont aussi inintéressants l'un
que l'autre). Formellement, donc, cela clôt la question, même si on
peut avoir l'impression d'avoir été arnaqué (que la question
soit Dieu existe-t-il ?
— certes pas très bien définie
mathématiquement — ou ZFC est-il consistant ?
, on
a l'impression qu'il y aurait plus à dire) : la réponse consiste
souvent à ajouter un paramètre (par exemple,
transformer ZFC est-il consistant ?
en P est-il un théorème de ZFC ?
pour P une donnée variable du problème, à laquelle on peut
faire prendre la valeur 0=1
; ceci permettra, par exemple,
d'après
le théorème de
Davis-Matiâsevič-Putnam-Robinson, d'expliciter une équation
diophantienne qui — démontrablement dans l'arithmétique de Peano —
aurait une solution si et seulement si ZFC est
inconsistant).
[#2b] [Ajout
()] Le fait de savoir si un énoncé
arithmétique P est un théorème de l'arithmétique de Peano
est semi-décidable, comme je l'explique plus loin, et équivalent en
difficutlé au problème de l'arrêt (on peut dire que son degré de
Turing est 0′). Le fait de savoir si un énoncé
arithmétique P est vrai, en revanche, est quelque
chose de beaucoup plus subtil : la différence, si on veut, tient au
théorème de Gödel (il existe des énoncés arithmétiques vrais mais non
démontrables dans Peano, même en se limitant à des énoncés du
type telle machine de Turing (explicite) ne s'arrête jamais
—
par exemple la machine de Turing qui recherche une preuve d'une
contradiction dans Peano), mais la théorie de la calculabilité permet,
ici, d'avoir une vision différente du théorème de Gödel. En
fait, le degré de Turing des énoncés vrais de l'arithmétique est ce
qu'on note 0(ω) (le « ω-ième saut de Turing »), qui
est une sorte de borne supérieure des sauts de Turing
finis 0, 0′, 0″, 0‴, etc. (ce n'est
cependant pas la borne supérieure au sens usuel, mais c'est un
majorant de tout ça : on peut se convaincre que c'est un majorant
parce que tout énoncé du type problème d'arrêt itéré fini —
c'est-à-dire un problème d'arrêt de machines disposant elles-mêmes
d'un oracle de l'arrêt pour un problème d'arrêt itéré plus petit —
peut être écrit comme un énoncé arithmétique, que l'oracle de la
vérité arithmétique permet donc de résoudre). Tout ça pour dire que,
n'en déplaise aux formalistes qui veulent ne voir dans la recherche
des théorèmes mathématiques que l'unique façon d'accéder à la vérité,
ces deux concepts sont nécessairement différents. [Voir
une note ultérieure pour plus de
précisions.]
[#3] Techniquement, ce que je fais là, c'est une réduction plus fine que la réduction de Turing, à savoir la réduction many-to-one (je ne connais pas le terme français), qui diffère de la réduction de Turing en ce qu'on ne peut interroger l'oracle qu'une seule fois, à la fin du calcul, sans pouvoir changer la réponse qu'il donne (il faut donc adapter la question qu'on lui pose).
[#4] C'est d'autant plus étonnant que l'énoncé est faux si on remplace les degrés r.é. par les degrés de Turing en général : il existe des degrés de Turing minimaux, c'est-à-dire qu'ils sont strictement supérieurs à 0 mais qu'il n'y a rien strictement entre 0 et eux. Je dois dire que je trouve ça particulièrement mystérieux.