Je donnais jeudi matin une très
courte[#] introduction à la
calculabilité, dans le cadre d'un cours intitulé Théorie des
Langages
(donc un sujet plutôt connexe que contenant) dont
j'enseigne à un groupe ; des circonstances anecdotiques (des feutres
manquants[#2] au début de la
séance, les élèves qui filent pour aller à un partiel à la fin) ont
fait que je n'ai pas pu la finir correctement. J'ai donc envoyé des
notes écrites[#3] aux élèves,
auxquelles je n'ai pas résisté à la tentation d'ajouter quelques
compléments en petits caractères. Comme ces notes (qui sont très
basiques et passablement informelles même par rapport à ce que j'ai pu
raconter sur le sujet sur ce blog) peuvent peut-être intéresser
d'autres gens,
je les
mets en ligne ici. L'approche choisie consiste à ne pas
chercher à définir formellement ce qu'est un algorithme
(que ce
soit par une machine de Turing ou autrement), vu que de toute façon on
ne demandera à personne de programmer une machine de Turing, et
pédagogiquement il semble que si on formalise un modèle de calcul,
cela paralyse les étudiants au point qu'ils ne comprennent plus la
notion d'algorithme alors qu'en entrant ils savaient.
[#] Et je trouve véritablement triste que dans une grande école dont l'informatique est une des spécialités, le seul contact que tous les élèves auront avec des notions aussi fondamentales que le problème de l'arrêt ou la notion de problèmes décidable et semi-décidable, c'est une séance d'une heure et demie dans le cadre d'un cours plutôt consacré à autre chose (et sur laquelle il est donc difficile de les interroger à l'examen).
[#2] Obtenir des feutres qui marchent au début de chaque cours peut être une véritable quête du graal.
[#3] Ils ont aussi un poly de cours (il n'a pas l'air d'être disponible publiquement), mais j'ai suivi une présentation différente dans mon exposé, suivant le principe qu'on comprend parfois mieux quand les choses sont expliquées deux fois de façon différente, et du coup j'ai repris mes notations dans ces notes.
Ajout () : plusieurs années plus tard, j'ai créé un cours à Télécom dont une bonne partie concerne la calculabilité : j'ai fait un bilan de la première année de ce cours dans un billet ultérieur.
⁂
Mais même en racontant des choses très basiques, on peut apprendre des choses ou s'éclaircir les idées. Notamment sur deux points, tous deux plus ou moins liés à l'énumération φ0,φ1,φ2,… des fonctions calculables partielles ℕ⇢ℕ. Il faut comprendre qu'on numéroté les programmes, par exemple par taille puis par ordre lexicographique, et que φe(n1,…,nk) est le résultat de l'exécution du e-ième programme auquel on fournit les arguments n1,…,nk, la valeur étant indéfinie si le programme ne (s'exécute pas correctement ou) ne termine pas. Un point important est qu'il existe un programme universel, c'est-à-dire que la fonction (e,n) ↦ φe(n) est elle-même calculable (informatiquement, cela signifie qu'on peut écrire un « interpréteur », qui prend un programme e et un paramètre n et exécute le programme sur cette entrée ; philosophiquement, cela signifie que le fait d'exécuter un algorithme est lui-même algorithmique). Les deux points qui m'avaient un peu échappés sont les suivants :
✱ Le premier point concerne le théorème s-m-n de Kleene. Si h(m,n)=φe(m,n) est une fonction calculable des deux variables m,n, alors pour chaque valeur de m elle est calculable dans la variable n : ça c'est plus ou moins une évidence ; mais ce qui l'est moins, c'est qu'on peut algorithmiquement fabriquer un indice s(e,m) pour cette fonction, au sens où φs(e,m)(n) = φe(m,n) avec s une fonction calculable — c'est ça que dit le théorème s-m-n. Informatiquement, cela signifie qu'il y a une transformation algorithmique (le s en question) qui prend un programme e prenant deux arguments m et n (ou en fait, deux jeux d'arguments), et une valeur à donner au premier, et qui renvoie un nouveau programme s(e,m) où ces arguments ont été fixés à cette valeur. Dans toute formalisme de calcul précis (que ce soit les machines de Turing, ou un langage de programmation réel), c'est plus ou moins évident — dans un langage de programmation fonctionnel, par exemple, cela signifie curryfier la fonction et appliquer à une constante — et la fonction s sera mieux que calculable (elle sera primitive récursive, et certainement beaucoup mieux que ça, parce que ce n'est pas un problème algorithmiquement difficile de substituer une valeur dans un programme !). Mais comme je n'introduisais pas de modèle de calcul précis, je me suis demandé si ça pouvait se démontrer in abstracto, à partir de la simple existence de l'énumération des fonctions calculables partielles et l'existence d'un programme universel.
La réponse est non, il existe des numérotations des fonctions calculables partielles qui vérifient le théorème d'universalité mais pas le théorème s-m-n. Un contre-exemple est fourni en définissant à partir d'une numérotation standard φe une nouvelle numérotation ψ‹v+1,e›(0)=v (et ψ‹v,e›(0) non définie), et sinon, ψ‹v,e›(n)=φe(n) (dans tout ça, ‹x,y› désigne un codage quelconque des couples d'entiers naturels par des entiers naturels) : autrement dit, dans la numérotation ψ, on précise séparément la valeur en 0 de la fonction (y compris « non définie ») et ses autres valeurs via une numérotation standard. Sur cet exemple, toute fonction calculable partielle apparaît bien dans les ψ, mais on ne peut pas calculer, à partir de d'un indice e d'une fonction calculable partielle h parmi les ψ, un tel indice pour la fonction constante de valeur h(1), car il faudrait pour cela déterminer si h(1) est défini (i.e., termine), donc résoudre le problème de l'arrêt. Donc on ne peut pas faire de substitution dans les ψ de façon algorithmique.
Pour raconter ce contre-exemple dans des termes informatiques,
imaginons un langage de programmation permettant de coder des
fonctions ℕ⇢ℕ (ou ℕk⇢ℕ, enfin peu importe) et
qui est un langage tout à fait banal à une particularité près : la
valeur en 0 de la fonction (qu'il s'agisse d'un entier ou du fait de
partir en boucle infinie) doit être précisée par une instruction
spéciale au début du programme, la seule instruction qui sera lue pour
calculer cette valeur en 0, les autres valeurs étant calculées par un
programme « normal » (par ailleurs, cette bizarrerie ne s'applique
qu'à la fonction main
, si j'ose dire, du programme).
Interpréter ce langage, ou le compiler vers un autre, ne pose pas de
problème particulier, et ce langage permet de représenter toutes les
fonctions calculables partielles, ou d'ailleurs d'écrire un
interpréteur pour un langage standard (une machine de Turing, disons)
ou quelque chose comme ça. Mais il ne vérifie pas le théorème s-m-n,
et ceci cause des bizarreries : on ne peut pas, par exemple, compiler
un programme vers ce langage sauf à calculer à la
compilation la valeur de la fonction en 0, ce qui risque de
provoquer une boucle infinie ; et on ne peut pas algorithmiquement
remplacer un programme dans ce langage par le programme qui calcule la
(fonction constante égale à la) valeur en 1 de cette fonction. Ceci
suggère que le terme Turing-complet
est défini de façon un peu
trop vague : à mon avis, ce qui importe est que l'énumération des
fonctions partielles calculées par le langage considéré soit non
seulement l'ensemble de toutes les fonctions calculables partielles,
mais aussi que la numérotation soit acceptable
au sens où on
peut de façon calculable convertir une machine de Turing en
le langage en question, et on peut montrer que cela revient exactement
à vérifier le théorème s-m-n (avec une fonction s
calculable).
(Référence pour tout ça : Soare, Recursively Enumerable Sets and Degrees, 1987, chapitre I, exercices 5.9 à 5.11. C'est de là que je tire le contre-exemple au théorème s-m-n.)
✱ Le second point concerne la fonction « castor affairé », qui à n associe le plus long temps d'exécution possible d'une machine de Turing à ≤n états et qui termine effectivement (en partant d'un ruban vide). Il est facile de voir que fonction, appelons-la h, dépasse infiniment souvent n'importe quelle fonction calculable [totale] f, au sens où, quelle que soit f calculable, il existe une infinité de n tels que h(n)≥f(n). (En effet si ce n'est pas le cas pour une certaine fonction f, quitte à modifier un nombre fini de valeurs de celle-ci, on a h(n)≤f(n) pour tout n, et on peut alors résoudre le problème de l'arrêt pour une machine de Turing — partant d'un ruban vide — en attendant f(n) étapes où n est son nombre d'états : si la machine ne s'est pas arrêtée au bout de ce temps-là, elle ne s'arrêtera jamais.) Mais le résultat classique dû à Tibor Radó est plus fort : la fonction h du « castor affairé » finit par dominer n'importe quelle fonction calculable f, au sens où, quelle que soit f calculable, l'inégalité h(n)≥f(n) est toujours vraie à partir d'un certain point, et je n'avais pas vraiment fait attention au fait que ce n'est pas trivial de passer de l'un à l'autre.
La démonstration d'origine de ce résultat (trouvable ici) est d'une part assez peu lisible (j'arrive à la suivre pas à pas, mais l'idée générale m'échappait) et d'autre part très spécifique au cas de la fonction « castor affairé » sur les machines de Turing en comptant leurs états. Par exemple, si on définit la fonction h en appelant h(n) la plus grande des valeurs φe(0) (ou φe(e), peu importe) qui soient définies pour 0≤e≤n (l'argument montrant qu'elle dépasse infiniment souvent toute fonction calculable marche essentiellement pareil), alors est-il encore vrai que h finit par dominer n'importe quelle fonction calculable ? La réponse est oui, comme il résulte d'un échange sur math.stackexchange (je n'ai pas osé aller sur MathOverflow pour cette question), où on a pu m'expliquer beaucoup plus clairement l'argument de Radó, ce qui m'a permis de le généraliser facilement.
(J'en ai profité pour apprendre ce qu'est un degré de Turing hyperimmune, à savoir qu'il calcule une fonction qui dépasse infiniment souvent n'importe quelle fonction calculable, ce qui n'implique pas automatiquement qu'il calcule une fonction qui finit par dominer n'importe quelle fonction calculable.)
✱ Sinon, de fil en aiguille,
je suis
tombé par accident sur la relation suivante : pour A
et B deux ensembles d'entiers naturels,
notons A∼B lorsqu'il existe deux fonctions
calculables partielles ℕ⇢ℕ qui se restreignent en des bijections
réciproques entre ces deux ensembles. C'est une notion qui me semble
extrêmement naturelle, mais qui n'est pas ce qu'on appelle de
façon standard
un isomorphisme
calculable
entre les deux ensembles. Mais ce qui me frappe,
c'est que je n'ai réussi à en trouver aucune mention dans la
littérature. [Mise à jour : il s'agit de la relation
d'équivalence calculable
(ou équivalence récursive
),
dont les types ont été, en fait, largement étudiés, notamment ceux qui
s'appellent les isols
; voir pour commencer le livre de Dekker
et Myhill de 1960, Recursive Equivalence
Types, ainsi que le survey par Dekker et
Ellentuck, Myhill's work in recursion
theory
, Ann. Pure Appl. Logic 56
(1992), 43–71, et les références qu'il contient.]