Institut Galilée L3 S6 – Année 2014–2015

Calculabilité
Notes de Cours

Résumé
À savoir
Les points les plus importants qu’il faut retenir du cours :
1. Calculabilité. On ne peut pas tout calculer avec un ordinateur. C’est-à-dire qu’il existe des
fonctions simples à énoncer mais qui ne sont calculables par aucun programme informatique.
2. Théorème de la Halte. Un exemple d’indécidable : il n’existe pas de programme qui
prend comme entrée un autre programme (son code source) et décide si celui-ci termine ou
part en boucle infinie.
3. Théorème de Rice. Tout ensemble de programme qui est est à la fois extensionnel et
non trivial est indécidable.
4. Thèse de Church-Turing. Tous les langages de programmation permettent de calculer
les mêmes fonctions. Ce qu’on peut calculer ne dépend pas du langage choisi.
5. Minimalité. On a besoin de très peu de choses pour pouvoir tout calculer. Il suffit de
savoir faire +1, −1, un test if) et un saut (goto). Les boucles for ne suffisent pas à tout
faire. Les boucles while sont suffisantes.

A savoir faire
Les idées importantes qu’il faut savoir manipuler :
1. Sémantique. Il faut savoir détailler l’exécution d’un programme étant donnée la sémanti-
que du langage. C’est une opération facile qui demande peu de réflexion mais un minimum
de rigueur et d’entraı̂nement sont nécessaires.
2. Compilation. Il faut savoir transformer un programme d’un langage dans un autre, étant
donnée la fonction de compilation. Là aussi, c’est une opération qui demande de la rigueur
et un peu d’habitude mais peu de réflexion.
3. Réduction. Il faut être capable de comprendre une preuve par réduction. Comprendre
l’idée et être capable de suivre la preuve. Trouver une preuve par réduction demande un
peu de réflexion et est donc plus difficile.

Cours : 12 janvier 2015 : Introduction et rappels

Historique : Hilbert, Russel (paradoxe du barbier), Gödel (paradoxe du menteur), Turing
(Church).
Rappels : ensembles, fonctions.
Injections / surjections / bijections.

TD : 12 janvier 2015
TD 01 : Ensemble, fonctions.

Jean-Yves Moyen & Luc Pellissier 1

Institut Galilée L3 S6 – Année 2014–2015
Cours : 16 janvier 2015 : Rappels, dénombrabilité, Cantor
Rappels : composition de fonctions.
Fonction caractéristique d’un ensemble, équivalence sous-ensemble / fonction caractéristique.
Fonctions partielles, convergence, divergence.
Cardinalité, infini, dénombrabilité, non-dénombrabilité.
Preuve d’indénombrabilité de P (N) (Cantor, diagonalisation).

Cours : 19 janvier 2015 : le langage While

Argument de cardinalité pour l’existence de fonctions non-calculables
Indénombrabilité de N → N vs dénombrabilité des chaı̂nes finies, donc des programmes.

Remarques sur la preuve de diagonalisation.

On peut bien évidemment construire une “énumération” qui contient l’anti-diagonale D. Par
exemple, D, A0 , A1 , A2 , . . . Mais on a alors une nouvelle énumération A00 = D, A01 = A0 , A02 =
A1 , . . . qui comporte une nouvelle diagonale D0 et donc une nouvelle anti-diagonale D0 qui n’est
pas dans l’énumération. Autrement dit, la preuve ne dit pas qu’il existe une partie absente de
chaque énumération. La preuve dit que chaque tentative d’énumération laisse de côté au moins
une partie.
Même si la preuve n’exhibe qu’une seule partie qui n’a pas été énumérée, on peut montrer que
l’écart entre dénombrable et non dénombrable est beaucoup plus grand. Même si on retire une
quantité dénombrable de réels, il en reste toujours une quantité non dénombrable. Autrement
dit, non seulement il existe des fonctions non calculable, mais il y a même une quantité non
dénombrable de fonctions non calculables. La plupart des fonctions sont non calculables. . .

le langage While : syntaxe.

While a un seul type de données : le type D des arbres binaires, défini par la grammaire
suivante.
·
D 3 d, e ::= nil |
d e
La syntaxe des programmes est donnée par la grammaire suivante :

Expressions 3 E, F ::= X (variable)

|d (constante)
| cons E F (cons)
| hd E (“tête” / fils gauche)
| tl E (“queue” / fils droit)
| =? E F (test d’équalité)

Commandes 3 C, D ::= X:=E (affectation)

| C;D (séquence)
| while E do{C}

Programmes 3 P ::=read X; C; write Y

Le langage While est extrêmement “pauvre” et ne dispose pas de constructions usuelles des
vrais langages de programmation. On va voir dans ce TD qu’on peut tout de même les écrire.

Jean-Yves Moyen & Luc Pellissier 2

Institut Galilée L3 S6 – Année 2014–2015
Sucre syntaxique
On utilisera les abréviations (“sucre syntaxique”) suivantes :
– false ≡ nil
·
– true ≡
nil nil
– if E then C équivaut à
Z:=E;while Z do{Z:=false;C}
– if E then C else D équivaut à
Z:=E;W:=true;
while Z do{Z:=false;W:=false;C}
while W do{W:=false;D}

Listes
·

La liste des n éléments [d1 , · · · , dn ] de D est représentée par l’arbre d1 ·

d2 ·

..
.
·

dn nil

Entiers naturels
Chaque entier n ∈ N est représenté par le “numéral” n ∈ D comme suit :

0 = nil ≡ [ ]
·
n+1= ≡ [nil, · · · , nil]
nil n | {z }
n + 1 fois

Remarque : nil représente aussi bien false, 0 ou la liste vide. . . Il faut donc que les pro-
grammes sachent quel va être le type de leur entrée (et de leurs variables) pour agir en consé-
quence. . . Et si on donne une “mauvaise” entrée au programme, il fonctionnera mais fournira un
résultat sans signification.

TD : 19 janvier 2015
(TD 01 : Ensembles, fonctions.)

Cours : 23 janvier 2015 : Sémantique de While

La sémantique d’un langage de programmation indique quel est le résultat d’un calcul (de
l’évaluation d’un programme sur une entrée donnée) ou, de manière équivalente, quelle est la
fonction calculée par un programme donné.
C’est quelque chose d’extrêmement important à connaı̂tre pour, par exemple, implémenter
le langage. Typiquement, un compilateur de C doit connaı̂tre la sémantique de C pour savoir ce
qu’il doit faire quand il rencontre chacun des mots clés. En poussant au maximum, il faut bien
à un moment expliquer au compilateur (ou à l’interprète) que if correspond à un test et for à
une boucle.

Jean-Yves Moyen & Luc Pellissier 3

Institut Galilée L3 S6 – Année 2014–2015
Évaluation des expressions
Une mémoire σ (ou un état de la mémoire, en anglais store) est une fonction qui associe à
chaque variable une valeur, c’est-à-dire un arbre binaire :

σ : Variables → D
Étant donnés une expression et une mémoire, on peut évaluer l’expression, ce qui renvoie une
valeur. Autrement dit, l’évaluation associe à chaque expression E une fonction totale EJEK des
mémoires vers les valeurs. On note EJEKσ la valeur de E quand la mémoire est σ :

EJ•K : Expressions → (Mémoires → D)

Expressions → Mémoires → D
E 7 → (σ 7 → EJEKσ)
La définition de EJEKσ est donnée par induction structurelle sur E selon les règles suivantes :

EJXKσ = σ(X)
EJdKσ = d
·
EJcons E FKσ =
EJEKσ EJFKσ


 ·
d si EJEKσ =
EJhd EKσ = d e


nil si EJEKσ = nil



 ·
e si EJEKσ =
EJtl EKσ = d e


nil si EJEKσ = nil

(
true si EJEKσ = EJFKσ
EJ=? E FKσ =
false sinon

Sémantique des commandes

L’évaluation d’une commande modifie la mémoire. On assocuie donc à chaque commande une
fonction des mémoires vers les mémoires. Comme une commande peut ne pas terminer (boucle
infinie), il s’agit d’une fonction partielle :
J•K : Commandes → (Mémoires → Mémoires⊥ )
Quand elle est définie, l’évaluation des commandes vérifie les règles suivantes :
(
X 7→ EJEKσ
JX:=EK(σ) =
Y 7→ σ(Y) si Y 6= X
JC;DK(σ) = JDK(JCK(σ)) = JDK(σ 0 ) avec σ 0 = JCK(σ)
Jwhile E do{C}K(σ) = σ si EJEKσ = nil
Jwhile E do{C}K(σ) = JC;while E do{C}K(σ)


= Jwhile E do{C}K JCK(σ) si EJEKσ 6= nil

Sémantique des programmes

La sémantique du langage While est la fonction :

J•K : Programmes → (D → D⊥ )

Jean-Yves Moyen & Luc Pellissier 4

Institut Galilée L3 S6 – Année 2014–2015
associant à un programme P = read X; C; write Y une fonction partielle des entrées vers les
sorties définie par
JPK(d) = e si JCK(σdX ) = σ et σ(Y) = e
où σdX est la mémoire initiale de P, qui associe d à X et nil à toutes les autres variables.

TD : 2 février 2015 ×2
(TD 02 : WHILE.) (TD 03 : Sémantique de WHILE.)

Cours : 9 février 2015 : Codage de While, théorème de la

Halte
Codage de While
On peut encoder les programmes de While sous forme d’arbre de D de manière injective,
c’est-à-dire que chaque code (arbre) correspond à un programme unique. On peut ainsi considérer
des ensembles de programmes comme des sous-ensembles de D et parler de leur décidabilité.
Si D contient au moins les 10 atomes {:=, ;, while, cons, hd, tl, =?, nil, var, quote} alors on
peut encoder les expressions, commandes et programmes de While comme suit (après avoir
numéroté les variables) :

pVi q = [var, i]
pdq = [quote, d]
pcons E Fq = [cons, pEq, pFq]
phd Eq = [hd, pEq]
ptl Eq = [tl, pEq]
p=? E Fq = [=?, pEq, pFq]

pC;Dq = [;, pCq, pDq]

pwhile E do{C}q = [while, pEq, pCq]
pVi :=Eq = [:=, [var, i], pEq]

pread Vi ; C; write Vj q = [[var, i], pCq, [var, j]]

Calculabilité
1. Une fonction partielle f : D → D⊥ est While calculable si et seulement si il existe un
programme While P tel que f = JPK, c’est-à-dire que pour tout d, e ∈ D :
– f (d) =⊥, si et seulement si JPK(d) =⊥.
– f (d) = e ∈ D, si et seulement si JPKd = e ∈ D.

Théorème de la Halte
Soit halt la fonction (mathématique) qui a comme arguments un programme (ou du moins
son encodage) P et un arbre d et qui indique si JPK(d) converge ou diverge :

halt(pPq, d) =true si JPK(d)↓.

halt(pPq, d) =false si JPK(d)↑.

Théorème 1 (Théorème de la Halte, Turing 1936). halt n’est pas calculable. C’est-à-dire qu’il
n’existe pas de programme While H tel que JHK = halt.

Jean-Yves Moyen & Luc Pellissier 5

Institut Galilée L3 S6 – Année 2014–2015
La preuve se fait par diagonalisation. On suppose que H existe et on va utiliser la technique
de la diagonale pour créer une absurdité.
Si H existe, il a nécessairement la forme read XH ; CH ; write YH où XH doit être un arbre
·
.
pPq d
On peut alors facilement construire le programme diag qui a un seul argument et l’utilise
pour remplacer les deux arguments de H :

read X ; (* X = pPq *)
·
XH :=cons X X; (* XH = *)
pPq pPq
CH ; (* Est-ce que JPK(pPq) converge ? *)
Y:=¬YH ;
while Y do{X:=X} ;
write Y ;

Le programme diag est d’accord avec H :

– Si JPK(pPq)↓ alors après avoir effectué CH , YH vaut true. Donc Y vaut false. Donc la
boucle n’est jamais effectuée et JdiagK(pPq)↓.
– À l’inverse, si JPK(pPq)↑, alors YH = false donc Y = true et la boucle est une boucle
infinie, donc JdiagK(pPq)↑.
Pour créer la contradiction, il faut construire non pas la diagonale, mais l’anti-diagonale,
antidiag :

read X ; (* X = pPq *)
·
XH :=cons X X; (* XH = *)
pPq pPq
CH ; (* Est-ce que JPK(pPq) converge ? *)
Y:=YH ;
while Y do{X:=X} ;
write Y ;

Maintenant, si JPK(pPq)↓, alors YH = true donc la boucle est infinie et JantidiagK(pPq)↑. À

l’inverse, si JPK(pPq)↑, alors JantidiagK(pPq)↓.
La contradiction se crée en appliquant antidiag à lui-même, c’est-à-dire avec P = antidiag.
Que vaut JantidiagK(pantidiagq) ?
– Si JPK(pPq)↓, alors JantidiagK(pPq)↑. Mais si P = antidiag, on obtient :
si JantidiagK(pantidiagq)↓, alors JantidiagK(pantidiagq)↑. Une impossibilité.
– De même, si JPK(pPq)↑, alors JantidiagK(pPq)↓. Mais si P = antidiag, on obtient :
si JantidiagK(pantidiagq)↑, alors JantidiagK(pantidiagq)↓. Une impossibilité.
Aucun comportement de JantidiagK(pantidiagq) n’est possible. D’où on déduit que antidiag
ne peut pas exister. Or le code de antidiag est immédiatement construit à partir de celui de H.
Donc H lui-même ne peut pas exister.
Autrement, si quelqu’un fournit un programme H, il est très facile de construire antidiag
(en gros, c’est un copier/coller de CH (qui peut contenir plusieurs millions de lignes)). Comme
antidiag ne peut pas exister, il en va de même pour H.

Jean-Yves Moyen & Luc Pellissier 6

Institut Galilée L3 S6 – Année 2014–2015
TD : 9 février 2015
(TD 04 : Codage de WHILE.)

Cours : 13 février 2015 : Preuves par réduction

La preuve du théorème de la Halte est par diagonalisation car une autre manière de voir
les choses est de numéroter les programmes et les arbres binaires (comme il y a une quantité
dénombrable de chacun d’eux, c’est possible). On a alors une énumération de tous les pro-
grammes : {P1 , P2 , · · · , Pn , · · · } et de tous les arbres binaires {d1 , d2 , · · · , dm , · · · }. Si H existe, on
peut l’utiliser pour construire un grand tableau à double entrée tel que tab[i, j] = JPi K(dj ).
diag est alors un programme qui correspond à la diagonale de ce tableaux. En gros, JdiagK(i) =
tab[i, i] (c’est un peu plus compliqué en vrai). Ce qui ne pose absolument aucun problème.
antidiag est un programme qui correspond à l’anti-diagonale. En gros, JantidiagK(i) 6=
tab[i, i]. Du coup, on ne peut pas avoir antidiag = Pi puisque par construction JPi K(i) =
tab[i, i] 6= JantidiagK(i).
Donc antidiag ne peut pas être un des programmes utilisés pour remplir le tableau, ce qui
est absurde puisqu’on a énuméré tous les programmes.

Preuves par réduction

Pour faire d’autres preuves de non-calculabilité, on n’a pas besoin de revenir à la diagonali-
sation à chaque fois. L’idée est de construire une absurdité de la forme :
 Si f était calculable, alors halt serait aussi calculable. 

Une telle implication se construit en faisant une réduction de halt vers f . C’est-à-dire en
trouvant une transformation calculable entre les entrées de halt et celles de f . C’est à dire
· ·
qu’il faut une fonction τ telle que f (τ ( )) = halt( ). Puisque halt n’est pas
pPq d pPq d
calculable, on ne peut pas calculer le membre droit de cette égalité. Donc on ne peut pas calculer
non plus le membre gauche. Ce qui implique que soit f soit τ n’est pas calculable.
Autrement dit, si f est calculée par un programme read Xf ; Cf ; write Yf et que τ est
calculée par read Xτ ; Cτ ; write Yτ , alors on pourrait calculer halt avec le programme :
read Xτ ; Cτ ; Xf :=Yτ ; Cf ; write Yf
Comme halt n’est pas calculable, c’est que soit f soit τ ne l’est pas non plus. Et donc si τ
est calculable, f ne l’est pas.
Par exemple, soit idem la fonction qui indique si deux programmes calculent la même chose :

·
idem( ) =true si JQK = JQ0 K
pQq 0
pQ q
·
idem( ) =false si JQK 6= JQ0 K
pQq 0
pQ q

Il faut donc qu’on trouve une transformation τ qui aille des entrées de halt vers les entrées
· ·
de idem, c’est-à-dire que τ ( )= , et qui vérifie la propriété idem(τ (x)) =
pPq d pQq pQ0 q
halt(x). Il faudra ensuite montre que τ est calculable.
La transformation est assez facile à décrire. En effet, on part de deux programmes Q et Q0
identiques (donc pour lesquels idem vaut trivialement true) et on modifie l’un des deux pour
que son fonctionnement dépende de la terminaison d’un programme arbitraire JPK(d). C’est facile
en faisant simplement un appel à P.

Jean-Yves Moyen & Luc Pellissier 7

Institut Galilée L3 S6 – Année 2014–2015
Autrement dit, on a P qui est de la forme read XP ; CP ; write YP . On commence par construire
Q le plus simple possible (par exemple, l’identité) :
read X; ; write X
et ensuite, on construit Q0 en ajoutant simplement l’appel à P(d) :
read X; XP :=d; CP ; write X
À noter que le résultat de P est jeté par Q0 . Seul sa terminaison est importante.
Que calcule Q0 ? Ça dépend de la terminaison de P sur l’entrée d. Si P termine, alors Q0 renvoie
X, sa variable d’entrée, et calcule l’identité, soit la même chose que Q. Par contre, si P ne termine
pas sur l’entrée d alors Q0 ne termine sur aucune entrée et calcule quelque chose d’autre que Q.
·
Autrement dit, si JPK(d)↓ (c’est-à-dire halt( ) = true), alors JQK = JQ0 K (c’est-à-dire
pPq d
·
idem( ) = true). À l’inverse, si JPK(d)↑, alors JQK 6= JQ0 K.
pQq pQ q 0

· · ·
Donc halt( ) = idem( ) = idem(τ ( )). Si on peut calculer
pPq d pQq pQ0 q pPq d
idem, alors on peut calculer τ .
Il reste à montrer que τ est calculable. Comme les programmes sont représentés par des listes,
τ ne fait que manipuler des listes et est assez simple à calculer. La construction du programme
correspondant est laissée en exercice. . .

Cours : 16 février 2015 : REC, RE, ordre de “difficulté”

Calculabilité, énumérabilité
1. Une fonction partielle f : D → D⊥ est While calculable si et seulement si il existe un
programme While P tel que f = JPK, c’est-à-dire que pour tout d, e ∈ D :
– f (d) =⊥, si et seulement si JPK(d) =⊥.
– f (d) = e ∈ D, si et seulement si JPKd = e ∈ D.
2. Un ensemble A ⊆ D est While décidable si et seulement si il existe un programme While
P tel que JPK(d) ↓ pour tout d ∈ D, et en plus d ∈ A si et seulement si JPK(d) = true. Dans
ce cas, la fonction caractéristique χA est While calculable.
3. Un ensemble A ⊆ D est While semi-décidable si et seulement si il existe un programme
While P tel que pour tout d ∈ D, d ∈ A si et seulement si JPK(d) = true (mais P peut
diverger sur les entrées n’appartenant pas à A).
4. Un ensemble A ⊆ D est While énumérable si et seulement si soit A = ∅ soit il existe un
programme While P tel que pour tout d ∈ D, JPK(d) ↓ et A = {JPK(d) ; d ∈ D}.
“Semi-décidable” est équivalent à “énumérable”. C’est-à-dire qu’un ensemble est semi-décidable
si et seulement si il est énumérable.
L’étape importante pour cette équivalence consiste à numéroter tous les arbres binaires (les
éléments de D). C’est possible de manière calculable (il existe une bijection calculable entre D et
N).
– Si un ensemble A est énumérable, pour le semi-décider, il faut répondre à la question d ∈ A?
soit par “oui”, soit en bouclant infiniment. On lance l’énumération de A (i.e. on liste tous
les éléments dans l’ordre) jusqu’à trouver d (ou boucler infiniment si d ∈ / A).
– Si un ensemble A est semi-décidable, on peut construire une énumération en lançant des
calculs en parallèle pendant un temps fixé à l’avance (pour éviter les problèmes de non-
terminaison). On commence par réfléchir à la question (exécuter le programme de semi-
décision) d1 ∈ A? pendant 1 seconde. Puis on réfléchit au deux questions d1 ∈ A? d2 ∈ A?
pendant 2 secondes, . . . À un moments, certaines questions vont avoir la réponse “oui”. On
énumère A dans l’ordre des “oui” obtenus.

Jean-Yves Moyen & Luc Pellissier 8

Institut Galilée L3 S6 – Année 2014–2015
REC, RE
Les fonctions calculables sont parfois appelées “Récursives” car elles correspondent au modèle
de calcul des fonctions récursives. C’est un autre modèle de calcul qui caractérise les mêmes
fonctions que les machines de Turing ou le langage While. Du coup, on note parfois REC
l’ensemble des fonctions calculables.
Les ensembles semi-décidables, ou énumérables, sont parfois appelés “Récursivement Énu-
mérable” car ils sont énumérables par une fonction récursive (au sens ci-dessus, c’est-à-dire
calculable). Plus précisément, le programme P du point 4 ci-dessus énumère tous les éléments de
A. Puisque c’est un programme, il correspond par définition à une fonction calculable. Du coup,
on note parfois RE (Recursively Enumerable) l’ensemble des ensembles énumérables.

Preuves par réduction

Lors d’une preuve par réduction, même si le choix de la réduction (de τ ) n’est pas complètement
trivial et peut demander un peu de réflexion, la démarche est toujours la même :
1. On cherche une entrée (généralement un programme) la plus simple possible pour laquelle
le résultat de f est évident. Généralement, un programme qui calcule l’identité ou une
fonction constante peut faire l’affaire.
2. On rajoute un appel à P(d) (l’argument de halt) de manière à ce que si l’appel ne termine
pas, le nouveau programme non plus, ce qui change la valeur de f sur ce programme.
Exemple : on veut montrer que la fonction g, telle que g(pQq) = true si et seulement si
JQK(3) = 5, est non calculable.
1. On cherche le programme le plus simple possible pour lequel la valeur de g est connue. Ici,
un programme qui renvoie toujours 5 convient, soit Q = read X; Y:=5; write Y.
2. On intercale un appel à un programme arbitraire P de manière à changer le résultat de
g, c’est-à-dire à changer le comportement de Q. Ici, comme souvent, il suffit de rajouter
l’appel à P tout au début. On obtient :
Q0 = read X; XP :=d; CP ; Y:=5; write Y.
·
On a bien g(Q0 ) = halt( ). Donc si on pouvait calculer g, on pourrait aussi calculer
pPq d
halt, ce qui est impossible. Donc g n’est pas calculable.
La notion de réduction est une notion générale qui n’est pas réservée à la calculabilité. En
particulier, elle apparaı̂t aussi dans le domaine de la complexité (voir cours de M1) et elle est
centrale pour comprendre le problème P = N P ? qui est l’un des problèmes ouverts les plus
important de l’informatique et des mathématiques actuels. C’est l’un des 7  problèmes du
millénium  de la fondation Clay.

Ordre sur les fonctions

La notion de réduction permet de définir un pré-ordre sur les fonctions. On dit que f est plus
facile que g, et on note f v g, si il existe une transformation calculable τ telle que pour toute
entrée x, on a f (x) = g(τ (x)). La notation v est faite pour rappeler ≤ mais en remplaçant le
triangle par un carré. C’est pour indiquer que c’est un pré-ordre qui se comporte donc beaucoup
comme ≤ (en particulier pour la transitivité).
Pourquoi cette relation implique que f est plus facile que g ? parce que si τ calculable existe,
on a alors la propriété suivante : si g est calculable, alors f est aussi calculable. f est donc  plus
facile  au sens  plus facilement calculable. 
À l’inverse, si f n’est pas calculable, alors g non plus (parce que τ est calculable). C’est
exactement ce qu’on a fait au début. On a montré (en exhibant τ ) que halt v idem ; et puis,
puisque halt n’est pas calculable, on a conclut que idem qui est encore plus dure ne peut pas
l’être.

Jean-Yves Moyen & Luc Pellissier 9

Institut Galilée L3 S6 – Année 2014–2015
TD : 16 février 2015
(TD 04 : Calculabilité.)

TD : 2 mars 2015 ×2
(révision, “partiel blanc”)

Partiel : 16 mars 2015

Partiel !

Cours : 27 mars 2015

Définition 1. Soit A un ensemble de programmes.
On dit que A est non-trivial si A n’est pas vide et que A ne contient pas tous les programmes
(A n’est pas vide).
On dit que A est extensionnel si il ne sépare pas deux programmes calculant la même fonction :
Si JPK = JQK alors soit P et Q sont tous les deux dans A, soit aucun des deux n’est dans A.
Théorème 2 (Théorème de Rice). Soit A un ensemble de programmes non-trivial et extension-
nel. A n’est pas calculable.

Théorème de Rice
L’extensionnalité peut aussi s’exprimer en disant qu’un programme de A et un programme
de A ne peuvent pas calculer la même fonction : P ∈ A et Q ∈ / A ⇒ JPK 6= JQK.
Si on a une propriété (un prédicat) sur les programmes, elle définie automatiquement un
ensemble de programmes (l’ensemble des programmes qui vérifient la propriété). On peut ainsi
parler de propriétés non-triviales (ou extensionnelles) si l’ensemble de programmes correspondant
est non-trivial (ou extensionnel).
Démonstration.
On fait la preuve par réduction à la Halte.
Soit loop un programme qui ne termine jamais :
read X; while true do{X:=X}; write X
Sans perte de généralité, on peut supposer que loop ∈ A (sinon, on inverse A et A dans la
preuve).
Comme A est non-trivial, A n’est pas vide. Soit P ≡ read XP ; CP ; write YP un programme
quelconque de A. Comme A est extensionnel, on a nécessairement JloopK 6= JPK.
Soit Q ≡ read XQ ; CQ ; write YQ un autre programme et d un arbre. On construit le programme
PQ suivant :

read XP ;
XQ :=d ;
CQ ;
CP ;
write YP

Comment se comporte PQ ? Ça dépend de JQKd.

– Si JQK(d)↑ alors PQ ↑ sur toutes ses entrées (car l’exécution de CQ ne termine jamais). Donc
JPQ K = JloopK et, par extensionnalité de A, PQ ∈ A.

Jean-Yves Moyen & Luc Pellissier 10

Institut Galilée L3 S6 – Année 2014–2015
– Si JQK(d)↓ alors PQ calcule la même chose que P (car l’exécution de CQ termine toujours et
le résultat est donc celui de CP ). Donc JPQ K = JPK et, par extensionnalité de A, PQ ∈
/ A.
On a donc PQ ∈ A ⇔ JQK(d) ↑.
Supposons maintenant que A soit décidable. Autrement dit, il existe un programme RA ca-
pable de décider l’appartenance à A (JRA K(pSq) = true ⇔ S ∈ A). En testant l’appartenance à
A de PQ , on pourrait en déduire la terminaison (ou non) de Q sur l’entrée d.
Comme on ne peut pas décider si Q termine sur l’entrée d (théorème de la Halte), on en déduit
que A n’est pas décidable.

Remarque : la preuve est une réduction assez classique. On doit construire un programme PQ
pour lequel la réponse à la question posée (l’appartenance à A) équivaut à la terminaison d’un
autre programme (Q). Pour ça, on utilise l’extensionnalité de A pour assimiler l’appartenance à
A avec le fait de calculer la même fonction qu’un programme préalablement choisi (loop et P
agissent comme de  représentants  de A et de A). L’astuce consiste à ne pas prendre deux
représentants au hasard pour lesquels on ne pourrait pas construire un programme ayant la
même sémantique aisément. En choisissant loop, on choisit en fait un représentant qu’il est
facile  d’imiter  dans le cas où Q ne termine pas.
Exemples : la plupart des exemples de non-calculabilité vus jusqu’à présent sont prouvables
à l’aide du théorème de Rice.
– Soit A37→5 l’ensemble des programmes qui, sur l’entrée 3, renvoient 5 : A37→5 = {P/JPK(3) =
5}.
– A37→5 est non trivial. En effet, le programme qui renvoie toujours 5 est dedans (donc
A37→5 est non vide) ; et le programme qui renvoie toujours 4 n’est pas dedans (donc
A37→5 est non vide).
– A37→5 est extensionnel. En effet, si P ∈ A37→5 et Q ∈ / A37→5 alors JPK(3) = 5 6= JQK(3) et
donc JPK 6= JQK.
Donc, d’après le théorème de Rice, A37→5 n’est pas calculable.
– Soit P un programme et idemP la propriété  calcule la même chose que P  : idemP (Q) ⇔
JPK = JQK et A l’ensemble des programmes qui vérifient cette propriété : A = {Q / idemP (Q)}.
– idemP est non triviale. En effet, on a idemP (P) (donc A n’est pas vide) ; et (i) si P ne
termine jamais n’importe quel programme qui termine n’est pas dans A ou (ii) sinon, le
programme qui fait comme P mais ajoute 1 à son résultat (YP :=cons nil YP juste avant
le write) calcule autre chose que P et n’est pas dans A (donc A n’est pas vide).
– idemP est extensionnelle. En effet, soit Q1 et Q2 deux programmes tels que JQ1 K = JQ2 K. Si
Q1 ∈ A alors on a idemP (Q1 ), ce qui est équivalent à JPK = JQ1 K mais comme JQ1 K = JQ2 K,
on a alors JPK = JQ1 K = JQ2 K donc Q2 ∈ A.
idemP étant extensionnelle et non-triviale n’est donc pas décidable.

Castor affairé (fonction de Radó)

Même si beaucoup de propriétés rentrent dans le cadre du théorème de Rice, il n’est pas
toujours suffisant pour prouver qu’une fonction n’est pas calculable.
Un Castor est un programme qui, sur l’entrée 0, termine et renvoie un entier, n, appelé la
longueur du barrage (qu’il construit). Un programme a une taille notée |P|, qui est simplement
la taille du programme (nombre de symboles, c’est-à-dire longueur de la chaı̂ne de caractères qui
contient le code du programme).
D’un naturel compétitif, les castors cherchent à construire le plus grand barrage possible. Un
castor affairé est un castor qui construit le plus long barrage possible parmi tous les castors de
même taille.
La fonction du castor affairé (en anglais, Busy Beaver ) est la fonction qui à m associe la
longueur du barrage construit par le castor affairé de taille m 1 :

BB(m) = max{n/∃P, |P| ≤ m et JPK(0) = n}

1. Historiquement, cette fonction est définie sur les machines de Turing et noté Σ. Comme les machines de
Turing peuvent être très compactes (un état peut correspondre à plusieurs lignes de code), l’écart entre Σ et BB
est important, d’où la notation différente.

Jean-Yves Moyen & Luc Pellissier 11

Institut Galilée L3 S6 – Année 2014–2015
Bien évidemment, le problème avec les castors est qu’il est impossible de décider si un pro-
gramme est un castor (c’est à peu près équivalent à décider si il termine sur l’entrée 0).
Théorème 3 (Castor affairé). BB n’est pas calculable.
Le théorème de Rice n’est pas suffisant pour conclure. En effet, l’ensemble des castors est
non-trivial et extensionnel (c’est l’ensemble des programmes qui sur l’entrée 0 renvoient le codage
d’un entier). Donc indécidable, d’après le théorème de Rice. Mais le fait que l’ensemble des castors
est indécidable n’est pas suffisant pour conclure (on pourrait avoir un moyen détourné de calculer
BB sans avoir besoin de décider si un programme donné est un castor ou non)
Démonstration. On va faire la preuve par l’absurde (ressemblant à une diagonalisation). L’idée
de la preuve est de trouver un entier K et un programme Q tels que :
– Q soit de taille inférieure ou égale à K.
– JQK(0) > BB(K).
Q est alors un castor de taille inférieure à K qui construit un barrage de longueur supérieure
à BB(K). Ceci est bien évidemment absurde puisque par définition BB(K) est la longueur du
plus grand barrage constructible par un castor de taille K ou moins.
Supposons que BB soit calculable par PBB ≡ read XBB ; CBB ; write YBB . Ce programme
a une taille , |PBB | = q ≥ 14 (il faut 14 symboles pour écrire “read”, “write”, les espaces et
point-virgules minimums). On peut alors faire un premier essai avec le programme Q0 suivant :

read X ;
XBB :=K ;
CBB ;
Y:=cons nil YBB ;
write Y

·
P0 calcule précisément , soit BB(K) + 1. Quelle est sa taille ? Laissons
nil JPBB K(K)
dans un premier temps la taille nécessaire pour représenter K. La taille de P0 est alors q 0 ≤ q + 50
(selon la manière dont on compte, mais 50 est une marge large).
Si on choisit K = 5 × q, on a alors K = q + 4 × q ≥ q + 4 × 14 = q + 56. Autrement dit, on a
q 0 ≤ q + 50 ≤ q + 56 ≤ K et on a bien avec Q0 un castor de taille ≤ K qui construit un barrage
de longueur K + 1 > BB(K), ce qui contredit le fait que BB(K) est la longueur du plus grand
barrage construit par un castor de taille < K.
Mais il reste un problème avec ce premier essai : on n’a pas pris en compte la taille nécessaire
pour représenter K dans l’affectation du début de Q0 . Si on prend la représentation évidente

K = cons nil (cons nil (. . . (cons nil nil ) . . .))

| {z } | {z }
K fois K fois

On a alors besoin pour écrire K de 11K + 5 symboles. Mais du coup, la vraie taille de Q0 est
q 0 = q + 11K + 55 et quelque que soit la valeur de K, on n’arrivera pas à avoir q 0 < K ce qui
casse toute la preuve. . .
L’astuce consiste à écrire dans le programme une valeur qui prend moins de place que K,
par exemple avec K 0 = K/16, K/16 aura une taille d’environ 11K/16 + 5 ≤ K, puis de faire
une boucle pour multiplier cette valeur par 16 (ou plus précisément ici, 4 boucles qui multiplient
chacune par 2). On a alors le programme Q1 suivant :

Jean-Yves Moyen & Luc Pellissier 12

Institut Galilée L3 S6 – Année 2014–2015
read X ;
X1 :=K 0 ;
X2 :=nil ;
while X1 do{X1 :=tl X1 ;X2 :=cons nil (cons nil X2 )}
X4 :=nil ;
while X2 do{X2 :=tl X2 ;X4 :=cons nil (cons nil X4 )}
X8 :=nil ;
while X4 do{X4 :=tl X4 ;X8 :=cons nil (cons nil X8 )}
X16 :=nil ;
while X8 do{X8 :=tl X8 ;X16 :=cons nil (cons nil X16 )}
XBB :=X16 ;
CBB ;
Y:=cons nil YBB ;
write Y

Chaque boucle double la variable de contrôle, on a donc bien X1 = K 0 , X2 = 2X1 = 2K 0 ,

X4 = 2X2 = 4K 0 , X8 = 2X4 = 8K 0 et X16 = 2X8 = 16K 0 = K. Donc le programme calcule toujours
BB(K) + 1.
En ce qui concerne sa taille, elle vaut q 00 ≤ q + (11K/16 + 5) + 295 ≤ q + 11K/16 + 300. Par
rapport à Q0 , le facteur constant a augmenté (de 50 à 300) mais le facteur variable a diminué
(de K à 11K/16). Si on choisit K = 74q, on a alors q 00 ≤ q + 16 11
× 74q + 300 ≤ 52q + 300 ≤
00
52q + 22 × 14 ≤ 52q + 22q = 74q = K. On a bien |Q1 | = q ≤ K.
Donc Q1 est un castor de taille ≤ K mais il construit un barrage de longueur BB(K) + 1, ce
qui est absurde par définition de BB. L’hypothèse qu’on a faite était de supposer BB calculable.
Donc BB n’est pas calculable.
Remarque : La preuve ne tourne pas en rond, contrairement aux apparences. . . En fait, Q0 est
complètement inutile à la preuve et aurait pu être supprimé, il ne sert qu’à justifier le calcul de K
à partir de K 0 et le “nombre magique” de 74q. Autrement dit, si PBB existe, il a nécessairement
une taille q. On peut donc choisir  arbitrairement  K = 74q puis construire Q1 et exhiber la
contradiction directement.
Remarque : Définie sur les machines de Turing, Σ (l’équivalent de BB) indique la taille du
barrage (le nombre de symboles qu’on peut écrire sur le ruban avant de s’arrêter) en fonction
du nombre d’états de la machine. Σ commence à avoir des valeurs intéressantes à partir de Σ(2)
(alors qu’il faut attendre BB(14) pour que les choses aient un sens). Σ croı̂t tellement vite que
les seules valeurs sont connues pour . . . Σ(2) = 4, Σ(3) = 6 et Σ(4) = 13. Ensuite, les choses
s’emballent et on n’a plus que des bornes inférieures : Σ(5) ≥ 4000 et Σ(6) ≥ 3, 5 × 1018267 . . . Une
croissance très très très rapide. BB suit la croissance de Σ mais avec un peu de décalage.

Cours : 3 avril 2015

Thèse de Church-Turing
Énoncé
La notion de calculabilité qu’on a définie est étroitement liée au langage While. On peut
légitimement se demander si l’utilisation d’un langage moins restreint ne permettrait pas de
calculer plus de fonctions. En particulier, est-ce que des constructions comme l’héritage de classes,
l’ordre supérieur, les exceptions, . . . qui donnent beaucoup de pouvoir expressif aux langages
 modernes  permettent de calculer plus de choses ?

Malheureusement, non. La thèse de Church-Turing stipule que quelque soit le langage de

programmation choisi, les fonctions calculables sont les mêmes. Autrement dit, on peut calculer
exactement les mêmes fonctions en While, en Ocaml, en C, en Java, en λ-calcul, . . .
Il s’agit d’une  thèse  et non d’un théorème parce que on ne peut pas considérer facilement
tous les langages qui pourraient un jour être inventés. Mais de nombreux langages (plusieurs

Jean-Yves Moyen & Luc Pellissier 13

Institut Galilée L3 S6 – Année 2014–2015
centaines de langages  sérieux ) existent et calculent les mêmes fonctions, ce qui donne un
poids très fort à cette thèse (certains langages calculent moins de fonctions, mais aucun n’en
calcule plus).
La thèse de Church-Turing a des conséquences tant sur le plan pratique que sur le plan
théorique.

Conséquences
Sur le plan pratique, premièrement, on sait que tout ce qui est indécidable pour While l’est
aussi, par exemple, pour C. Ainsi, l’arrêt des programmes C est indécidable (parce qu’on peut
simuler un machine de Turing ou un programme While en C). On peut rêver d’un compilateur
évolué qui indiquerait au moment de la compilation si telle ou telle fonction termine, afin d’éviter
d’exécuter des programmes mal conçus qui bouclent par erreur. C’est tout simplement impossible,
non pas parce qu’on est  trop mauvais  pour écrire un tel compilateur mais parce que la
calculabilité nous dit qu’on ne peut pas y arriver.
Deuxièmement, il est inutile d’espérer sortir d’un  trou  de calculabilité en changeant de
langage. Si une fonction n’est pas calculable en C, ce n’est pas en passant à Java et en rajoutant
des objets et des classes qu’on va réussir à la calculer. Il faut abandonner tout espoir de la
calculer et essayer de contourner le problème. En sens inverse, pour prouver qu’une fonction
n’est pas calculable, on peut le faire dans un langage  simple  (comme While ou les machines
de Turing) sans avoir besoin de considérer toutes les constructions qui existent dans tous les
langages.
Finalement, le choix d’un langage de programmation n’a pas à être dicté par ce qu’il peut
calculer puisque tous calculent les mêmes fonctions. Savoir si on va coder en C, Java ou Ocaml
ne dépend pas de  dans quel langage on peut le faire . Si on peut le coder dans un langage,
alors on peut le coder dans les autres. Le choix du langage peut dépendre de l’habitude du
programmeur avec tel ou tel langage, de l’habitude du groupe de programmeurs (dans un gros
projet existant, il vaut mieux ne pas mélanger les langages), de la destination du résultat (pour
une application web, il vaut mieux utiliser un langage conçu pour) et un peu de la nature du
problème (certains problèmes s’expriment très bien avec un récurrence et un langage qui facilite
la récurrence donnera un programme plus simple).
Au point de vu théorique, la conséquence la plus importante est l’universalité de la notion de
calculabilité. Puisque tous les langages définissent les mêmes fonctions calculables, la notion de
 fonctions calculable  est en fait un objet mathématique bien défini et  absolu . L’ensemble

des fonctions calculables a ainsi une existence mathématique à un niveau similaire à celui de
l’ensemble des entiers.
Ensuite, la morale de l’histoire, c’est que pour atteindre l’intégralité de toute la calculabi-
lité, on n’a pas besoin de grand chose. Le langage While est extrêmement pauvre (seulement
6 expressions et 3 commandes) mais suffit à tout calculer. Quand on conçoit des langages de
programmation, on a immédiatement l’ensemble des fonctions calculables (presque  gratuite-
ment ) et la majorité des constructions sont uniquement là pour le confort du programmeur.

Équivalences
On va illustrer la thèse de Church-Turing en montrant que divers langages avec d’autres
constructions sont équivalents à While. On note J•KW la sémantique de While pour la différencier
des autres sémantiques qu’on va définir.
Pour ça, on doit construire pour chaque langage L :
– une grammaire et une sémantique J•KL ;
– une traduction vers While hPiLW ;
– une traduction depuis While hQiW L ;
et prouver que les traductions préservent la sémantique :
– JhPiLW KW = JPKL ;
– JhQiW L KL = JQKW .
Remarque : on n’a pas besoin que les traductions soient réciproquent (on peut avoir hhPiLW iW L 6=
P), il suffit que la sémantique soit préservée.
Remarque : Attention aux indices ! Ils sont prévus pour bien s’enchaı̂ner, voir les exemples.

Jean-Yves Moyen & Luc Pellissier 14

Institut Galilée L3 S6 – Année 2014–2015
Avec de telles traductions, toute fonction calculable dans L est immédiatement calculable en
While : la fonction f est calculée dans L par un programme P avec JPKL = f , elle est donc
calculé en While par Q = hPiLW . De même, toute fonction calculable en While est calculable
dans L. Les deux langages calculent donc exactement les mêmes fonctions.

Le Langage Goto
Présentation informelle
Le langage Goto utilise les mêmes données et expressions que While. Au niveau des com-
mandes, Goto n’a pas de boucle mais un saut conditionnel. Un programme Goto est un en-
semble de labels avec une instruction associée à chaque label. Normalement, on exécute les
instructions dans l’ordre des labels, mais la commande de saut (goto) peut forcer à sauter à
n’importe quel label.
Au niveau des traductions, une boucle peut être simulée avec des sauts (c’est typiquement
ce qui se passe en assembleur). À l’inverse, on stockera une variable compteur de programme
(ou  pointeur d’instruction , ou  compteur ordinal , en anglais  instruction pointer  ou
 program counter ) qu’on teste pour savoir quelle ligne exécuter.

Par exemple, voici un programme While qui renverse une liste :

read X ;
Y:=nil ;
while X do{Y:=cons (hd X) Y;X:=tl X}
write Y

Voici comment on peut le traduire en Goto. Remarque : la numérotation exacte des sauts
qui simulent la boucle ne peut être faite qu’une fois l’ensemble de la boucle écrite.

read X ;
1 :Y:=nil ;
2 :if X then goto 3 else goto 6 ;
3 :Y:=cons (hd X) Y ;
4 :X:=tl X ;
5 :if X then goto 2 else goto 2 ;
write Y

Remarque : le saut de la ligne 5 est particulièrement mal pensé. Une traduction plus intelli-
gente mettrait ici le test de la boucle avec un saut en 3 ou 6 selon la valeur de X. Mais ça n’a
aucune importance ici.
À son tour, ce programme peut être retranscrit en While comme suit.

read X ;
IP:=1 ;
if =? IP 1 then Y:=nil ;
if =? IP 2 then {if X then IP:=3 else IP:=6} ;
if =? IP 3 then Y:=cons (hd X) Y ;
if =? IP 4 then X:=tl X ;
if =? IP 5 then {if X then IP:=2 else IP:=2} ;
write Y

Jean-Yves Moyen & Luc Pellissier 15

Institut Galilée L3 S6 – Année 2014–2015
Données et expressions
Les données et les expressions de Goto sont les mêmes que celles de While. En particulier
la sémantique est aussi la même et on notera donc uniformément EJEKσ sans différencier EJEKW σ
et EJEKG σ.

Syntaxe
On utilise la grammaire suivante pour les commandes et programmes de Goto :

N 3 l, l0

Instructions 3 I ::= X:=E

| if E then goto l else goto l0

Programmes 3 P ::=read X ; {l : Il } write Y

Autrement dit, un programme est un ensemble d’instructions numérotées (par des labels).

Sémantique
La sémantique des commandes de While transformait une mémoire en une nouvelle mémoire.
Pour les instructions de Goto, il faut non seulement conserver la mémoire mais aussi le label
courant. On a donc une sémantique de type :

J•KG : P (N × Instructions) → ((Mémoires × N) → (Mémoires × N))

où P (N × Instructions) dénote les ensembles d’instructions numérotées (des couples (entier,
instruction)).
On note I = {1 : I1 , . . . , n : In } et la(sémantique est définie par :
X 7→ EJEKσ
– Si Il = X:=E alors on définit σ 0 =
Y 7→ σ(Y) si Y 6= X
Et on a JIKG (σ, l) = JIKG (σ 0 , l + 1).
– Si Il = if E then goto l0 else goto l00 alors
(
JIKG (σ, l00 ) si EJEKσ = nil
JIKG (σ, l) =
JIKG (σ, l0 ) sinon

– Finalement, si Il n’existe pas (si l > n, autrement dit si on a atteint la fin du programme)
alors
JIKG (σ, l) = (σ, l)
En ce qui concerne les programmes, la sémantique est similaire à celle de While, il s’agit
d’une fonction
J•KG : Programmes → (D → D⊥ )
associant à un programme P = read X; I; write Y une fonction partielle des entrées vers les
sorties définie par

JPKG (d) = e si JIKG (σdX , 1) = (σ, l) et σ(Y) = e

où σdX est la mémoire initiale de P, qui associe d à X et nil à toutes les autres variables.

Jean-Yves Moyen & Luc Pellissier 16

Institut Galilée L3 S6 – Année 2014–2015
Traduction
La traduction de While vers Goto a besoin de connaı̂tre le numéro du premier label libre
(pas encore utilisé).
hX:=E, liW G ={l : X:=E}, l + 1
hC1 ;C2 , liW G =E 0 ∪ E 00 , l00 avec E 0 , l0 = hC1 , liW G et E 00 , l00 = hC2 , l0 iW G
hwhile E do{C}, liW G =E 0 ∪ {l : if E then goto l + 1 else goto l0 ,
l0 − 1 : if E then goto l else goto l}, l0
avec E 0 , l0 − 1 = hC, l + 1iW G
Et pour les programmes, on a :
hread X; C; write YiW G = read X; hC, 1iW G ; write Y

Cours : 13 avril 2015

Goto
While calcule moins que Goto
Théorème 4. Toute fonction calculable en While est aussi calculable en Goto.
Démonstration. Pour ça, il suffit de montrer que JQKW = JhQiW G KG . En effet, une fonction f est
calculable en While si elle est calculée par un programme Q, c’est-à-dire si f = JQKW mais on a
alors le programme (en Goto) P = hQiW G qui calcule la même fonction, donc f est calculable
en Goto.
Soit Q = read X; C; write Y et P = hQiW G = read X; I; write Y avec I = hC, 1iW G =
{1 : I1 , . . . , n : In }.
D’après la sémantique des programmes, on a (π1 est la première projection) :
JQKW (d) = (JCKW (σdX ))(Y) et JPKG (d) = (π1 (JIKG (σdX , 1)))(Y)
Il faut donc prouver l’égalité de sémantique sur les commandes. Pour que la récurrence marche, on
va devoir généraliser le label (et ne pas garder systématiquement 1). Remarque : il ne s’agit pas à
proprement parler de récurrence (sur les entiers) ou d’induction structurelle (sur les programmes)
puisqu’un programme peut ne pas terminer. . . Il faudrait plutôt faire une preuve par bissimulation
pour être plus correct. En pratique, ça marche. . .
Hypothèse d’induction :
∀C, ∀l, ∀σ, JIKG (σ, l) = (JCKW (σ), l0 ) avec I, l0 = hC, liW G
On note I = {l : Il , . . . , n : In }.
– Si C ≡ X:=E.
On a alors JCKW (σ) = σ’ pour une certaine mémoire σ’.
D’autre part I = {l : X:=E}. On a donc JIKG (σ, l) = JIKG (σ 00 , l + 1) = (σ 00 , l + 1) pour une
certaine mémoire σ”. En comparant les règles, on s’aperçoit immédiatement que σ’ = σ”
– Si C ≡ C1 ;C2 .
On a alors JCKW (σ) = σ” = JC2 KW (σ 0 ) avec σ’ = JC1 KW (σ).
D’autre part, on a E 0 , l0 = hC1 , liW G et E 00 , l00 = hC2 , l0 iW G et I = E 0 ∪ E 00 .
Par hypothèse d’induction, JE 0 KG (σ, l) = (JC1 KW (σ), l’) = (σ’, l’). Donc JIKG (σ, l) =
JIKG (σ 0 , l0 ).
Par hypothèse d’induction, JE 00 KG (σ 0 , l0 ) = (JC2 KW (σ 0 ), l”) = (σ”, l”). Donc JIKG (σ 0 , l0 ) =
JIKG (σ 00 , l00 ) = (σ”,l”).
En regroupant, on a bien JIKG (σ, l) = JIKG (σ 0 , l0 ) = JIKG (σ 00 , l00 ) = (σ”,l”) = (JCKW (σ),
l”).
– Si C = while E do{D} et EJEKσ = nil.
On a alors JCKW (σ) = σ. D’autre part Il ≡ if E then goto l + 1 else goto l0 .
Puisque EJEKσ = nil, on a JIKG (σ, l) = JIKG (σ, l0 ) = (σ, l’) = (JCKW (σ), l’).

Jean-Yves Moyen & Luc Pellissier 17

Institut Galilée L3 S6 – Année 2014–2015
– Si C = while E do{D} et EJEKσ 6= nil.
On a alors 2 JCKW (σ) = JCKW (JDKW (σ)) = JCKW (σ 0 ) avec σ’ = JDKW (σ).
D’autre part Il ≡ if E then goto l + 1 else goto l0 . Puisque EJEKσ 6= nil, on a JIKG (σ, l)
= JIKG (σ, l + 1).
Soit E 0 , l0 − 1 = hD, l + 1iW G . On a JE 0 KG (σ, l + 1) = (σ’,l’-1) par hypothèse d’induction.
Mais du coup, on a JIKG (σ, l) = JIKG (σ, l + 1) = JIKG (σ 0 , l0 − 1) = JIKG (σ 0 , l) = JCKW (σ 0 )
= JCKW (σ).

Goto calcule moins que While

La traduction de Goto vers While présentée ici n’est pas tout à fait la même de celle de
l’exemple précédent. Elle est un peu moins efficace mais la preuve en sera facilitée.
On traduit chaque instruction séparément :

hl : X:=EiGW =if =? IP l then {X:=E;IP:=0;IP0 :=l + 1}

hl : if E then goto l else goto l00 iGW =if =? IP l then {if E then IP0 :=l0 else IP0 :=l00 ;IP:=0}
0

Soit P ≡ read X; I; write Y avec I = {1 : I1 , . . . , n : In }. On définit Q = hPiGW comme le

programme suivant :
read X ;
IP:=1
while not =? IP n + 1 do
{
h1 : I1 iGW ;
h2 : I2 iGW ;
...
hn : In iGW ;
IP:=IP0 ;
}
write Y
Théorème 5. Toute fonction calculable en Goto est aussi calculable en While.
La preuve est faite en TD.

CM
Description
Les machines à compteurs (CM) utilisent les même commandes que Goto mais avec des
expressions différentes. Les données de CM sont les entiers (N) au lieu des arbres binaires. Les
expressions sont :

ExpressionsC 3 E, F ::= n| X
| E + F| E − F
| E ∗ F| E/F
| n ↑ E| log0b E
| =? E F

La sémantique des expressions est la sémantique (presque) évidente. La difficulté réside uni-
quement pour la soustraction et la multiplication. Comme on veut que le résultat soit dans N, on
2. Attention ! Il faut bien utiliser la version de la sémantique indiquée ici. Si on utilise JCKW (σ) = JD;CKW (σ),
on va se retrouver avec une commande différente, donc une traduction en Goto différente et on ne pourra pas
faire fonctionner l’hypothèse d’induction.

Jean-Yves Moyen & Luc Pellissier 18

Institut Galilée L3 S6 – Année 2014–2015
renverra 0 ou on arrondira à l’entier inférieur au besoin. Le logarithme est aussi un peu bizarre
pour faire fonctionner la traduction (d’où la notation log0 et non log).

EJnKC σ =n
EJXKC σ =σ(X)
EJE + FKC σ =EJEKC σ + EJFKC σ
EJE ∗ FKC σ =EJEKC σ × EJFKC σ
EJE/FKC σ =bEJEKC σ/EJFKC σc
EJE − FKC σ = max(0, EJEKC σ − EJFKC σ)
EJn ↑ EKC σ =n(EJEKC σ)
(
0 0 si EJEKC = 0
EJlogb EKC σ =
sinon, le plus grand entier k tel qu’il existe un entier m avec k b · m = EJEKC σ
EJ=? E FKC σ =1 si EJEKC σ = EJFKC σ et 0 sinon.

Remarque : pour les  puissances pures  (2k , . . . ) le log0 correspond au logarithme, c’est-à-
dire log02 2k = k (avec m = 1). Pour les autres nombres, ça correspond à la puissance de la base
b dans la décomposition en facteurs premiers de n (si b est premier, ce qui sera toujours le cas
pour nous).
La sémantique des instructions est adaptée au type de données, ce qui change uniquement
pour le test qui est fait à 0 et non plus à nil.

Traduction
On fait uniquement la traduction de Goto vers CM et on a besoin de traduire uniquement
les données (arbres binaires) et les expressions. Toute l’astuce réside dans le codage des arbres
binaires.

hniliGC =0
·
* +
=1 + 2hdiGC × 3heiGC
d e GC

hXiGC =X
hcons E FiGC =1 + (2 ↑ hEiGC ) ∗ (3 ↑ hFiGC )
hhd EiGC σ = log02 hEiGC
htl EiGC σ = log03 hEiGC
h=? E FiGW ==? hEiGW hFiGW

TD : 13 avril 2015
(TD 06 : Thèse de Church-Turing.)

Cours : 17 avril 2015

VCM
VCM (Machines à Compteurs restreintes aux Variables) est une restriction de CM où les
expressions ne sont pas récursives et sont forcément formées à partir de variables. Les expressions

Jean-Yves Moyen & Luc Pellissier 19

Institut Galilée L3 S6 – Année 2014–2015
sont donc définies par la grammaire
ExpressionsV 3 E, F ::= n| X
| X + Y| X − Y
| X ∗ Y| X/Y
| n ↑ X| log0b X
| =? X Y
La sémantique est la même que CM.
La traduction de CM vers VCM, h•iCV , se fera en  cassant  les expressions récursives
en petits bouts. Il faut faire attention car cela va créer beaucoup de nouvelles variables et de
nouveaux labels dans le programme.

SCM
SCM (Machines à Compteurs Successeur) est une restriction de VCM où les seules opérations
permises sont +1 et −1. Les expressions sont donc définies par la grammaire
ExpressionsS 3 E, F ::=X| X + 1| X − 1

La sémantique est la même que VCM et CM.

La traduction de VCM vers SCM, h•iV S se fera en montrant comment simuler les opérations
complexes à l’aide de +1, −1 et boucles (sauts conditionnels).

Cours : 4 mai 2015 ×2

Rappels : Automates
Voir le cours d’Automates et Théorie des Langages pour les détails.
Un automate comporte un alphabet Σ, un ensemble d’états Q, un état initial q0 , un (ou
plusieurs) état final (ou état d’acceptation) qf et une fonction de transition δ : Q × Σ → Q. Il est
souvent représenté de manière compacte sous forme d’un graphe orienté où chaque nœud est un
état et où une transition δ(q, x) = q 0 est représentée par une flèche de q vers q 0 étiquetée par x.
Quand on fournit un mot (de Σ∗ ) à un automate, il lit les lettres une à une et change d’état
selon sa fonction de transition. En pratique, on peut sur le graphe suivre les flèches étiquetées
par les lettres lues.
Si, une fois arrivé à la fin du mot, on est dans l’état final, le mot est accepté. Sinon, il est
rejeté. L’ensemble des mots acceptés par un automate est appelé le langage reconnu par cet
automate.
Exemple, automate qui reconnaı̂t les multiples de 4 écrits en binaire, c’est-à-dire les mots sur
{0, 1}∗ qui finissent par 00. On a besoin de 3 états, un si le préfixe lu jusqu’à présent est impair
(le dernier chiffre lu est un 1), un si il est pair (on a lu un 0 mais pas deux) et un si il est multiple
de 4 (on a lu au moins deux 0).

1 0
1

q1 0 q2 0 q4
start

On sait que les automates ne peuvent pas tout décider et qu’on peut faire mieux avec des
programmes. Par exemple, il n’existe pas d’automate qui reconnaisse le langage an bn alors qu’il
est très facile d’écrire un programme (par exemple en C) qui le fait.
Let automates ont principalement 3 restrictions par rapport aux programmes :

Jean-Yves Moyen & Luc Pellissier 20

Institut Galilée L3 S6 – Année 2014–2015
1. Ils ne peuvent répondre que “oui” ou “non”, c’est à dire qu’ils peuvent décider quelque
chose mais qu’ils ne peuvent pas calculer.
2. Ils sont obligés de parcourir le mot de gauche à droite (du début à la fin). Il est impossible
de revenir en arrière pour aller relire une partie du mot.
3. Ils n’ont pas de mémoire. À l’exception du mot initial, qui n’est jamais modifié, il n’y a pas
de données pour un automate. Ainsi, on ne peut pas stocker une valeur en mémoire et la
réutiliser plus tard (par exemple, le n pour reconnaı̂tre an bn ).

Rappels : Automates à pile

Voir le cours d’Automates et Théorie des Langages pour les détails.
Pour se débarrasser de la troisième restriction des automates, on peut rajouter une mémoire
annexe. Par exemple, une pile. La fonction de transition doit alors produire, outre le nouvel état,
une action à effectuer sur la pile (push, pop, ou rien). On a alors δ : Q × Σ → Q × {push, pop, ∅}.
Sur la représentation graphique, les flèches seront étiquetées à la fois par la lettre lue et par
l’action de pile. On les séparera par une barre pour bien indiquer ce qui est une entrée de la
transition (à gauche de la barre) de ce qui est une sortie (à droite).
Remarque : on peut avoir besoin de faire des tests plus évolués avec la pile (par exemple,
tester quel est la lettre au sommet de la pile) mais ce n’est pas nécessaire dans ce rappel. . .
Exemple : automate à pile qui reconnaı̂t an bn . On a un premier état qui lit les a et les stocke
sur la pile (ce qui revient à les compter à l’aide de la hauteur de la pile) et un deuxième qui lit
les b en enlevant un a de la pile à chaque fois. Si la pile est vide à la fin, tout va bien.

a/push b/pop

b/pop fin du mot et pile vide

start qa qb qf

a/∅

poubelle

a, b/∅

Quand on simule l’exécution d’un automate à pile, on a besoin de conserver à chaque étape
le contenu de la pile.

Machines de Turing
Définition
Les machines de Turing se débarrassent des deux premières restrictions des automates. Elles
ont été introduites par Alan Turing pour modéliser le calcul que pourrait faire un être humain :
on a une feuille de papier sur laquelle est écrite un calcul à effectuer (c’est-à-dire une suite de
formules). À chaque étape, on recopie la ligne précédente en faisant éventuellement quelques
changements locaux.
Le principal changement par rapport aux automates est d’autoriser les aller-retours dans le
mot lu. La fonction de transition aura donc besoin d’avoir en résultat un mouvement (gauche,
droite ou rester sur place). Comme on peut à tout moment retourner à n’importe quelle position
dans le mot, on peut l’utiliser comme mémoire et on n’a pas besoin de mémoire annexe (la pile).
Au lieu de push ou pop, on va directement écrire dans le mot, c’est-à-dire que la fonction de
transition aura en sortie une lettre à écrire.

Jean-Yves Moyen & Luc Pellissier 21

Institut Galilée L3 S6 – Année 2014–2015
Avec ce système, on peut parfois “sortir” du mot, c’est-à-dire aller à droite alors qu’on est
déjà en train de lire la dernière lettre (ou à gauche quand on lit la première). Interdire un tel
comportement reviendrait à limiter la mémoire à la taille du mot initial, ce qui est beaucoup trop
restrictif (notamment par rapport aux automates à pile ou la hauteur de la pile n’est pas bornée
à priori et peut devenir aussi grande que nécessaire). Du coup, on considère que à droite et à
gauche du mot, il y a autant de symboles “blanc” que nécessaire. On note les blancs # quand
c’est nécessaire. On dit souvent que le mot est écrit sur un ruban bi-infini (ruban : on peut aller
à gauche ou à droite mais pas en haut ou en bas, bi-infini : on peut aller aussi loin qu’on veut
dans ces directions).
Pour retenir la lettre qu’on est en train de lire (et sur laquelle on peut écrire) dans le ruban, on
considère qu’il y a une tête de lecture qui pointe dessus. C’est similaire aux bandes magnétiques
(cassettes audios ou vidéos du 20ème siècle) où les données sont écrites sur un ruban et l’appareil
de lecture dispose d’une tête de lecture capable de lire un endroit précis du ruban (et un seul
endroit à la fois) et de se déplacer ensuite dans un sens ou dans l’autre (plus précisément, en
enroulant ou en déroulant la bande, on change l’endroit du ruban lu par la tête).
Formellement, une machine de Turing est donc définie par un alphabet Σ qui doit contenir
le symbole blanc ’#’ et au moins un autre symbole, un ensemble d’états Q, un état initial q0 ,
un état acceptant (ou final) qf et un fonction de transition δ : Q × Σ → Q × Σ × {←, ↓, →} (↓
indique “pas de mouvement” et est en pratique nécessaire surtout pour les machines à plusieurs
rubans).
Comme pour les automates à pile, on peut représenter une machine de Turing par un graphe
en indiquant sur chaque flèche à la fois la lettre lue, la lettre écrite et le mouvement de la tête de
lecture. On séparera l’entrée (lettre lue) des sorties (lettre écrite et mouvement) par une barre.
Exemple : machine qui ajoute 1 à un nombre écrit en binaire sur son ruban. On commence,
dans qdroite à aller tout à droite du mot (c’est-à-dire à dépasser la fin et tomber sur le # et revenir
en arrière), ensuite, on peut ajouter 1 au bit de poids faible et si besoin propager la retenue. Une
fois le calcul fini, on revient au début du mot.

0/0, → 0/0, ←
1/0, ←

#/#, ← 0/1, ←
start qdroite qplus qretour 1/1, ←

1/1, → #/#, →
#/1, ↓

qf

Exécution
Quand on exécute un automate, on peut se contenter de suivre les flèches dans le graphe.
Pour les machines de Turing, comme le mot lu (le ruban) est modifié très souvent, on a besoin
de garder à la fois l’état de l’automate et la composition du ruban, ainsi que la position de la
tête de lecture (la lettre lue).
On a donc une configuration qui est composée d’un état et d’un mot (le ruban) dont un
symbole est marqué (la position de la tête de lecture).
Pour passer d’une configuration à la suivante, on regarde l’état courant et la lettre lue et on
applique la fonction de transition. On écrit alors la nouvelle lettre, on change d’état et on déplace
la tête de lecture.
Si on est bloqué (il n’y a pas de transition pour la lettre lue et l’état courant), la machine
s’arrête.

Jean-Yves Moyen & Luc Pellissier 22

Institut Galilée L3 S6 – Année 2014–2015
Au début de l’exécution, la machine est dans une configuration initiale. L’état est l’état initial
et le ruban contient le mot donné en entrée sur la machine, tous les autres symboles sont blancs
(#). La tête de lecture est positionnée sur la première lettre du mot d’entrée.
De manière similaire aux automates, si une machine s’arrête dans un état d’acceptation (ou
état final), on dit qu’elle accepte le mot (qui était sur son ruban au début de l’exécution). L’en-
semble des mots acceptés par une machine de Turing est le langage reconnu par cette machine.
Contrairement aux automates, une machine de Turing peut produire un résultat qui n’est
pas simplement “oui” ou “non”. En effet, lorsque la machine s’arrête, le ruban comporte un
mot qui peut être considéré comme le résultat du calcul. Par convention, on demande que la
tête de lecture soit positionnée au moment de l’arrêt sur la première lettre du résultat. Cette
convention permet de facilement composer des machines de Turing puisqu’une deuxième machine
peut immédiatement commencer son calcul quand la première a terminé, la tête étant positionnée
au bon endroit.
C’est à cause de cette convention que la machine précédente a l’état qretour . Cette convention
permet d’exécuter des machines de Turing  à la chaı̂ne  pour pouvoir facilement composer les
fonctions calculées.
Exemple, exécution de la machine précédente sur l’entrée 1010011. On donne simplement la
liste des configurations, dans l’ordre (la lettre lue est soulignée). Chaque étape de calcul est ici
numérotée. Les # inutiles ne sont pas indiqués.

n◦ état ruban n◦ état ruban n◦ état ruban

0 qdroite 1010011 6 qdroite 1010011 12 qretour 1010100
1 qdroite 1010011 7 qdroite 1010011# 13 qretour 1010100
2 qdroite 1010011 8 qplus 1010011# 14 qretour 1010100
3 qdroite 1010011 9 qplus 1010010 15 qretour #1010100
4 qdroite 1010011 10 qplus 1010000 16 qf #1010100
5 qdroite 1010011 11 qretour 1010100

Remarque : il faut faire attention à indiquer très clairement quelle est la lettre lue pour éviter
toute confusion !

Décision, calcul
On peut maintenant définir la décidabilité et la calculabilité en terme de machines de Turing,
de manière très similaire à ce qui a été fait avec le langage While.
– une machine de Turing M semi-décide L si, pour tout mot w ∈ Σ∗ , l’exécution de M sur
w s’arrête sur un état final acceptant si, et seulement si w ∈ L ;
– une machine de Turing M décide L si M semi-décide L et pour tout mot w ∈ Σ∗ , l’exécution
de M sur w s’arrête (pas forcement sur un état final).
– une machine de Turing M calcule une fonction f : L → L⊥ si, pour tout mot w ∈ L,
– si f (w) ↓, alors l’exécution de M sur w s’arrête sur un état final, en laissant le seul mot
f (w) sur le ruban, la tête de lecture étant sur la premiere lettre (à gauche) de ce mot ;
– si f (w) ↑, alors l’exécution de M sur w ne s’arrête jamais sur un état final (boucle infinie
ou arrêt sur un état non final).

Calculabilité
En toute rigueur, pour des raisons historiques, la calculabilité est définie en terme de machines
de Turing. C’est-à-dire que si on dit qu’une fonction est calculable, sans plus de précision, on veut
en fait dire  calculable par une machine de Turing . Toutefois, la thèse de Church-Turing nous
indique que cette notion est la même pour tous les modèles de calcul raisonnables. En particulier
pour tous les langages de programmation existant.
Pour boucler cette équivalence entre les langages, et justifier à posteriori le choix de While
comme langage d’étude, il faut qu’on montre que  calculable par une machine de Turing  et
 calculable par un programme While  signifient la même chose. On va faire ça en deux étapes

et en utilisant les équivalences établies précédemment.

Jean-Yves Moyen & Luc Pellissier 23

Institut Galilée L3 S6 – Année 2014–2015
1. Montrer que toute fonction calculable par une machine de Turing est calculable par un
programme Goto.
2. Montrer que toute fonction calculable par une SCM est calculable par une machine de
Turing. Pour ça, on introduira d’abord des machines de Turing à plusieurs rubans avant
de les simplifier.
Les preuves sont ici très techniques. Aussi, seule l’idée principale de la preuve est donnée, les
détails sont laissés de côté.

Des machines de Turing vers Goto

On montre ici que toute fonction calculable par une machine de Turing est aussi calculable
par un programme Goto. Comme pour les équivalences vue précédemment, il suffit pour ça de
montrer comment simuler une machine de Turing à l’aide d’un programme Goto.
Simuler un automate à l’aide de Goto est assez facile. En effet, chaque état correspond à un
label différent et les transitions sont juste des goto vers le bon label. Pour pouvoir manipuler
aisément les lettres, on demande que les atomes sur lesquels sont construits les arbres contiennent
au moins l’alphabet de la machine.
La principale difficulté consiste à simuler le ruban bi-infini de la machine de Turing. Si le
ruban n’était extensible que d’un côté, on pourrait utiliser une liste. L’astuce consiste donc à
couper le ruban en deux et à représenter chaque moitié par une liste.
Le ruban des machines de Turing comporte une case spéciale, celle où se situe la tête de
lecture. On va donc couper le ruban en deux à cet endroit. Les manipulations sur le ruban ont
toutes lieu à l’endroit où se trouve la tête de lecture. Les manipulations sur les listes se font
facilement au début de la liste. Aussi, on va faire en sorte que les deux têtes des listes soient à
l’endroit de la tête de lecture.
On représente donc le ruban par deux listes mais en inversant l’une des deux. C’est-à-dire
qu’il y a une liste qui représente toute les cases non vides du ruban à droite de la tête de lecture
(incluse) et une autre liste qui représente toutes les cases non vides à gauche de la tête de lecture
(exclue) en ordre inverse. Ainsi, la case immédiatement à gauche de la tête de lecture sera la
première valeur d’une liste, donc facilement accessible.
Par exemple, le ruban 1001110001 sera représenté par les deux listes :
AP : [0; 0; 0; 1] (* contenu après la t^
ete, incluse *)
AV : [1; 1; 1; 0; 0 ; 1] (* contenu avant la t^ete, en ordre inverse *)

Avec cette représentation, les manipulations sur le ruban sont très faciles (en première ap-
proche).
– Écrire α :
AP:=cons α (tl AP)
– Aller à gauche :
AP:=cons (hd AV) AP
AV:=tl AV
– Aller à droite :
AV:=cons (hd AP) AV
AP:=tl AP
Les mouvements sont ici incorrects si l’une des deux listes est vide, c’est-à-dire si on est à une
des extrémité du ruban. Dans ce cas, il faut rajouter un # avant de se déplacer. On aura alors,
par exemple pour le mouvement à gauche :

l :if =? nil AV then goto l + 1 else goto l + 2

l + 1 :AV:=cons # AV
l + 2 :AP:=cons (hd AV) AP
l + 3 :AV:=tl AV

Et la même chose en symétrique pour aller à droite.

Jean-Yves Moyen & Luc Pellissier 24

Institut Galilée L3 S6 – Année 2014–2015
Ensuite, pour simuler un état, il faut tester la lettre lue (c’est la tête de AP), et selon la
fonction de transition écrire la nouvelle lettre et effectuer le déplacement.
Par exemple, pour simuler l’état qdroite de la machine qui fait +1, on aurait :
(********************* début de l’état q droite au label l *********************)
(** la lettre est-elle 0 ? *****************************************************)
l : if =? (hd AP) 0 then goto l+1 else goto l+7
(**** cas 0 *)
l+ 1 : AP := cons 0 (hd AP) (* on écrit 0 *)
l+ 2 : if =? nil (tl AP) then goto l+3 else goto l+4 (* mouvement à droite *)
l+ 3 : AP := cons (hd AP) (cons # nil) (* on ajoute un blanc si nécessaire *)
l+ 4 : AV := cons (hd AP) AV
l+ 5 : AP := tl AP (* fin du déplacement *)
l+ 6 : if =? nil nil then goto l else goto l (* on va dans l’état q droite *)
(** la lettre est-elle 1 ? *****************************************************)
l+ 7 : if =? (hd AP) 1 then goto l+8 else goto l+14
(**** cas 1 *)
l+ 8 : AP := cons 1 (hd AP) (* on écrit 1 *)
l+ 9 : if =? nil (tl AP) then goto l+10 else goto l+11 (* mouvement à droite *)
l+10 : AP := cons (hd AP) (cons # nil) (* on ajoute un blanc si nécessaire *)
l+11 : AV := cons (hd AP) AV
l+12 : AP := tl AP (* fin du déplacement *)
l+13 : if =? nil nil then goto l else goto l (* on va dans l’état q droite *)
(** la lettre est-elle # ? *****************************************************)
l+13 : if =? (hd AP) # then goto l+14 else goto -1 (* goto -1 : erreur *)
(**** cas # *)
l+14 : AP := cons # (hd AP) (* on écrit # *)
l+15 : if =? nil AV then goto l+16 else goto l+17 (* mouvement à gauche *)
l+16 : AV := cons # AV (* on ajoute un blanc si nécessaire *)
l+17 : AP := cons (hd AV) AP
l+18 : AV := tl AV (* fin du déplacement *)
l+19 : if =? nil nil then goto l+20 else goto l+20 (* on va dans l’état q plus *)
(********************* début de l’état q plus au label l+20 ********************)
l+20 : ...
Comme souvent, cette transformation n’est pas optimale (par exemple, il est inutile de réécrire la
même lettre que celle qu’on vient de lire). Le but est ici d’avoir une transformation aussi régulière
et simple que possible. On peut très facilement refaire la même transformation pour les autres
états et avoir ainsi un programme Goto qui simule toute la machine.
On voit aisément sur l’exemple que la transformation est un peu lourde. . . la donner en détails
est inutilement compliqué (notamment, ça dépend du nombre de lettres dans l’alphabet, . . . ) Ceci
dit, on voit aisément que cette transformation peut être effectuée sur n’importe quelle machine
de Turing. Donc toute fonction calculable par les machines de Turing est aussi calculable par le
langage Goto.

Des SCM aux machines de Turing à plusieurs rubans

Dans l’autre sens, on va simuler par des machines de Turing le modèle le plus simple vu
jusqu’à présent : les SCM. Pour simplifier la simulation, on va travailler avec des machines de
Turing à plusieurs rubans. On montrera ensuite qu’on peut se restreindre à un seul ruban.
Une machine de Turing a plusieurs rubans comporte un nombre arbitraire de rubans. Chaque
ruban a une tête de lecture. Lors d’une transition, on lit une lettre sur chaque ruban, on écrit une
lettre sur chaque ruban et on déplace la tête de chaque ruban. C’est ici qu’il est particulièrement
utile d’autoriser le  déplacement  immobile pour travailler sur un des rubans sans modifier les
autres. Ainsi, avec k rubans, la fonction de transition a pour type δ : Q × Σk → Q × Σk × {←, ↓
, →}k .

Jean-Yves Moyen & Luc Pellissier 25

Institut Galilée L3 S6 – Année 2014–2015
Pour simuler une SCM avec k compteurs, on va utiliser une machine de Turing à k rubans.
Chaque ruban représente un compteur. Sur chaque ruban, on aura un (et un seul) symbole, par
exemple ♥. La tête de lecture sera toujours sur ou à droite du ♥ et sa distance par rapport au
♥ indique la valeur du compteur. Autrement dit, un compteur qui vaut 4 sera représenté par un
ruban dans l’état ♥####.
Les opérations sur les compteurs des SCM sont alors très faciles à représenter. +1 se fait en
déplaçant la tête du ruban correspondant à droite et -1 se fait en la déplaçant à gauche (si elle
n’est pas déjà sur le ♥). Le test à zéro se fait en regardant si la lettre lue est ♥ ou pas.
Pour représenter l’ensemble d’une SCM, il faut un état par label (par ligne de code) avec les
transitions qui correspondent à ce que fait l’instruction (modifier une variable ou faire un test).
Là aussi, ce n’est pas très compliqué mais un peu lourd. . .
Remarque : un point technique qui n’a pas été traité. . . Par convention, on a décidé qu’au
début de son calcul une machine avait la tête de lecture sur le premier symbole du ruban, ce qui
dans notre traduction correspond nécessairement à la valeur 0 dans la variable d’entrée. . . Pour
y remédier, il faut au début avoir sur le premier ruban, par exemple, ♥aaaa pour représenter
l’entrée 4. Puis la machine va commencer par parcourir ce ruban en remplaçant les ’a’ par des #,
et ajouter un ♥ sur les autres rubans. Ensuite, la simulation proprement dite peut commencer.

Simplification des machines de Turing

Un seul ruban. Dans la construction précédente, on n’a pas besoin d’avoir plusieurs rubans.
En effet, tous les rubans contiennent la même chose (un seul ♥) et ne diffèrent que par la position
de la tête de lecture. On peut donc avoir un seul ruban avec plusieurs têtes de lectures et faire
exactement pareil.
De manière plus générale, on peut regrouper plusieurs rubans en un seul ruban avec plusieurs
têtes de lecture. L’astuce consiste à entrelacer les rubans, c’est-à-dire à alterner les lettres de
chacun, toujours dans le même ordre.
Par exemple, on peut entrelacer les deux rubans 0000101 et aab pour obtenir 0a0a0b0#1#0#1.
Bien sûr, si les rubans utilisent le même alphabet, le résultat est un peu moins facile à désentrelacer
(ex. : retrouver les rubans initiaux entrelacés en 00011001#0#1#).
Il faut ensuite modifier les transitions pour que chaque déplacement soit répété autant de
fois que nécessaire (autant de fois que le nombre de rubans entrelacés). En effet, dans l’exemple
précédent, pour déplacer la tête qui lit ’a’ à gauche, il faut en fait la déplacer 2 fois (pour qu’elle
revienne sur une case qui correspond au même ruban. On peut facilement faire ça en rajoutant
des états intermédiaires (beaucoup, et ça va être moche).
Une seule tête. On peut simuler plusieurs têtes de lectures avec une seule. Pour ça, il faut
multiplier le nombre de symboles pour créer pour chaque symbole une copie  pointée par la
ième tête  et ajouter un marqueur de début de ruban. Ainsi, le ruban précédent deviendrait
♥0a0a0b0#1#0#1, où a et 0 sont des nouveaux symboles (et on doit bien sûr aussi avoir les
symboles b, 0, 1, 1, a et b pour gérer tous les cas !)
Pour simuler une machine à plusieurs têtes, une machine à une seule tête va devoir, pour
chaque état de la machine à plusieurs têtes :
1. Aller au début du ruban (au seul ♥ présent, qui est toujours quelque part à gauche).
2. Avancer pour trouver le symbole écrit en gras, qui correspond à la position de la première
tête.
3. Stocker la valeur de ce symbole dans son état, c’est-à-dire passer dans une copie de l’auto-
mate  j’ai lu 0  (ou 1).
4. Revenir au début.
5. Aller chercher le symbole en italique, qui correspond à la position de la première tête.
6. En fonction de ce symbole, du symbole lu avant et de son état, effectuer la transition. La
lettre en italique peut être modifiée immédiatement.
7. Revenir au début, rechercher la lettre en gras et la modifier.
8. Dans le cas où l’une deux deux têtes veut aller à gauche du ♥, il faut prévoir de déplacer
ce symbole et de le remplacer par un #.

Jean-Yves Moyen & Luc Pellissier 26

Institut Galilée L3 S6 – Année 2014–2015
Bien sûr, la tête de lecture va du coup passer son temps à faire des aller-retours pour chercher
les symboles marqués. . . De plus, la machine aura beaucoup d’états, mais ils vont rester en nombre
fini (car il y a un nombre fini de symboles possible et un nombre fini d’états de la machine à
plusieurs têtes à simuler).
Une seule lettre. Même si ce n’est pas nécessaire ici, on peut aussi restreindre l’alphabet des
machines de Turing à une seule lettre (en plus de #). L’idée est alors de coder chaque symbole
en binaire en utilisant cette lettre et #.

Résumé des transformations

On a construit, plus ou moins en détails, les simulations entre modèles comme représentées
sur le graphe suivant. T M désigne les machines de Turing à 1 ruban et T Mk les machines de
Turing a plusieurs rubans.

While Goto TM T Mk

CM VCM SCM

TD : 4 mai 2015 ×2
TD 07 : machines de Turing.

On est là !

TD : 11 mai 2015 ×2
TD 08.

Partiel : 18 mai 2015

Partiel !

Jean-Yves Moyen & Luc Pellissier 27