Planche 1

Inf 431 -- Cours 13
Machines finies
et infinies
http://jeanjacqueslevy.net
secrétariat de l'enseignement:
Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX,
01 69 33 34 67
http://www.enseignement.polytechnique.fr/informatique/IF

Planche 2

Plan

Automates finis
Les 3 théorèmes
Machines de Turing
Diagonalisation
Langages non récursivement énumérables

M. L. Minsky, Computation: Finite and Infinite Machines. Prentice Hall, 1967.

D. Kozen, Automata and Computability. Springer, 1997.

J. Hopcroft, R. Motwani, J. Ullman, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, 2000.

Planche 3

Exemples d'automates finis

Mécanismes à mémoire finie
Protocoles dans les réseaux
Model checking dans la concurrence
Automates cellulaires
Systèmes réactifs
Controleurs dans les circuits
Analyseurs lexicaux

Planche 4

Mécanisme fini (1/2)

Distributeur de boissons:
Deux fentes pour pièces de 0,10, 0,20.
Café si on met 0,30.

Planche 5

Mécanisme fini (2/2)

Machine avec une mémoire tampon (buffer) de taille 2,
2 cafés avec 0,60.

Planche 6

Contrôle de flux

Un récepteur ne doit pas être submergé par les messages d'un émetteur.

!m envoi du message m		?m lecture du message m
?a lecture accusé de réception		!a envoi de l'accusé de réception

Le problème se complique en cas de pertes de messages.
Þ protocole du bit alterné.

Planche 7

Protocoles réseau

Les protocoles TCP/IP (Transmission Control Protocol/Internet Protocol) sont les protocoles de base pour la transmission en série de paquets sur l'internet.

Certains protocoles peuvent générer beaucoup d'états [1, 2, 3].

Planche 8

Automate cellulaire

Tempête sur le plateau: on ne voit rien, on n'entend rien.
Le général convoque n-1 soldats, les aligne sur son coté, et veut les faire tirer tous en même temps.
Le général et les soldats sont des machines synchrones réagissant tous en phase en ne tenant compte que des états de leurs voisins de gauche ou de droite.
3 types de machines: le général, les soldats, le soldat en bout de chaîne.

Exercice 1 Trouver une solution, avec un nombre fini d'états (indépendant de n) pour chaque machine.

Planche 9

Langage reconnu par un automate fini

Mots contenant un nombre impair de a et un nombre impair de b.

Planche 10

Automate fini (1/3)

Un automate fini A est un quintuplet A = (Q, S, d, q₀, F) où:

	S est un alphabet donné,
	Q est un ensemble fini d'états,
	q₀ Î Q est l'état initial,
	F Ì Q est l'ensemble des états finaux,
	d : Q × S ® Q est la fonction de transition

On peut étendre d sur Q × S^* ® Q comme suit:

	d(q, e) = q
	d(q, aw) = d(d(q,a), w)

Le langage reconnu par l'automate A est:

T(A) = {w | d(q₀,w) Î F}

Planche 11

Automate fini (2/3)

Graphiquement:

La bande de lecture n'est pas modifiable (read-only)
La tête de lecture avance d'une case vers la droite à chaque transition.
L'état q évolue vers l'état q' = d(q, e) si le caractère e est sous la tête de lecture.

Planche 12

Automate fini (3/3)

Plusieurs représentations possibles:

En dur, dans le contrôle fini du programme

int c = in.read(); int q = q0;switch (q) { case 0: if (c == 'a') ... else if (c == 'b') ...; break; case 1: if (c == 'b') ... else if (c == 'c') ... ; break; ... case 10: if ... break;}
matrice |Q| × |S| pour représenter la fonction de transition
vecteur de |Q| listes d'association (c', q')
(graphe dont les sommets sont les états et les arcs sont les transitions étiquetées par les lettres)

Planche 13

Automate fini non déterministe (1/2)

A chaque état, l'automate choisit entre plusieurs transitions.

Formellement, d : Q × S ® 2^Q
On étend d comme suit

d(q, e) = {q} d(q, aw) =

È

q' Î d(q, a)
d(q',w)
Le langage reconnu par l'automate A est:

T(A) = {w | d(q₀,w) Ç F ¹ Ø }
Un mot est accepté si une série de choix amène à un état de F.

(Les mauvais choix ne comptent pas).

Planche 14

Automate fini non déterministe (2/2)

S = {a, b} et L₁ = { xaay | x,y Î S^* }.


(non déterministe)	(déterministe)

Exercice 2 Trouver des automates finis pour reconnaitre les langages suivants:

L₂ = { xaay | x,y Î S^* } È { xbby | x,y Î S^* }
L₃ = { xwy | x,y Î S^* } où w est un mot donné de S^*
L₄ Ì S^* tel que a est la 6ème lettre à partir de la fin dans tout w Î ₄L.

Planche 15

Les 3 théorèmes fondamentaux

Theorem 1[Rabin-Scott] Tout langage reconnu par un automate fini non déterministe est reconnu par un automate fini déterministe.

Démonstration: on considère l'automate déterministe défini sur 2^Q, en prenant { q₀ } comme état initial et F comme ensemble de fin.

Remarque: l'automate déterminisé peut avoir 2ⁿ états, si n est le nombre d'états de l'automate non-déterministe.

Theorem 2[Myhill - Nerode] Tout langage reconnu par un automate fini est reconnu par un automate déterministe minimal unique à un isomorphisme près sur le nom des états.

Theorem 3[Kleene] Les langages reconnus par un automate fini sont exactement ceux décrits par les expressions régulières.

Langages réguliers (ou rationnels en France).

Planche 16

Autres définitions d'automate fini

d : Q × S È {e} ® Q
déterministe avec transitions vides
d : Q × S È {e} ® 2^Q
non déterministe avec transitions vides
d : Q × S^* ® 2^Q défini sur un sous-ensemble fini de S^*
non déterministe avec transitions composées
d : Q × S ® 2^{Q ×
{gauche, droite }}
non déterministe, déplacement dans les 2 sens

Exercice 3 Montrer que toutes ces définitions sont équivalentes à la définition initiale d'automate fini (dernier cas plus dur).

Exercice 4 Montrer que si dans la définition 3 on enlève la restriction finie, alors on sort de la définition des automates finis.

Planche 17

Machine de Turing (1/6)

Reconnaître {aⁿbⁿ | n > 0}

aaabbb

Xaabbb

Xaabbb

XaaYbb

XXaYbb

XXaYbb

XXaYbb

XXaYYb

XXaYYb

XXXYYb

XXXYYb

XXXYYb

XXXYYY

XXXYYY

XXXYYY

XXXYYY

XXXYYY

XXXYYY

XXXYYYB

XXXYYYBB

Table de transitions (q₁ état initial, F = { q₅ })

	a	b	X	Y	B
q₁	(q₂,X,d)			(q₄,Y,d)
q₂	(q₂,a,d)	(q₃,Y,g)		(q₂,Y,d)
q₃	(q₃,a,g)		(q₁,X,d)	(q₃,Y,g)
q₄				(q₄,Y,d)	(q₅,B,d)
q₅

Exécution

Planche 18

Machine de Turing (2/6)

Une machine de Turing M est un 7-uplet M = (Q, S, G, d, q₀,B, F) où:

	S est un alphabet d'entrée,
	G est un alphabet des symboles de la bande (S Ì G),
	B Î G - S est le symbole blanc,
	Q est un ensemble fini d'états,
	q₀ Î Q est l'état initial,
	F Ì Q est l'ensemble des états finaux,
	*d : Q × G ® Q × G × { gauche, droite* } est la fonction de transition**

(u, q, v) est une configuration où

q Î Q est l'état courant,
u = X₁X₂... X_i-1 Î G^* est le mot à gauche de la tête de lecture,
v = X_iX_i+1... X_n Î G^* est le mot à droite de la tête de lecture jusqu'à un caractère X_n suivi uniquement de blancs.

Planche 19

Machine de Turing (3/6)

Les transitions sont définies par:

d (q, X) = (q', Y, *droite*)	Þ	(u, q, Xv) ¾® (uY, q', v)
d (q, B) = (q', Y, *droite*)	Þ	(u, q, e) ¾® (uY, q', e)
d (q, X) = (q', Y, *gauche*)	Þ	*(uZ, q, Xv) ¾® (u, q', ZYv)*
d (q, B) = (q', Y, *gauche*)	Þ	(uZ, q, e) ¾® (u, q', ZY)

Le langage (récursivement énumérable) reconnu par M est:

T(M) = {w | wÎ S^*, (e, q₀,w) ¾®^* (u,q,v), q Î F }

(La bande modifiable constitue une réserve infinie de mémoire)

Planche 20

Machine de Turing (4/6)

Exercice 5 Donner une machine de Turing qui reconnaisse les palindromes w formés de a et de b tels que w=w^R où w^R est l'image mirroir de w.

Exercice 6 Trouver une machine de Turing qui reconnaisse les mots bien parenthésés formés de a et de b.

Exercice 7 Donner une machine de Turing qui calcule le successeur x+1 de tout nombre binaire x.

Exercice 8 Donner une machine de Turing qui calcule la somme x+y de tous nombres binaires x et y.

Exercice 9 Soit S(n) le nombre maximal d'étapes que peut mettre une machine de Turing à n états avant de s'arréter en partant d'une bande complètement blanche. Calculer S(n) pour n £ 4 (le castor affairé, Rado).

Planche 21

Machine de Turing (5/6)

Autres définitions possibles de Machine de Turing:

la bande est infinie à gauche et à droite
avec plusieurs bandes et têtes de lecture
d : Q × G ® Q × G × { gauche, immobile, droite }
d : Q × G ® 2^{Q × G ×
{ gauche, droite }}
non déterministe
d : Q × G^* ® 2^{Q × G ×
{ gauche, droite }} défini sur un sous-ensemble fini de G^* non déterministe avec transitions composées

Exercice 10 Montrer que toutes ces définitions sont équivalentes à la définition initiale.

Exercice 11 Montrer que si dans la définition 4 on enlève la restriction finie, alors on sort de la définition des machines de Turing.

Planche 22

Machine de Turing (6/6)

uringbsurdeacileouclefs0ineltaystemuteterintln

class Turing { int q0; Liste fin; Action[ ][ ] delta; static boolean accepter (String w, Turing m) { StringBuffer bande = new StringBuffer (w); int tete = 0; int q = m.q0; while ( !Liste.estDans(m.fin, q) ) { char c = tete < bande.length() ? bande.charAt(tete) : BLANC; Action a = m.delta [q][c]; if (a == null) return false; q = a.q; if (a.dept == GAUCHE && tete > 0) bande.setCharAt(tete--, a.c); else if (a.dept == DROITE && tete < bande.length()) bande.setCharAt(tete++, a.c); else if (a.dept == DROITE && tete == bande.length()) { bande.append(a.c); // new déguisé (allocation dans le tas) ++tete; } else return false; } return true; }class Action { int q; char c; int dep;}

Planche 23

Turing [1936], Proc. London Math. Soc.
``On computable numbers, with an application to the Entscheidungsproblem''

Computing is normally done by writing certain symbols on paper. We may suppose this paper is divided into squares like a child's arithmetic book. In elementary arithmetic the two-dimensional character of the paper is sometimes used. But such a use is always avoidable, and I think that it will be agreed that the two-dimensional character of paper is no essential of computation. I assume then that the computation is carried out on one-dimensional paper, i.e., on a tape divided into squares. I shall also suppose that the number of symbols which may be printed is finite. If we were to allow an infinity of symbols, then there would be symbols differing to an arbitrary small extent. The effect of this restriction of the number of symbols is not very serious. It is always possible to use sequences of symbols in the place of single symbols. Thus an Arabic numeral such as 17 or 9999999999999 is normally treated as a single symbol. Similarly in any European language words are treated as single symbols (Chinese, however, attempts to have an enumerable infinity of symbols). The differences from our point of view between the single and compound symbols is that the compound symbols, if they are not lengthy, cannot be observed at one glance. This in accordance with experience. We cannot tell at a glance whether 9999999999999999999 and 9999999999999999999 are the same.

The behaviour of the computer at any moment is determined by the symbols which he is observing, and his `state of mind' at that moment. We may suppose that there is a bound B to the number of symbols or squares which the computer can observe at one moment. If he wishes to observe more, he must use successive observations. We will also suppose that the number of states of mind which need be taken into account is finite. The reasons for this are of the same character as those which restrict the number of symbols. If we admitted an infinity of states of mind, some of them will be `arbritrarily close' and will be confused. Again, the restriction is not one which seriously affects computation, since the use of more complicated states of mind can be avoided by writing more symbols on the tape.

Let us imagine the operations performed by the computer to be split up to `simple operations' which are so elementary that it is not easy to imagine them further divided. Every such operation consists of some change of the physical system consisting of the computer and his tape. We know the state of the system if we know the sequence of symbols on the tape, which of these are observed by the computer (possibly with a special order), and `state of mind' of the computer. We may suppose that in a simple operation not more than one symbol is altered. Any other changes can be split up into simple changes of this kind. The situation in regard to the squares whose symbols may be altered in this way is the same as in regard to observed squares. We may, therefore, without loss of generality, assume that the squares whose symbols are changed are always 'observed' squares.

Planche 24

Diagonalisation

Un langage récursivement énumérable peut être infini.
Sa représentation par une machine de Turing est finie (nombre d'états fini, fonction de transition finie).

Þ On peut énumérer les machines de Turing, en prenant un codage quelconque de leur description. Soit M_i la i-ème machine de Turing.
Egalement, on peut énumérer les mots sur S^* (en ordre par longueur, puis par ordre alphabétique par exemple). Soit w_i le i-ème mot.
Considérons le langage L = {w_i | w_i Î S^*, w_i ÏT(M_i) }.

S'il existe une machine M_d telle que L = T(M_d), alors
w_d Î T(M_d) ssi w_d ÏT(M_d)
Contradiction!
Þ

Il existe des langages non récursivement énumérables.

Planche 25

Fonctions calculables

Si les mots figurant au début et à la fin sur la bande sont des nombres, une machine de Turing (déterministe) calcule des fonctions de N ® N.

Une fonction calculable est une fonction calculée par une telle machine de Turing.
Si, avec j au début sur la bande, M_i termine sans produire un entier sur la bande, on donnera 0 comme résultat de la fonction calculable correspondante.
Comme les machines de Turing sont dénombrables, les fonctions calculables sont en bijection avec N.
card(N ® N) > card(N) [Cantor]
Þ

Il existe des fonctions non calculables.

Planche 26

Fonction non calculable

Soit H une machine testant l'arrêt de toute machine M_i de Turing.

H(i) =

0 si M_i(i) diverge

1 si M_i(i) converge
On peut alors construire une machine D telle que

D(i) =

converge si M_i(i) diverge

diverge si M_i(i) converge

Alors si D = M_d, contradiction sur D(d).
Þ

Il n'existe pas de machine de Turing testant

l'arrêt de toute machine de Turing.

Planche 27

Le problème de l'arrêt en Java

uringbsurdeacileouclefsilempilerepilerystemutrintrintln

class Turing { static boolean termine (Object o) { // La valeur retournée vaut true si o.f() // termine. Sinon la valeur retournée vaut false. // (le code est breveté par le vendeur)} }class Facile { void f () { } } class Boucle { void f () { while (true) do ; } } class Absurde { void f () { while (Turing.termine(this)) ; } }class Test { public static void main (String[ ] args) { Facile o1 = new Facile(); System.out.println (Turing.termine(o1)); Boucle o2 = new Boucle(); System.out.println (Turing.termine(o2)); Absurde o3 = new Absurde(); System.out.println (Turing.termine(o3));} }

o3.f() termine ssi o3.f() ne termine pas !!
Þ Contradiction (vive le logiciel libre!).

Planche 28

Expressivité -- calculabilité

Programmer des machines de Turing est fastidieux. Il manque un langage de programmation de haut niveau.
Si on rajoute des instructions de haut niveau, peut-on reconnaître plus de langages sur S^*?
Peut-on calculer plus de fonctions avec des instructions de plus haut niveau?

Thèse [Church, 35] Tous les modèles de la

calculabilité sont équivalents.
Les machines de Turing, calculent toutes les fonctions calculables. Cette hypothèse n'a jamais été invalidée.
Autres modèles tous équivalents: l-calcul [Church], systèmes de Post [Post], fonctions récursives [Kleene], dominos de Wang, Java, ML, Ocaml, Ada, C, C++, PC Compaq, PC hp, Mac, etc.

Planche 29

Finitude de la calculabilité

Ingrédients nécessaires pour un modèle général de la calculabilité:

description finie du fonctionnement
réserve infinie d'espace mémoire

Exercice 12 Montrer que les machines de Turing read-only (ne pouvant donc pas écrire sur la bande) sont identiques aux automates finis.

Exercice 13 Montrer que les machines de Turing (ne pouvant écrire qu'une partie bornée de la bande) sont identiques aux automates finis.

Exercice 14 Pourquoi un ordinateur n'est pas un automate fini?

Exercice 15 Refaire les raisonnements de diagonalisation avec des programmes Java au lieu de machines de Turing.

This document was translated from L^AT_EX by H^EV^EA.