David Madore's WebLog: Problème de l'arrêt de problème de Post

Index of all entries / Index de toutes les entréesXML (RSS 1.0) • Recent comments / Commentaires récents

Entry #2092 [older|newer] / Entrée #2092 [précédente|suivante]:

(lundi)

Problème de l'arrêt de problème de Post

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.

↑Entry #2092 [older|newer] / ↑Entrée #2092 [précédente|suivante]

Recent entries / Entrées récentesIndex of all entries / Index de toutes les entrées