Calculabilité

Cours 2 : machines de Turing

Kévin Perrot – L3 Info Aix Marseille Université – printemps 2021

Table des matières

3 Machines de Turing 1
3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
3.2 Décider et calculer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
3.3 Propriétés de clôture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.4 Un peu d’histoire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5

3 Machines de Turing
Pour montrer qu’une fonction est calculable ou qu’un langage est décidable (distinc-
tion discutée en 3.2) il faut donner un algorithme. Pour montrer qu’une fonction n’est
pas calculable ou qu’un langage est indécibable, il faut d’abord définir l’ensemble des
algorithmes (car cela définit l’ensemble de ce qui est calculable/décibable). L’intérêt des
machines de Turing est qu’elles définissent les algorithmes de façon intuitive et simple !
Imaginez devoir définir mathématiquement votre langage de programmation préféré dans
ses moindres détails. . .
L’idée d’Alan Turing est inspirée du calculateur humain devant sa feuille [1] :
— feuilles découpées en cases : ruban ;
— crayon posé sur une case : tête de lecture/écriture, déplacement ;
— l’opérateur dispose d’une mémoire finie (son cerveau) : états.

3.1 Définitions

Définition 1. Une machine de Turing (MT) déterministe est un 7-uplet

M = (Q, Γ, Σ, δ, q0 , B, qF )
où
— Q est un ensemble fini : les états,
— Γ est un ensemble fini : l’alphabet de ruban,
— Σ ⊂ Γ est l’alphabet d’entrée,
— δ : (Q \ {qF }) × Γ → Q × Γ × {L, R} est la fonction de transition décrite ci-après,
— q0 ∈ Q est l’état initial,
— B ∈ Γ \ Σ est le symbole blanc,
— qF ∈ Q est l’état final.

1
 Γ contient tous les symboles qui peuvent apparaı̂tre sur le ruban. En particulier Σ ⊂ Γ
car l’entrée est initialement écrite sur le ruban. On supposera que Q ∩ Γ = ∅ pour qu’il
n’y ait pas de confusion entre états et symboles du ruban.
La fonction de transition δ est une application partielle
de l’ensemble (Q \ {qF }) × Γ dans l’ensemble Q × Γ × {L, R}.
Une transition
δ(q, a) = (p, b, L)
signifie que dans l’état q et en lisant le symbole de ruban a, la machine passe dans l’état
p, remplace a par b sur le ruban, et déplace la tête de lecture/écriture d’une cellule sur
la gauche (L pour left et R pour right). Une application partielle peut être indéfinie pour
certains arguments, auquel cas la machine n’a pas de mouvement suivant et s’arrête. En
particulier, il n’y a pas de transition depuis l’état final qF .
Initialement, le mot d’entrée est écrit sur le ruban et toutes les autres cellules contiennent
le symbole blanc B. La machine est dans l’état q0 , et la tête de lecture/écriture est posi-
tionnée sur la lettre la plus à gauche de l’entrée. Il y a trois possibilités :
— acceptation si au cours des transitions la machine entre dans l’état final qF (et
donc s’arrête),
— rejet si au cours des transitions la machine s’arrête dans un état non final (s’il
n’y a pas de mouvement suivant à réaliser),
— rejet si la machine ne s’arrête jamais.

Définition 2. Une description instantanée (DI) d’une MT décrit sa configuration

courante. C’est un mot

uqav ∈ ({} ∪ (Γ \ {B})Γ∗ )QΓ({} ∪ Γ∗ (Γ \ {B})

avec q ∈ Q l’état courant, u, v ∈ Γ∗ le contenu du ruban à gauche et à droite de la

tête, respectivement, jusqu’au dernier symbole non blanc, et a ∈ Γ le symbole de ruban
actuellement sous la tête.

Définition 3. Un mouvement, une transition, un déplacement de la MT à partir

de la DI α = uqav vers la DI suivante β sera noté α ` β. Plus précisément :
1. Si δ(q, a) = (p, b, L),
— si u =  alors β = pBbv (potentiellement en supprimant les B à la fin de bv),
— si u = u0 c avec c ∈ Γ alors β = u0 pcbv (potentiellement en supprimant les B à
la fin de bv).
2. Si δ(q, a) = (p, b, R),
— si v =  alors β = ubpB (potentiellement en supprimant les B au début de ub),
— si v 6=  alors β = ubpv (potentiellement en supprimant les B au début de ub).
3. Si δ(q, a) est indéfini alors aucun mouvement n’est possible depuis α, et α est une
DI d’arrêt. Si q = qF alors α est une DI acceptante.

Notation 4. Notre modèle de MT est déterministe, ce qui signifie que pour tout α il y
a au plus un β tel que α ` β. Nous noterons
α `∗ β
si la MT change α en β en n’importe quel nombre d’étapes (0 inclus, auquel cas α = β),
α `+ β si la MT change α en β en au moins une étape, et
α `i β si la MT change α en β en exactement i étapes.

2
 Pour tout w ∈ Σ∗ nous pouvons définir la DI de départ correspondante

q0 w, si w 6= 
ιw =
q0 B si w = .

3.2 Décider et calculer

Définition 5. Le langage reconnu (ou accepté) par la MT M est

L(M ) = {w | w ∈ Σ∗ et ιw `∗ uqF v avec u, v ∈ Γ∗ }

Définition 6. Un langage est semi-décidable s’il est reconnu par une machine de
Turing. Un langage est décibable, s’il est reconnu par une machine de Turing qui
s’arrête sur toutes les entrées.

Attention à la différence ! Tout langage décidable est également semi-décidable.

Notation 7. Le résultat du calcul de la MT M sur l’entrée w sera noté


 uv si ιw `∗ uqF v avec u, v ∈ Γ∗
M (w) = uav si ιw `∗ uqav avec u, v ∈ Γ∗ et δ(q, a) non défini†
↑ si l’exécution ne termine pas.


†potentiellement en supprimant les B à la fin de av.

Définition 8. Une fonction f : Σ∗ → Γ∗ est calculable si et seulement si il existe une

MT M telle que pour tout w ∈ Σ∗ : f (w) = M (w).

Remarque 9. Décider (un langage) est équivalent à calculer (une fonction).

⇐ Décider un langage L revient à calculer sa fonction caractéristique

fL : Σ ∗ → 
{0, 1}
1 si w ∈ L
w 7→
0 sinon.

⇒ Calculer une fonction f revient à décider le langage

Lf = {(x, y) | y = f (x)}.

Nous n’établirons pas de distinction très nette entre calculer et décider.

— Dans la vraie vie on dira plutôt calculer (plus parlant).
— Dans le monde des mathématiques on dira plutôt décider (plus simple à formaliser).
— Récursif est synonyme de calculable et décidable.

Remarque 10. Le terme semi-décidable (définition 6) vient du fait que la machine

de Turing qui semi-décide s’arrête pour toute entrée qui appartient au langage (on a à
coup sûr la réponse si le mot appartient au langage car la machine atteindra un état final
acceptant), mais ne s’arrêt pas obligatoirement sur les entrées qui n’appartiennent pas au
langage (si le mot n’appartient pas au langage, la machine peut ne pas s’arrêter). Il y a
donc une asymétrie entre les mots dans et en dehors du langage. En lançant une telle
machine sur un mot d’entrée dont on se demande s’il appartient au langage, on ne sait

3
pas si la machine va s’arrêter et donner une réponse, mais on sait que si le mot est dans
le langage alors la machine finira par nous donner la réponse en l’acceptant au bout d’un
temps fini (mais a priori inconnu).
Pour semi-décidable on dit également récursivement énumérable car il est possible
d’écrire (pour ces langages) une MT qui va, à partir d’une entrée vide, énumérer tous les
mots du langage, un à un et sans en oublier aucun (dans n’importe quel ordre, possible-
ment en répétant plusieurs fois certains mots). Pour formaliser cette idée nous aurons un
état spécial d’énumération qe (quand on entre dans cet état c’est qu’on énumère le mot
présent sur le ruban, par convention à la droite de la tête de lecture/écriture) tel que :
pour tout mot w ∈ L, il existe une étape t telle que ι `t w0 qe w.
Exemple 11. Le langage suivant est décidable :
{w ∈ {a, b}∗ | w est un palindrome}
donc il existe une machine Mpalindrome qui le décide (répond oui/non sur toute entrée).

3.3 Propriétés de clôture

Théorème 12. Les propriétés suivantes sont vraies :
1. la famille des langages décidabless est close par complémentation ;
2. les familles des langages décidables et semi-décidables sont closes par union et
intersection ;
3. Un langage L ⊆ Σ∗ est décidable si et seulement si L et Σ∗ \L sont semi-décidables.
Idées de démonstration.
1. On veut prouver L décidable implique Σ∗ \ L décidable. Soit M la machine dont le
langage est L(M ) = L et qui s’arrête toujours, nous allons construire une nouvelle
machine M 0 dont le langage est L(M 0 ) = Σ∗ \ L et qui s’arrête toujours. Pour cela,
on ajoute un puits global qui sera notre nouvel état final (toutes les transitions
indéfinies de M mènent vers le nouvel état final de M 0 , et l’état final de M n’a
aucune transition dans M 0 ). Ainsi, la machine M 0 s’arrête dans son état final à
chaque fois que M s’arrêtait sur un état non final (w ∈ / L(M ) ⇒ w ∈ L(M 0 )). De
plus, chaque fois que M s’arrêtait dans son état final, M 0 s’arrête également mais
cet état n’est plus final (w ∈ L(M ) ⇒ w ∈ / L(M 0 )).
2. Concentrons nous sur l’intersection de deux lanages décidables, les autres démon-
strations sont analogues. Soient L1 = L(M1 ) et L2 = L(M2 ). On veut construire
une machine M 0 qui décide le langage L(M 0 ) = L1 ∩ L2 . Pour cela, sur une entrée
w la machine M 0 simule (pour cela il suffit de modifier l’état final des machines
simulées) :
— M1 sur l’entrée w (on sait que le calcul termine),
— puis M2 sur l’entrée w (on sait que le calcul termine),
se souvient du résultat de chaque simulation (arrêt dans l’état final ou non), et va
dans l’état final si et seulement si M1 et M2 acceptent w (sinon M 0 va dans un
nouvel état non final à partir duquel aucune transition n’est possible).
3. Le sens ⇒ est assez simple et laissé en exercice. Pour ⇐, on construit une machine
qui simule en parallèle les deux machines qui reconnaissent L et L \ Σ∗ . Chacune
peut ne pas s’arrêter, mais puisque soit l’une soit l’autre accepte w, soit l’une soit
l’autre entrera dans son état final, et nous pourrons alors :

4
 — entrer dans notre état final si c’est la machine qui reconnait L qui est entrée
dans son état final,
— entrer dans un nouvel état non final sans transition si c’est la machine qui
reconnait Σ∗ \ L qui est entrée dans son état final.

3.4 Un peu d’histoire

Cantor Hilbert Gödel Church Kleene Turing von Neumann

(1845-1918) (1862-1943) (1906-1978) (1903-1995) (1909-1994) (1912-1954) (1903-1957)

A la toute fin du XIXe siècle, Georg Cantor définit les fondements de la théorie des
ensembles, dont l’usage systématique (c’est-à-dire qui est utilisée dans tous les domaines)
allait bouleverser les fondements de la logique mathématique. En 1900, pour fêter le pas-
sage au XXe siècle, David Hilbert énonce 23 grands problèmes ouverts, dont le suivant :
les propriétés qui s’expriment en langage mathématique sont-elles toutes décidables ?
Si la réponse devait être affirmatives, les propriétés mathématiques valides seraient des
théorèmes dérivables mécaniquement de quelques axiomes dans un système formel. Au-
trement dit : on pourrait remplacer les mathématicien·ne·s par des machines surpuis-
santes ! En 1931, Kurt Gödel met un terme à cette interrogation : il existe des propriétés
mathématiques indécidables (dans tous les systèmes d’axiomes qui formalisent au moins
l’arithmétique). Autrement dit : mathématicien·ne·s 1 - machines 0. Entre 1932 et 1936,
Alsonso Church et Stephen Kleene proposent des modèles de calculs (le λ-calcul et les
fonctions µ-récursives) qui semblent capturer la notion intuitive de fonctions calculables,
mais il est un peu difficile de s’en convaincre. . . Notons tout de même que le λ-calcul est
extrêmement minimaliste, ce qui rend sa compréhension mathématique fort intéressante :
tout est capturé en quelques lignes de définition ! Indépendamment, en 1936, Alan Tu-
ring propose sa définition de machines. En 1937 il montre que la classe des fonctions
λ-calculables est égale à la classe des fonctions programmables sur les machines de Tu-
ring. Les machines de Turing permettent de reformuler en termes intuitifs de calculs les
résultats de Kurt Gödel (qui étaient exprimés en termes de démonstration). Avec l’aide
de Von Neumann (et d’autres), les premiers ordinateurs programmables verront le jour
quelques années plus tard !
La vie de Turing vaut le coup d’oeil (savez vous que le rôle de Turing durant la seconde
guerre mondiale est resté secret d’Etat de nombreuses années ?).
e-penser (13’) : [Link]

Références
[1] A. M. Turing. On computable numbers, with an application to the Entscheidung-
sproblem. Proceedings of the London Mathematical Society, 2(42) :230–265, 1936.