Calculabilité

Concept de calculabilité
 La calculabilité est la branche de l'algorithmique qui s'intéresse
aux questions suivantes

 Peut-on tout calculer à l'aide d'un ordinateur ?

 Que signifie calculer à l'aide d'un ordinateur ?

 Peut-on concevoir un algorithme permettant de savoir si un

programme passé en paramètre

 va se terminer ? c'est à dire renvoyer un résultat

 va provoquer une erreur ?

 est correct et ne contient pas de bugs ?

 Exist-il un programme capable de dire si un autre programme est

correct ou buggué
44

Calculabilité
Notion de calculable

 Calcul = programme, algorithme, dérivé du latin “calculus” = petits

cailloux.

 Une fonction f : N → N est calculable s’il existe un

programme/algorithme qui calcule f.

 Cette pseudo-définition est floue : est-ce qu’il existe des fonctions

“C-calculables”, mais pas “Java-calculables” ? est-ce qu’on doit faire
une preuve de calculabilité à chaque fois qu’on change de langage ?
ou d’ordinateur ?

 Heureusement non : on admettra la thèse de Church-Turing, qui

dit que tous les modèles “raisonnables” de calcul sont
équivalents.

45

1
Calculabilité
Codages

 Sur l’ordinateur tout est codé en binaire (Unicode, ASCII, . . .).

 Formellement, un codage binaire d’un ensemble D est une
fonction injective (et calculable) f : D → {0, 1}∗, c-à-d. une
fonction t.q. f (d)  f (dJ) pour tout d  dJ dans D.
 Peut-on coder des ensembles quelconques ? Non, voir la
notion d’ensemble dénombrable.
 Exemple : on peut coder un graphe G avec ensemble de
sommets V = {1, 2 . . . , n} et ensemble d’arêtes E ⊆ V × V
de plusieurs façons :
• par sa matrice d’adjacence M ∈ {0, 1}n×n,
• par des listes d’adjacence,
• ...

46

Calculabilité
Problème de décision
 Un problème de décision A est
 une question portant sur un ensemble de données (entrées)
 dont la réponse est OUI ou NON.
Rq : Ne pas confondre problème et algorithme le résolvant.
 Une instance du problème A est la question posée sur une
donnée/entrée particulière de A.
Exemple:
 Problème : Savoir si un graphe non-orienté est connexe.
 Instance : V = {1, 2, 3, 4, 5}, E = {(1, 2), (2, 3), (3, 1), (4, 5)}
 Algorithme : Depth-first-search.

47

2
 Calculabilité
Autres types de problèmes
 Les problèmes calculatoires, dont la réponse n’est pas
nécessairement binaire (OUI/NON).
Exemple:

 Calculer les composantes connexes d’un graphe non-orienté.

 Calculer les facteurs premiers d’un entier.

 Les problèmes d’optimisation qui maximise ou minimise une entité

Exemple:

 Calculer un cycle de longueur minimale dans un graphe.

 Calculer un cycle de longueur maximale et sans sommet
répété dans un graphe.
 Calculer le plus petit facteur premier d’un entier.
48

Calculabilité
Exemples de problèmes de décision

 Un nombre entier positif n en base 2. n est-il pair ?

 Un nombre entier positif n en base 10. n est-il premier ?
 Une séquence DNA s et un motif p. p apparait-il dans s ?
 Un programme C. Le programme est-il syntaxiquement correct ?
 Un graphe donné par une liste d’adjacence. Le graphe est-il 3-
coloriable ?
 Un graphe donné par une liste d’adjacence. Le graphe est-il 3-
coloriable ?
 Un programme C.Le programme s’arrête-t-il toujours ?
 Des couples de mots (u1, v1), . . . , (un, vn). Existe-t-il des entiers ii, .
. . , ik tels que ui1 . . . uik = vi1 . . . vik ?

49

3
 Calculabilité
Rappels et définitions
 Problèmes de décision versus problèmes de calcul : réponse
OUI/NON pour les premiers, résultat pour les autres. La
première catégorie est juste un cas spécial de la deuxième.
 Instance d’un problème A : une entrée de A. Une instance
positive d’un problème de décision est une instance sur
laquelle la réponse est OUI.
 De manière abstraite, un problème de décision A peut être
interprété comme problème de langages :
 On choisit un codage f des instances de A sur un alphabet Σ (ou
N).
 L’ensemble des codages des instances positives de A définit un
langage LA ⊆ Σ∗ (ou LA ⊆ N).
 La question si une instance I de A est positive revient à
demander si f (I) ∈ LA (problème du mot).
50

Calculabilité
Ensembles dénombrables
 On note N = {0, 1, 2, . . .} l’ensemble des entiers naturels.
 Un ensemble D est dit dénombrable s’il est en bijection avec N.
 Un ensemble D fini ou dénombrable est dit au plus dénombrable
s’il existe une fonction injective f : D → N (ou une fonction
surjective f : N → D).

Exemples. Les ensembles suivants sont dénombrables :

 1. N = {0, 1, . . .},
 Z : les entiers,
 N × N : paires d’entiers positifs ; Nk (k > 2) : les k-uplets,
 Q : les rationnels,
 l’ensemble des matrices avec entrées entières,
 l’ensemble Σ∗ des mots sur un alphabet (fini) Σ,
 l’ensemble des programmes C,
 l’ensemble des arbres orientés,
 l’ensemble des graphes. 51

4
 Calculabilité
Quelques ensembles non dénombrables
Exemples Les ensembles suivants ne sont pas dénombrables :

 l’ensemble des nombres réels,

 l’ensemble des suites infinies d’entiers,
 l’ensemble des parties de N ;
 l’ensemble des fonctions de N dans {0, 1}.
Note Ces ensembles sont en bijection.
À u ne partie X de N, o n associe la suite x = ( x n ) n ≥ 0 définie par

n
x =
1 si n ∈ X
0 si n  X

De même, à toute suite x = (xn)n≥0 à valeurs dans {0, 1}, on associe

bijectivement la fonction fx : N → {0, 1} définie par fx(n) = xn.
52

Calculabilité
Diagonalisation

L’argument suivant, dû à Cantor et nommé diagonalisation, permet de

montrer que l’ensemble E = {0, 1}N des suites infinies de 0 ou 1 est non
dénombrable

 Supposons par contradiction qu’on peut énumérer E : e1, e2, ...

 Soit x = (xn)n≥0 la suite infinie de 0 ou 1 définie par

xn = 1 − (en)n

 Puisque xn  (en)n, on a x en, et ce, pour tout n ∈ N.

 Comme x n’est pas de la forme en, on déduit que x E, contradiction.

53

5
Calculabilité
Problématique
 Combien de mots binaires y a-t-il ? autant que des entiers
positifs (N = {0, 1, 2, . . .}). On dit que l’ensemble {0, 1}∗ est
dénombrable. Les mots binaires peuvent être énumérés, par
exemple : 0, 1, 00, 01, 10, 11, 000, . .
 Combien de programmes/algorithmes existe-t-il ?On peut
coder chaque programme P par un mot en binaire wP ∈ {0, 1}∗, il
suffit de choisir son codage préféré. Ensuite, on peut énumérer
les programmes, en énumérant les mots w ∈ {0, 1}∗ représentant
des programmes. L’ensemble des programmes est donc
dénombrable également.
 Combien de fonctions f : N → N existe-t-il ? Autant que des
nombres réels (ensemble non dénombrable). il existe des
fonctions f : N → N non-calculables.

54

Calculabilité
Problèmes de Hilbert
 David Hilbert, 8 aout 1900, Paris : 23 problèmes dont certains
ont été résolus, d’autre à moitié résolus, et d’autres non résolus

 10ème problème : Est-ce qu’il existe un algorithme qui décide si

un polynôme quelconque (à coefficients entiers) a une solution
entière ?
 La réponse est non; prouvé en 1970 (Youri Matiyasevich)

55

6
Calculabilité
Concept d’algorithme

 Formulation Lewis – Papadimitriou: Un algorithme est une

machine de Turing qui s'arrête pour toutes ses entrées.
 Formulation Wolper: Les langages reconnus par une procédure
effective sont ceux décidés par une machine de Turing.
 La notion d'algorithme / de procédure effective est intuitive
formalisée par la thèse de church-Turing
 La notion de “fonction calculable” ne dépend pas du modèle de
calcul choisi (en supposant un modèle raisonnable).

56

Calculabilité
Thèse de Church-Turing

 La notion physique de la calculabilité, définie comme

étant tout traitement systématique réalisable par un
processus physique ou mécanique, peut être exprimée par
une machine de Turing déterministe.

 Tout ce qu'on peut calculer, à la main, avec un boulier ou

avec un ordinateur ou tout autre moyen se calcule avec une
machine de Turing déterministe.

57

7
 Calculabilité
Problème de l’arrêt

 Problème des énoncés "autoréférants" (principe de la

diagonale)

Exemple

 Le barbier rase tous les hommes qui ne se rasent pas eux-

mêmes et uniquement ceux-là.

 Qui rase le barbier ?

 lui-même ? non parce qu'il ne rase que les hommes ne pouvant pas se raser,
 un autre ? non parce qu'alors il ne peut pas se raser et il rase tous les
hommes qui ne peuvent pas se raser.

58

Calculabilité
Indécidabilité d'un problème
 Il n'existe pas d'algorithme résolvant ce problème
de manière générale
 iI n'existe pas de machine de Turing qui prend en
entrée les données (langage) et qui s'arrête toujours
en donnant une solution.

Exemple
 Le problème de l'arrêt pour les machines de Turing est indécidable.

8
Calculabilité
Machines de Turing : intuition
 Le nombre d’états d’une machine de Turing est fini (pour
comparaison, un ordinateur a un nombre fini de registres).

 La bande représente la mémoire infinie de la machine. Motivation :

sur un ordinateur, on peut ajouter des périphériques mémoire de
façon quasi-illimitée.

 L’accès à la mémoire est séquentiel : la machine peut bouger sa

tête à droite ou à gauche d’une case à chaque étape.

60

Calculabilité
Machines de Turing : intuition

61

9
Calculabilité
Machines de Turing : formalisation
Une machine de Turing (MT) à une bande M = (Q, q0, F, Σ, Γ, δ) est
donnée par:
 Q : ensemble fini d’états.
 q0 : état initial.
 F ⊆ Q : ensemble d’états finaux (ou acceptants).
 Γ : alphabet fini de la bande, avec # ∈ Γ.
 Σ : alphabet d’entrée, avec Σ ⊆ Γ \ {#}.
 δ : ensemble de transitions. Une transition est de la forme
, ,
(p, a, q, b, d), notée 𝑝 𝑞 ,avec
• p, q ∈ Q ,
• a , b ∈ Γ,
• d ∈ {← , −, → } .
= > O n s u ppo s er a qu’aucune transition ne part d’un état de F.

62

Calculabilité
Machines de Turing : représentation graphique

 On représente souvent une MT comme un automate.

 Seules changent les étiquettes des transitions.
 Exemple, avec Γ = {0, 1, #} et Σ = {0, 1} :

0 , #,
1 , #,

#, #, −
p q

δ = {( p , 0 , #, , p), ( p, 1 , #, , p), ( p, #, #, −, q )}

63

10
Calculabilité
Fonctionnement d’une MT

 Initialement, un mot w est écrit sur la bande entouré de #.

 Un calcul d’une MT sur w est une suite de pas de calcul.
 Cette suite peut être finie ou infinie.
 Le calcul commence
 avec la tête de lecture-écriture sur la première lettre de w, dans
l’état initial q0.
 Chaque pas de calcul consiste à appliquer une transition, si
possible.
 Le calcul ne s’arrête que si aucune transition n’est applicable.

64

Calculabilité
Fonctionnement d’une MT

Transition
𝒂,𝒃,𝒅
 Une transition de la forme 𝒑 𝒒 est possible seulement si
 la machine se trouve dans l’état 𝒑, et
 le symbole se trouvant sous la tête de lecture-écriture est 𝒂.
 Dans ce cas, l’application de la transition consiste à
 Changer l’état de contrôle qui devient 𝒒,
 Remplacer le symbole sous la tête de lecture-écriture par 𝒃,
 Bouger la tête d’une case à gauche si 𝒅 = ←, ou bouger la tête
d’une case à droite si d = →, ou ne pas bouger la tête si d = −.

65

11
 Calculabilité
Configurations et calculs

 Une configuration représente un instantanné d u calcul.

 La configuration uqv signifie que
 L’état de contrôle est q
 Le mot écrit sur la bande est uv, entouré par des #,
 La tête de lecture est sur la première lettre de v.
 La configuration initiale sur w est donc q0w.
 Pour 2 configurations C, Cj, on écrit C┤Cj lorsqu’on obtient Cj par
application d’une transition à partir de C.
 Un calcul d’une machine de Turing est une suite de configurations.

C0 ┤ C1 ┤ C2 ┤ ···

66

Calculabilité
Concept formel
 Une machine de Turing comporte :
 Une bande infinie à droite ou à gauche faite de cases
consécutives.
 Dans chaque case se trouve un symbole, éventuellement blanc #.
 Une tête de lecture-écriture, qui peut se déplacer dans les deux
directions d'un caractère à la fois
 Un contrôle à nombre fini d’états de transition
 A chaque étape, en fonction de l'état courant et du symbole
courant, la machine :
 Change d'état,
 Ecrit un symbole à l'emplacement courant,
 Déplace la tête d'une position, à droite ou à gauche, ou ne se
déplace pas.

67

12
Calculabilité
Définitions générale
 Initialement la machine est dans un état initial :
 le mot w = 12…n est dans le ruban, cadré à gauche, avec un blanc
devant et une suite infinie de blancs derrière,
 la tête de lecture / écriture pointe sur l'extrémité gauche du ruban,
 le contrôle sur l'état initial.

 L'état initial de la machine peut être représenté par le

schéma suivant (le symbole # désigne un blanc) :

# 1 2 … n # # …

68

Calculabilité
Calculs acceptants

 Un calcul d’une machine de Turing est une suite de configurations.

C0 ┤ C1 ┤ C2 ┤ · · ·

 3 cas possibles

 Le calcul est infini,

 Le calcul s’arrête sur un état final (de F),
 Le calcul s’arrête sur un état non final (pas de F).

69 /134
69

13
 Calculabilité
Exemple de MT

 Soit la machine de Turing M = (Q, , , , q0) où :

– Q = {q0, q1, q2},  # a b
–  = {a, b}, q0 (q1, #, )
–  = {a, b, #} q1 (q2, #, ) (q1, b, ) (q1, a, )
q2 (q2, a, ) (q2, b, )
( : fonction partielle)
 Représentation graphique de M :

#, #, 
#, #, 
q0 q1 q2

a, b,  a, a, 
b, a,  b, b, 
(pas d’état final)

70

Calculabilité
utilisation de MT

 Les machines de Turing peuvent être utilisées :

 soit pour reconnaître (ou accepter) un langage,
 soit pour calculer une fonction.

 Et si ça devient trop compliqué ?

 On réutilise des morceaux de machines qu’on a déjà écrit

 Ce formalisme peut-il être étendu pour construire des

machines plus puissantes ? Pour reconnaître une classe de
langages plus grande ? Ou calculer plus de fonctions ?

71

14
 Calculabilité
Les machines de Turing pour reconnaître des langages
 Pour qu’une machine de Turing standard puisse reconnaitre un
langage, il faut ajouter la notion d'état final.
 Une machine de Turing augmentée avec des états finaux est
le sextuplet
M = (Q, , , , q0, F) où :
 Q : ensemble fini (non vide) d'états
  : alphabet (ensemble non vide de lettres)
 Γ : alphabet fini, avec # ∈ Γ.
  : fonction de transition : Q    Q
(q, ) = q' (q' : état de la machine après avoir lu la lettre
dans l'état q)
 q0 : état initial : q0  Q
 F : ensemble des états finaux : F  Q

72

Calculabilité
Les machines de Turing pour reconnaître des langages
 Soit M = (Q, , , , q0, F) une machine de Turing. Une chaîne
w  * est acceptée par M ssi :
(q0, #w) ├M* (qf, w'aw'') où :
– qf  F,
– a  ,
– w', w''  *,
– (qf, a) n'est pas défini.

 Le langage accepté par M, noté L(M), est l'ensemble de toutes

les chaînes acceptées par M.

73

15
 Calculabilité
Les machines de Turing pour reconnaître des langages
Exemple
q0 q1 q2 q3
#, #,  a, a,  a, a, 

b, b,  b, b, 

 La suite de configurations associée au mot aabb est :

(q0, #aabb) ├M(q1, #aabb) ├M(q2, #aabb) ├M(q3, #aabb) Comme l'état q3 est
final, et qu'il n'y a pas de transition depuis q3, le mot w = aabb est accepté.

 Pour tout mot w ne contenant par aa, le calcul s'arrête sur le

premier # à droite de w sur le ruban dans un état non final.

Calculabilité
Les machines de Turing pour reconnaître des langages
 Le langage accepté par une machine de Turing est dit
Turing-acceptable ou récursivement énumérable.
 Si la machine de Turing s'arrête sur toutes les entrées
possibles (c-à-d pour tous les mots w, w  L ou w  L), alors
le langage est dit Turing-décidable ou récursif.
 On dit que M semi-décide L, ou encore M accepte L.
 On a alors :
–  w  L, (q0, #w) ├M* (qf, #Y) (qf  F)  YES (accepté)
–  w  L, (q0, #w) ├M* (qf, #N) (qf  F)  NO (rejeté)

75

16
 Calculabilité
Les machines de Turing pour reconnaître des langages
Autre formulation :
 Une machine de Turing est le septuplet
M = (Q, , , , q0, qaccept, qreject) où :
 Q : ensemble fini (non vide) d'états
  : alphabet (ensemble non vide de lettres)
 Γ : alphabet fini de la bande, avec # ∈ Γ.
  : fonction de transition : Q    Q
(q, ) = q' (q' : état de la machine après avoir lu la lettre 
dans l'état q)
 q0 : état initial : q0  Q
 qaccept  Q est l’état d’acceptation de l’entrée,
 qreject  Q est l’état de rejet de l’entrée.

76

Calculabilité
Langages acceptés
On peut utiliser une machine pour accepter des mots.
 Le langage L(M) ⊆ Σ∗ des mots acceptés par une MT. Avec M est
l’ensemble des mots w sur lesquels il existe un calcul fini

C0 ┤ C1 ┤ C2 ┤ · · · Cn

avec C 0 = q 0 w (w est le mot d’entrée) et C n ∈ Γ*F Γ* .

 3 cas exclusifs : u n calcul peut
 soit s’arrêter sur un état acceptant,
 soit s’arrêter sur un état non acceptant,
 soit ne pas s’arrêter.
 O n dit qu’une machin e est déterministe si, pour tout
(p , a ) ∈ Q × Γ, il existe au plus un e transition de la forme
a,b,d
p —−→ q.
 Si M est déterministe, elle n’admet qu’un calcul par
77 /134
entrée. 77

17
Calculabilité
fonctions non calculables
 Un programme est un ensemble fini d'instructions = mot fini sur l'alphabet
(fini) des instructions  Les programmes sont énumérables

 Mot de Bω = fonction N→B. indénombrables Donc les fonctions N→N

aussi

 Le nombre de programmes est donc strictement inférieur au nombre de

fonctions N→N: toutes les fonctions ne sont pas calculables

 Nombre réel = (u,n) avec u un mot de [0-9]ω et n un entier (la position de

la virgule)

 Et de nombreuses fonctions non calculables sont utiles

78

Calculabilité
Les machines de Turing pour calculer des fonctions
 Utiliser les machines de Turing pour calculer des fonctions de
chaînes vers chaînes.

 Soient
 0 et 1 deux alphabets ne contenant pas le symbole blanc (#),

 f une fonction de 0* vers 1*.

 Une machine de Turing M = (Q, 0, , , q0, F) calcule la

fonction f ssi :

 w  0* tel que f(w) = u, on a (q0, #w)├*M(qf, #u)

où : qf  F, et (qf, #) n'est pas défini.

79

18
Calculabilité
Les machines de Turing pour calculer des fonctions

 Lorsqu'une telle machine de Turing existe, la fonction est dite

Turing-calculable.
 La notion de Turing-calculable n'est pas restreinte aux
fonctions de chaînes vers chaînes. Elle peut être étendue de
plusieurs façons :
 Nombre quelconque d’arguments
 Pour des fonctions de N dans N

80

Calculabilité
Les machines de Turing pour calculer des fonctions

 Fonctions avec un nombre quelconque d'arguments de la

forme f : (0*)k  1*

 Une machine de Turing M = (Q, 0, , , q0, F) calcule la

fonction f ssi :

–  1, 2, …, k  0* tels que f(1, 2, …, k) = u, on a

: (q0, #1#2#...#k) ├M* (qf, #u)

où : qf  F, (qf, #) n'est pas défini.

81

19
Calculabilité
Les machines de Turing pour calculer des fonctions
Fonctions de N dans N :
 Notons I un symbole fixé différent de #.
 Tout entier naturel n peut être représenté par la chaîne In en
notation unaire
 L'entier zéro est représenté par la chaîne vide

 Une fonction f : N  N est calculée par une machine de

Turing M, si M calcule la fonction f' : {I}*  {I}* telle que f'(In) =
If(n) pour tout n  N.

82

Calculabilité
Les machines de Turing pour calculer des fonctions

 La fonction successeur définie par succ(n) = n + 1, n0,

est calculée par la machine de Turing

M = (Q, , , , q0, F) où :

– Q = {q0, q1, q2},  # I

q0 (q1, #, )
–  = {I}, q1 (q2, I, ) (q1, I, )
q2 (q2, I, )
–  = {I, #},

– F = {q2}

83

20
Calculabilité
Combinaison des machines de Turing
 Machine de Turing = module ou sous-routine
 Ces modules peuvent être connectés entre eux en utilisant des
règles de combinaisons :
a

M1 M2 M1 M2
b

M3

 Les flèches ne représentent pas des transitions mais des

branchements, conditionnels ou non

84

Calculabilité
Extensions des machines de Turing

 Est-il possible d’accroitre la puissance des machines de Turing ?

 Plusieurs des extensions :
 Un ruban infini dans les deux directions,
 Plusieurs rubans,

 plusieurs têtes sur le ruban,

 un ruban bidimensionnel,
 le non-déterminisme,

 l'accès aléatoire.

 Ces machines étendues peuvent être simulées par des

machines standard 85

21
Calculabilité
Simulation des extensions des machines de Turing
 Pour chaque type d'extension, l'opération de la machine
étendue peut être simulée par une machine de Turing
normale.

 La démonstration consiste dans chaque cas :

 à montrer comment construire une machine normale à partir de la
machine étendue considérée,

 à prouver que la machine normale construite simule

correctement le comportement de la machine de départ.

86

Calculabilité
Machine de Turing à ruban infini dans les deux sens
 Soit une machine de Turing M = (Q, , , , q0, F) dont le
ruban n'a pas de borne à gauche :
 La chaîne d'entrée peut se trouver n'importe où sur le ruban,

 La tête pointe sur le premier blanc à gauche de la chaîne.

 Dans cette machine, une configuration est de la forme :

(q, wau) avec q  Q, w, u  *, a  , où :

 w ne commence pas par un blanc

 u ne finit pas par un blanc.

 On étend la relation entre configurations pour prendre en

compte les déplacements à gauche :
 si (q, a) = (p, b, G) alors (q, au) ├M (p, #bu). 87

22
 Calculabilité
Machine de Turing à ruban infini dans les deux sens
 Une machine M avec ruban infini dans les deux sens n'est
pas plus puissante qu'une machine normale
 Elle ne permet pas de reconnaître plus de langages, ou
calculer plus de fonctions.

 En construisant une machine M'= (Q', , ', ', q0', F'), à partir
de M et qui simule M :
 si M s'arrête sur un mot w, alors M' s'arrête sur ce même mot w,

 si M ne s'arrête pas sur un mot w, alors M' ne s'arrête pas non

plus sur ce même mot w.

88

Calculabilité
Machine de Turing à ruban infini dans les deux sens
 Pour simuler le ruban doublement infini de M dans celui de
M', on définit pour M' un ruban à 2 pistes.
 Ce ruban est obtenu en coupant en 2 celui de M de façon
arbitraire.

Exemple

Ruban de M : … f g h i j k …

B A
i j k …
$
Ruban de M' : h g f …

89

23
Calculabilité
Machine de Turing à plusieurs rubans
 Une machine de Turing étendue peut être caractérisée par
k rubans, chaque ruban étant munie d'une tête autonome.

 Une telle machine respecte les conventions :

 La chaîne d'entrée est initialement placée sur le premier ruban,
cadrée à gauche et précédée d'un blanc, avec la tête sur ce
blanc.

 Les autres rubans sont remplis de blancs avec la tête à l'extrême

gauche.

 Lorsque la machine s'arrête, la chaîne de sortie se trouve sur le

premier ruban, les autres rubans sont ignorées.

90

Calculabilité
Machine de Turing à plusieurs rubans

Contrôle

... # # # 0 1 1 ø0 # # # # # # # ...

... # # # 0 1 1 ø0 # # # # # # # ...

... # # # 0 1 1 ø0 # # # # # # # ...

91

24
 Calculabilité
Machine de Turing à plusieurs rubans
 Machine à k rubans avec
 : fonction partielle de Q  k dans Q  k  {, , -}k
 Soit la transition (qi, a1, …, ak) = (qj, b1, …, bk, D1, …, Dk).
 Cette transition s'applique lorsque :
• La machine est dans l'état courant qi,

• Le symbole courant sur le 1er ruban est a1, … sur le kème ruban est ak.
 Après l'application de cette transition :
• La machine est dans l'état qj,
• Le symbole b1 est écrit sur le 1er ruban à la place de a1, …, bk est
écrit sur le kème ruban à la place de ak,

• La tête de lecture du 1er ruban est déplacée d'une position dans la

direction indiquée par D1, … la tête de lecture du kème ruban est
déplacée d’une position dans la direction indiquée par Dk. 92

Calculabilité
Machine de Turing à plusieurs rubans
Exemple : machine à copier à deux rubans,  = {a, b}

##,##, ##,##, ##,##, ##,##, ##,##, 

q0 q1 q2 q3 q4 q5

a#,aa, #a,#a,S #a,aa, a#,a#,  a#,a#, 

b#,bb, #b,#b,S #b,bb, b#,b#,  b#,b#, 

93

25
 Calculabilité
Machine de Turing non déterministe

 Pour un état et un symbole courant, il peut y avoir

plusieurs choix de comportements possibles.

 Une telle machine est décrite par M = (Q, , , , q0, F) où :

  est un sous-ensemble de Q    K    {, , S}. (Machine de
Turing classique :  est une fonction partielle de K  dans Q    {,
, -}.)

 Ainsi une machine de Turing non déterministe peut produire

deux sorties différentes pour une même entrée.
– Une machine non déterministe est donc un accepteur dont le seul
résultat qui nous intéresse est de savoir si la machine s'arrête ou non,
sans considérer le contenu du ruban.
94

Calculabilité
Machine de Turing non déterministe
 Le non déterminisme n'apporte aucune puissance
supplémentaire, En effet, pour toute machine de Turing non
déterministe M, on peut construire une machine normale M'
telle que pour toute chaîne w  * on a:
– si M s'arrête avec w en entrée, alors M' s'arrête sur w,

– si M ne s'arrête pas sur l'entrée w, alors M' ne s'arrête pas non plus sur w.

 Théorème
Tout langage accepté par une machine de Turing non déterministe est accepté
par une machine de Turing déterministe

95

26
Calculabilité
Machines de Turing universelles

 Existe-t-il une machine de Turing qui peut simuler

n'importe quelle machine de Turing ?
 Le but est de construire une machine de Turing M à laquelle
on fournit :
 la description d'une machine de Turing quelconque M'
 un mot w
 simule l'exécution de M sur w.
 En clair construire une machine de Turing qui serait un
interpréteur de machines de Turing…

 Ces machines de Turing existent et sont appelées

machines de Turing universelles.

96

Calculabilité
Exemples de machines de Turing

 Machine qui effectue while(true);

 Machine qui efface son entrée et s’arrête.

 Machine qui accepte 0∗1∗.

n
 Machine qui accepte {a2 | n ≥ 0}.

 Machine qui accepte {anbn | n ≥ 0}.

 Machine qui accepte {anbncn | n ≥ 0}.

 Machine qui accepte {ww | w ∈ {0, 1}∗}.

97

27
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
Idée : marquer le 1 er a et le 1 er b, et recommencer.
a, a, → a, a, ←
B, B, → B, B, → B, B, ←

a, A, → b, B , ←
q0 q1 q2

#, #, → A, A, →

q3

98

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

a a a b b b # # # # # ...

 L'état initial q0 est sur le a le plus à gauche disponible (s'il existe)

 Il le remplace par A et va en q1
q0  q1 cherche le b le plus à gauche disponible, s'il existe sinon
échec Il le remplace par B et va en q2
 q2 replace le contrôleur sur le a le plus à gauche
disponible sinon sur un A et va en q3
 q3: il n'y a plus de a disponibles, on vérifie qu'il n'y a plus de b non
plus
99

28
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a b b b # # # # # ...

q1

100

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a b b b # # # # # ...

q1

101

29
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a b b b # # # # # ...

q1

102

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a B b b # # # # # ...

q2

103

30
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a B b b # # # # # ...

q2

104

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a B b b # # # # # ...

q2

105

31
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A a a B b b # # # # # ...

q0

106

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B b b # # # # # ...

q1

107

32
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B b b # # # # # ...

q1

108

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B b b # # # # # ...

q1

109

33
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B B b # # # # # ...

q2

110

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B B b # # # # # ...

q2

111

34
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B B b # # # # # ...

q2

112

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A a B B b # # # # # ...

q0

113

35
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B b # # # # # ...

q1

114

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B b # # # # # ...

q1

115

36
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B b # # # # # ...

q1

116

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q2

117

37
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q2

118

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q2

119

38
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q0

120

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q0

121

39
Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q0

122

Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q0

123

40
 Calculabilité
MT acceptant ({anbn | n ≥ 0})∗
a A b B #
q0 (q1,A,) (q0,B, ) (q3,#, )
q1 (q1,a, ) (q2,B, ) (q1,B, )
q2 (q2,a,) (q0,A, ) (q2,B, )
q3

A A A B B B # # # # # ...

q3

Remarques:
 Cette machine est déterministe
 Elle réalise de l'ordre de O(n2) mouvements 124

Calculabilité
n 𝒏
MT acceptant { 𝒂 𝟐 | n ≥ 0 }
Idée : marquer un a sur 2.

A, A, → A, A, →

a, A, → #, #, →
q0 q1 q2

#, #, → a, a, →
a, A, →
q5 q3 q4
#, #, ← a, a, →

a, a, ← A, A, → A, A, →
A, A, ←

125

41
Calculabilité
Exemples de machines de Turing

 Machine qui interprête son entrée comme un entier n, le

remplace par 𝑛/2 et s’arrête.

 Machine qui effectue l’incrément en binaire.

 Machine qui effectue l’addition de deux entiers en unaire.

 Machine qui effectue la multiplication de deux entiers en unaire.

126

Calculabilité
0, 0, →
Calcul de ⌊n/2⌋ 1, 1, →

0 , #, →
#, #, ← 1 , #, →
q1 q2 q3

Incrément en binaire

0, 0, →
1, 1, → 1, 0, ←
0, 1, −
#, #, ← #, 1 , −
q1 q2 q3

127

42
 Calculabilité
Addition en unaire

Le mot d’entrée est de la forme 1 n # 1 m interprété c o m m e la

donn ée de s entiers n et m.

1, 1, → 1, 1, →

# , 1, → #, #, ← 1 , #, −
q1 q2 q3 q4

128

Calculabilité
Nombre de machine de Turing
Considérons une machine de Turing à p états et q lettres.
On peut supposer que les états sont notés : e1, e2, … , ep
et que les symboles du ruban sont #, r1, r2, … , rq.
Il y a un nombre fini de transitions possibles, (même si la machine
n'est pas déterministe), donc le nombre de machines de Turing à p
états et q lettres est fini !

L'ensemble des machines de Turing est dénombrable.

Pour tout alphabet R contenant au moins deux lettres, il est

possible de décrire chaque machine de turing T avec un mot écrit
avec cet alphabet.

129

43
Calculabilité
Machine de Turing Universelle
Il est possible de concevoir une machine de Turing TU capable
d'émuler toutes les machines de Turing.
Plus précisément, si on note R l'alphabet des symboles du ruban
de TU, il existe un codage :

Prog : {machines de Turing} → {mots sur R}

T → 〈T 〉

et un codage des données initiales : x → 〈x〉tels que

x est accepté par T ⇔ (〈T 〉, 〈x〉 ) est accepté par TU

L'ensemble des résultats T (x) est égal à l'ensemble des résultats

TU (〈T 〉, 〈x〉).
130

Calculabilité
Modèles de calcul

 Machine de Turing à mémoire à accès direct

 Fonction Primitive Récursive

 Lambda-Calcul

131

44
Calculabilité
Machine de Turing à mémoire à accès direct
 Random Access : on peut accéder à chaque case en une
étape, contrairement au ruban d'une machine de Turing qui
est à accès séquentiel
 Cette machine comporte :
 T : ruban à accès direct
• T[0], T[1], T[2], T[3] … : cases du ruban

 R0, R1, R2, R3 : registres

 K : compteur de programme (qui est un registre particulier).

132

Calculabilité
Machine de Turing à mémoire à accès direct

133

45
Calculabilité
Machine de Turing à mémoire à accès direct
La machine à mémoire RAM est simulé de la façon suivante :
 Parcourir le ruban représentant la mémoire jusqu’à trouver
l’adresse correspondant au contenu du compteur de
programme (PC);
 Lire et décoder l’instruction se trouvant à cette adresse;
 Le cas échéant trouver les opérandes de cette instruction;
 Exécuter l’instruction, en modifiant éventuellement la
mémoire et/ou des registres;
 Incrémenter le compte de programme par la taille de
l’instruction ou effectuer un saut pour passer au cycle
suivant. 134

Calculabilité
Machine de Turing à mémoire à accès direct
Instructions :
– read j R0 := T[Rj] placer dans le 1er registre le contenu de la
R ème case, R étant la valeur du jème registre
j j
– write j T[Rj] := R0
– store j Rj := R0 placer le contenu du 1er registre dans le jème
registre
– load j R0 := Rj
– load = c R0 := c
– add j R0 := R0 + Rj
– add = c R0 := R0 + c c : nombre entier
– sub j R0 := max{ R0 – Rj, 0 }
– sub = c R0 := max{ R0 – c, 0 }
– half R0 := integer{ R0 / 2 }

135

46
 Calculabilité
Machine de Turing à mémoire à accès direct
Instructions de contrôle :
– jump s K := s s : numéro
– jpos s if R0 > 0 then K := s d’instruction
– jzero s if R0 = 0 then K := s
– halt k := 0
Remarques
– Chaque instruction incrémente K : K := K + 1
– R0 : rôle particulier (accumulateur)

136

Calculabilité
Machine de Turing à mémoire à accès direct
 Une machine de Turing à accès direct est un couple
M = (k, ) où :
 k > 0 est le nombre de registres,
  est une suite finie d'instructions (le programme).

 Une configuration d'une machine M = (k, ) est un

(k+2)-uplet (m, R0, …, Rk-1, T) où :
 m est le compteur de programme,
 Rj (0  j < k) est le contenu du jème registre
 T est un ensemble de couples d'entiers : (i,j)  T signifie que la
ième case du ruban contient la valeur j.

137

47
Calculabilité
Machine de Turing à mémoire à accès direct
 Une telle machine peut être simulée par une machine de
Turing à plusieurs rubans :
 un ruban pour la mémoire,
 un ruban pour le programme
 un ruban pour chaque registre.
 Le contenu de la mémoire est représenté par des paires de
mots (adresse, contenu).
 La simulation pourrait être la répétition du cycle suivant :
 parcourir le ruban du programme jusqu'à l'instruction
correspondant à la valeur trouvée dans le compteur de
programme,
 lire et décoder l'instruction,
 exécuter l'instruction  modifications éventuelles des
rubans correspondant à la mémoire et / ou aux registres,
138
 incrémenter le compteur de programme.

Calculabilité
Machine de Turing à mémoire à accès direct
Exemple
1. store 2 11. add 2
2. load 1 12. store 4
3. jzero 19 13. load 2 read j R0 := T[Rj]
write j T[Rj] := R0
4. half 14. add 2
store j Rj := R0
5. store 3 15. store 2
load j R0 := Rj
6. load 1 16. load 3 add j R0 := R0 + Rj
7. sub 3 17. store 1 sub j R0 := max{ R0 – Rj, 0 }
8. sub 3 18. jump 2 half R0 := integer{ R0 / 2 }
9. jzero 13 19. load 4 jump s K := s
10. load 4 20. halt jpos s if R0 > 0 then K := s
jzero s if R0 = 0 then K := s
halt k := 0

Ca fait quoi ?
Si initialement R0 contient x et R1 contient y, que contient R0 à la fin de
l’exécution ? (convention : tous les registres contiennent initialement 0) 139

48