La machine de Turing

Une bande infinie qui est une suite de cases. Chaque case porte un symbole qui est un élément d'un ensemble fini de symboles que l'on appelle alphabet.Une tête de lecture/écriture peut se déplacer devant la bande. Elle se positionne exactement devant une case.A chaque mouvement de la tête, il n'y a déplacement que d'une case, soit vers la droite, soit vers la gauche.

Reste maintenant à spécifier le comportement de la machine.

Le comportement de la machine est modélisé par un diagramme de transitions (automate fini).

La machine de Turing

Les états sont représentés par des certangles et les transitions par des flèches. Notre automate est ici déterministe (il n'y a pas deux transitions partant d'un même état et étiquetées par le même "événement".- nous appellerons événement, le fait de lire un symbole). Les transitions sont étiquetées par un texte de la forme :a/b, G oua/b, DCeci ce lit :Chaque fois que la machine est dans un état s et que un symbole a est lu par la tête à ce moment là, - la machine efface le symbole a, - et écrit le symbole b à sa place - puis, la tête est déplacée d'une case vers la gauche, et entre alors dans l'état t.

La machine de Turingdépart est l'état de départoui et non sont les états d'arrêt

La machine démarre à la case la plus à gauche de la bande. Elle fonctionne selon l'automate. Elle s'arrête lorsque que l'automate entre un état d'arrêt.

Exercice : Considérez la bande suivante : ###abba##

Faites fonctionner la machine.

Notre machine nous dit si la chaîne de caractères est un palindrome. Dans notre cas, elle a dû s'arrêter dans l'état final oui.

La machine de Turing

La thèse de Church/Turing

Qu'est-ce qui peut être fait par une machine de Turing et à quel coût ?

Réponse :

" Les machines de Turing sont capables de résoudre tout problème algorithmique effectivement solvable ou dit autrement, tout problème algorithmique pour lequel on peut trouver un algorithme qui peut être programmé dans un certain langage de programmation, tout langage, exécutable sur un certain ordinateur, tout ordinateur, même celui qui n'a pas encore été construit, mais qui peut être construit, et même ceux qui nécessitent des durées et des mémoires non limitées, pour des entrées encore plus grandes, est solvable par une machine de Turing." Harel, p. 233

La thèse de Church/Turing

N.B. : il n'agit d'une thèse ! (et non d'un théorème qui a été démontré). C'est qu'en effet, elle porte sur un concept non formel, celui de "calculabilité effective", que la thèse assimile à la notion mathématique de "résolution par une machine de Turing"

Bibliographie :Le texte de Turing en traduction française :Alan Turing, Jean-Yves Girard, La machine de Turing, traductions de l'anglais par Julien Basch & Patrice Blanchard, Sources du savoir, Seuil , ISBN : 2-02-013571.X

David Harel, Algorithmics, The spirit of Computing, Second Edition, Addison-Wesley, ISBN : 0-201-50401-4

Automates

1) Automates simples déterministes : des états, des transitions entre états

2) Automates simples indéterministes

plus d'une transition part d'un automate. Le choix de la transition est indéterministe.

3) Automates avec événements et sorties 3.1) le cas où les sorties sont notées sur les transitions

(automates de Mealy)

3.2) le cas où les sorties sont notées sur les états (automates de Moore)

LDS

attente

Piècereçue

attente

argent choix

x:= valeur(pièce_x)

x := O

attente

Piècereçue

Argent/

Choix/

état

Signal reçu

tâche

statecharts de Harel4) Les automates structurées (statecharts de Harel)

Un macro état peut être composé d'autres états. Quand le système peut être dans chacun des états du macro état, on dit qu'on a une décomposition parallèle. Dans ce cas, on utilise une ligne en pointillé pour séparer les états parallèles.

Sur la figure, le macro état Y est décomposé en deux macro états A et D. A et D sont deux états parallèles. A est lui-même composé de deux états (non parallèles) et D de trois états (non parallèles). Les états initiaux par défaut sont indiqués par une flèche sans origine. La notation "b (in G)" signifie que l'on passe de l'état C à l'état B si arrive l'événement b et si l'état parallèle est dans l'état G.

Automates synchronisés(MSR, Cachan)Les transitions portent des messages de synchronisation (m1, m2, m3, m4).

Une transition peut avoir plusieurs messages, par exemple, a2 a deux messages, m3 et m4.

Un automate peut aller d'un état à un autre (i.e. déplacer son jeton) seulement si il existe une transition entre ces deux états et que tous les messages de synchronisation présents sur cette transition peuvent être émis.

Un message peut être émis si et seulement si tous les automates qui connaissent ce message (i.e. qui ont au moins une transition portant ce message) peuvent utiliser simultanément une transition portant ce message.

Automates synchronisésPar exemple, l'automate A peut aller de l'état Ae1 vers l'état Ae2 si et seulement si les deux messages de synchronisation m1 et m2 peuvent être émis. C'est possible si, par exemple, les automates B et C sont (i.e. ont leur jeton) respectivement dans l'état Ae2, Be2, et Ce2.

D'un autre côté, si A est dans l'état Ae1 tandis que l'automate B est dans l'état Be2, nous sommes dans une situation de deadlock. Utiliser la transition a1 requiert la capacité d'émettre le message m1 ce qui est impossible. En effet, B connaît m1 — porté par b1 — mais n'est pas dans un état où il peut l'émettre. Aussi la transition a1 ne peut-elle être utilisée et à la fois m1 et m2 ne peuvent être émis, ce qui signifie que la transition c1 ne peut être utilisée et que tout l'automate devra rester dans le même état, et donc dans une situation de deadlock.

Les boutons ou la lecture critiqueExtrait de M. Jackson, Software Requirements & Specifications, ACM Press, Addison-Wesley

" When you know what a description is about, and it seems clear enough, you must guard against making assumptions that the writer never intended you to make.These assumptions often stem from the pictures that a word conjures up in your mind. Look at this finite-state machine :

Les boutons ou la lecture critiqueWhich of these inferences would you draw from it ?

(1) In the Stopped state it's impossible to hit the Red Button, and in the Running state it's impossible to hit the Bleu Button.

(2) You can hit the Red Button in the Stopped state, and the Blue Button in the Running state, but it has no effect: it doesn't change the state.

(3) You can hit the Red Button in the Stopped state, and the Blue Button in the Running state, but the effect is unspecified."

Les boutons ou la lecture critique

"Which of these inferences would you draw from it ?

(1) In the Dark state it's impossible to Push Down, and in the Lit state it's impossible to Push Up.

(2) You can Push Down in the Dark state, and Push Up in Lit state, but it has no effect: it doesn't change the state.

(3) You can Push Down in the Dark state, and Push Up in the Lit state, but the effect is unspecified."

Les boutons ou la lecture critique

Voici le commentaire de M. Jackson (nous avons conservé les termes anglais apparaissant sur les dessins) :

" Des noms signifiants font naître des attentes. N ’attendez-vous pas après un événement Push Up, l'évement Push Down ?

Peut-être avez-vous à l'esprit une image d'un levier à deux positions. C'est mon cas. Et vous attendez, qu'après un Hit Red Button vous puissiez facilement faire un nouveau Hit Red Button si vous le désirez.

Les boutons ou la lecture critiquePeut-être vous pensiez à deux boutons indépendants comme ceux d'un clavier d'ordinateur. C'est très raisonnable. Mais ce peut être plutôt erroné. Le levier Push Up/ Push Down peut être doté d'un ressort de sorte qu'il retourne à une position centrale après chaque push, toujours prêt à être pushed soit up soit down. Et les boutons peuvent être situés sur les deux bouts d'une bascule de sorte que vous pouvez seulement alternater les hit.

Lors d'une lecture critique, vous devez toujours être en alerte pour séparer vos attentes raisonnables de ce que les descriptions disent vraiment. "

Réseaux de PetriEn voici un :Les points rouges : jetons ou marques (tokens). Cercles : places. Trait horizontal :une transition.L'affectation de jetons aux places : le marquage.

Le marquage d'un RDP évolue selon la règle suivante :

Une transition est franchissable si chaque place immédiatement en amont a au moins un jeton. Si la transition est franchi, alors on supprime un jeton dans chaque place immédiatement amont et on ajoute un jeton dans chaque place immédiatement aval.

RDPP1 p2

p3

p4

T1

T2

P1

p3

p4

T1

T2

P1

p3

p4

T1

T2

Avant Après si choix deT1

Après si choix deT2

RDPAttention : il n'y a pas forcément conservation du nombre de jetons lors des franchissements. Si, pour un RDP donné, il y a conservation, c'est un invariant du RDP en question.

Ne pas voir le fonctionnement des RDP comme l'évolution d'un flot. L'analogie ne serait pas bonne.

Prenons un réseau avec deux transitions

RDP2 transitions sont franchissables (T1 et T2).

D'après la majorité des auteurs, dans ce cas, une seule transition est franchie à la fois. Laquelle ? Le choix est indéterministe.

Réseau de Petri et AutomateUn marquage est un état d'un automate.Attention ! nous n'avons pas dit : chaque place est un état de l'automate !Le choix entre T1 et T2 est indéterministe.

- on peut annoter les arcs (les flèches) avec un entier. Dans nos exemples, par défaut cette annotation est "1". L'entier indiqué indique, pour les arcs amonts, combien de jetons sont nécessaires dans la place origine de l'arc et pour les arcs avals, combien de jetons sont ajoutésà la place aval en cas de franchissement.

- on peut aussi mettre des temporisations, sur les places, sur les transitions

RDP colorés- on peut aussi avoir des RDP colorés : jetons de couleurs différentes. On peut donc avoir plusieurs entiers par place. La règle de franchissement est toujours la même mais s'applique par couleur.Il faut avoir au moins un jeton de même couleur dans chaque place amont.

AvantAprès

SynchronisationProc1 Proc2

Rendez-vous : « P1 attend P2 »

Proc1 Proc2

Sémaphore : le franchisse-ment de T2 doit se faire aprèscelui de T1

t1

t2

Synchronisation

Réseaux à arc inhibiteur

Producteur tampon Consommateur

RDP- on peut avoir des RDP donc chaque jeton est un n-uplet (un enregistrement)- on peut avoir des RDP à expression booléenne (on dit "à prédicat") i.e. que pour qu'une transition soit franchissable, il faut que cette expression prenne la valeur vrai.