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

  1. Automates finis
  2. Les 3 théorèmes
  3. Machines de Turing
  4. Diagonalisation
  5. 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

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

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, q0, F) où:
S est un alphabet donné,
Q est un ensemble fini d'états,
q0 Î 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(q0,w) Î F}

Planche 11

Automate fini (2/3)

Graphiquement:
Planche 12

Automate fini (3/3)

Plusieurs représentations possibles:
Planche 13

Automate fini non déterministe (1/2)

Planche 14

Automate fini non déterministe (2/2)

S = {a, b} et L1 = { xaay | x,y Î S* }.
(non déterministe) (déterministe)

Exercice 2 Trouver des automates finis pour reconnaitre les langages suivants:
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 { q0 } comme état initial et F comme ensemble de fin.

Remarque: l'automate déterminisé peut avoir 2n é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

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 {anbn | n > 0}
aaabbb
Xaabbb
Xaabbb
Xaabbb
XaaYbb
XaaYbb
XaaYbb
XaaYbb
XXaYbb
XXaYbb
XXaYbb
XXaYYb
XXaYYb
XXaYYb
XXaYYb
XXXYYb
XXXYYb
XXXYYb
XXXYYY
XXXYYY
XXXYYY
XXXYYY
XXXYYY
XXXYYY
XXXYYYB
XXXYYYBB

Table de transitions (q1 état initial, F = { q5 })
  a b X Y B
q1 (q2,X,d)     (q4,Y,d)  
q2 (q2,a,d) (q3,Y,g)   (q2,Y,d)  
q3 (q3,a,g)   (q1,X,d) (q3,Y,g)  
q4       (q4,Y,d) (q5,B,d)
q5          
Exécution

Planche 18

Machine de Turing (2/6)

Une machine de Turing M est un 7-uplet M = (Q, S, G, d, q0,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,
q0 Î 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
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, q0,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=wRwR 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: 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 == nullreturn 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 qchar 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


Planche 25

Fonctions calculables

Planche 26

Fonction non calculable

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 (truedo ; } } 
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é

Planche 29

Finitude de la calculabilité

Ingrédients nécessaires pour un modèle général de la calculabilité: 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 LATEX by HEVEA.