Circuits Logiques, Formes normales et Machines de Turing

Bonjour,

Inscrite en examen terminal, et ne pouvant pas assister aux TD d'informatique, je me permets de vous demander
votre aide pour une bonne compréhension des notions abordées et leur mise en pratique dans les exercices.

Ayant déjà dans le passé étudié quelques unes de ces notions, mes questions portent surtout sur les conventions adoptées dans le cours pour la réalisation des circuits logiques, et l'écriture des formes normales disjonctives.

Comme il m'est difficile de préciser plus, serait-il possible d'obtenir une correction d'un ou plusieurs exercices des feuilles de TD afin de me fournir un exemple de ce qui est attendu? (comme, par exemple, les exercices 2 et 3 de la première ou la seconde feuille sur les circuits logiques).

Je souhaiterais également vous demander quelques explications pour l'écriture de machines de Turing, que je n'ai encore jamais réalisées. Ici encore, je n'ai pas de question bien précise. Aussi, et ici encore, il serait peut-être possible d'obtenir quelques exemples concrets à travers les exercices de la feuille de TD qui y correspond.

Dans tous les cas, je vous remercie par avance pour l'aide que vous m'apporterez,

Cordialement,

c.f.

Bonjour,

Voici la correction (très développée) de l'Exercice 2 de la première feuille d'exercice Calcul binaire et Circuits logiques :

1. Pour trouver FND(p ∞ q) (j'emploie le symbole ∞ à la place de l'autre symbole latex "papillon"), il suffit de comprendre ce que la table de vérité nous dit. Elle nous dit que pour telle valuation (i.e. distribution de valeur de vérité) sur les atomes, la formule prend telle valeur ; la formule sera donc vraie (valeur 1) pour toutes les valuations correspondant aux lignes où la formule prend la valeur 1. FND(p ∞ q) est la disjonction des conjonctions correspondant aux valuations qui rendent vraie la formule. FND(p ∞ q) pourrait donc se traduire comme suit : p ∞ q est vraie lorsque [p est faux et q est faux] ou lorsque [p est faux et q est vraie]. Il suffit donc d'identifier les lignes de la table de vérité où la formule p ∞ q a la valeur 1, puis, pour chacune de ces lignes, considérer les valeurs des atomes p, q :

• si p=1 on écrit p dans la conjonction
  
• si p=0 on écrit ¬p dans la conjonction
  
• idem avec q

Ce qui donne autant de conjonctions qu'il y a de lignes où la formule est vraie. FND(p ∞ q) sera alors la disjonction des conjonctions obtenues :

Chaque formule F à n variables propositionnelles (atomes) étant une fonction de vérité (F: Atomes x ... x Atomes → {0,1}), on observe que la table de vérité de F est une certaine façon d'écrire F, et que FND(F) est une autre façon d'écrire la même fonction, ces deux façons étant tout à fait isomorphes (il existe un isomorphisme évident entre l'ensemble des tables de vérité et l'ensemble des FND). Il en résulte aussi que, quelque soit la formule F, F ↔ FND(F) est une tautologie (formule toujours vraie), i.e. FND(F) est sémantiquement équivalente à F.

2. Les circuits logiques sont aussi une certaine façon d'écrire les fonctions de vérité (les trois "langages" : tables de vérité, FND, circuits logiques, disent la même chose ; passer de l'un à l'autre c'est simplement traduire (ces trois représentations des fonctions logiques sont isomorphes)). Chaque interrupteur sera représenté par un atome nié ou non :

• l'interrupteur p sera ouvert (le courant ne passe pas) si p=0, fermé (le courant passe) si p=1
  
• l'interrupteur ¬p sera ouvert si p=1, fermé si p=0

Avec ces conventions fixées, il suffit, pour construire le circuit logique, de mettre en parallèle les disjonctions et en série les conjonctions ; le circuit d'une FND sera donc une mise en parallèle de circuits en série. FND(p ∞ q) est donc :

On vérifie alors aisément ce "théorème" (trop évident pour être appelé théorème...) :

[Équivalence sémantique Formule/Circuit] Quelque soit F, quelque soit la distribution de valeur de vérité δ : δ(F)=1 ⇔ le courant passe dans CircuitLog(FND(F))

Cordialement,
Aurélien Ohayon

Correction de l'Exercice 3 de la première feuille d'exercice Calcul binaire et Circuits logiques :

1.

2. Cette fonction logique (ou fonction de vérité) est ¬(A∧B), aussi appelée NAND (traduction de NON-ET), qui peut se traduire par : au plus l'un des deux (en effet, ¬(A∧B) est faux uniquement lorsque A et B sont toutes les deux vraies).

3.
Cordialement,
Aurélien Ohayon

Correction (développée) de l'Exercice 3 de la feuille Machines de Turing :

Rappel :

Intuitivement, une MT est un ruban infini des deux côtés, divisé en cases, muni d'une tête de lecture qui peut lire, écrire et effacer, se déplacer d'une seule case à droite et à gauche, en fonction d'un nombre fini d'états qui dictent son comportement.

Formellement, une MT est un triplet (Σ, Q, T) où :

• Σ est un ensemble appelé alphabet (par convention, le métasymbole # qui signifie case vide (ou résultat d'un effacement) appartient à tout Σ)
  
• Q est un ensemble fini de la forme Q={e₀, ..., e_n} appelé ensemble d'états
  
• T est une fonction, appelée fonction de transition, qui "transforme" un état et un symbole de Σ en un autre état (ou le même), un autre symbole (ou le même), et l'indication d'une direction, droite, gauche ou FIN (la machine s'arrête). On adoptera un langage de processus pour noter les transitions (transformations). Chaque transition (e,α) → (e',β,d) peut se lire comme suit :
  
  [Transition (e,α) → (e',β,d)] Si la MT est dans l'état e, qu'elle lit le symbole α, alors elle passe dans l'état e', écrit β à la place de α, puis la tête de lecture-écriture se déplace d'une case vers la droite.
  
  Pour les matheux :
  
  
  T : QxΣ → QxΣx{d,g,FIN}
  (e,α) ↦ (e',β,x)

Par convention, au début de l'exécution de la machine, la tête de lecture sera située sur le premier symbole du mot (le symbole le plus à gauche).

Correction :

Définissons une MT qui multiplie par 2 tout nombre écrit en unaire. On rappelle que la langage unaire est le langage bâtons : Σ={|}. Pour trouver les transitions et le nombre d'états nécessaire à l'exécution de la tâche, commencez par dessiner sur un coin de votre feuille un ruban avec un mot du langage qui sera assez général pour prendre en compte les cas particuliers (ici considérez le nombre 0 comme cas particulier, donc considérez deux cas, le cas général et le cas 0). Sur ce mot, trouvez l'exécution de la MT qui convient de façon globale, générale, c'est-à-dire sans vous préoccuper des états. Ici, cela donne :

Idée générale : A chaque bâton effacé le plus à gauche du mot, on écrit deux bâtons, en les ajoutant aux extrémités des bâtons déjà ajoutés aux étapes précédentes (aucun bâton déjà ajouté au départ) ; ajouter les bâtons aux extrémités de la suite de bâtons déjà ajoutée permettra de conserver un espacement d'une seule case vide entre le reste du mot et la nouvelle suite de bâtons, ce qui nous permettra de savoir quand le mot a été complètement traité (puisque la case située à droite de cette case d'espacement sera vide lorsque le mot sera complètement effacé).

Fonctionnement physique : La tête va effacer le symbole le plus à gauche du mot, se déplacer à gauche (I) ; écrire un bâton (II) ; (traverser la suite de bâtons déjà écrits (suite vide à la première étape)) (III) ; arrivée à la première case vide à la fin de cette suite de bâtons, écrire un nouveau bâton, aller à droite (IV); traverser la suite de bâtons déjà écrits (V) ; arrivée sur la première case vide à droite de la suite de bâtons, laisser cette case vide, aller à droite sur le symbole le plus à gauche du mot RESTANT ; recommencer (i.e. boucler) si le mot restant n'est pas 0 (VI), s'arrêter sinon (VII).

Je rappelle que, lorsqu'on écrit les étapes de la MT, l'introduction d'un nouvel état résulte de l'anticipation du fait qu'à l'étape suivante la MT effectuera une action différente de celle qu'elle vient d'effectuer, différente en genre, en nature, non en nombre : si le Chaplin des Temps modernes était une MT (ce qu'il "est" en réalité...), cette MT ne comporterait qu'un seul état qui boucle sur lui-même : une même action est répétée plusieurs fois ! D'ailleurs Chaplin paie cette répétition qui n'en finit pas...

Maintenant, il faut traduire cela en langage formel, en associant, à chaque type d'action, un état :

(e₀,|) → (e₁,#,g) (I)
(e₁,#) → (e₁,|,g) (II)
(e₂,|) → (e₂,|,g) (III)
(e₂,#) → (e₃,|,d) (IV)
(e₃,|) → (e_3,|,d) (V)
(e₃,#) → (e₀,#,d) (VI)
(e₀,#) → (e₀,#,FIN) (VII)

On vérifie, sur un exemple, que la MT fonctionne bien, en notant, sur des lignes successives en dessous du ruban, les différents états de la machine à chaque pas, et sur des lignes au dessus du ruban, les symboles écrits (ou effacés) à chaque pas.

Cordialement,
Aurélien Ohayon

Monsieur,

Je vous remercie de vos réponses et vos explications claires et détaillées.
A présent, je vais essayer de retravailler tout cela plus précisément,

Cordialement,

c.f.

Monsieur,

Ayant encore un peu de difficultés avec cet exemple de réalisation de Machine de Turing,
je me permets de vous demander s'il serait possible d'avoir un second exemple, peut-être un peu
plus simple, pour que je puisse éclaircir le premier et parvenir à en écrire une correctement par la suite.

En vous remerciant par avance,

Cordialement,

c.f.

[Attention la MT de l'exercice 1 comportait une erreur (trop d'états et une erreur de spécification) que je viens de corriger ! (AO)]
[Attention la MT de l'exercice 2 était incomplète, je viens de la compléter ! (AO)]
[Attention la MT de l'exercice 3 comportait une erreur (trop d'états) que je viens de corriger ! (AO)]

Voici la correction de trois exercices beaucoup plus simples de MT :

1) Face à une suite de bâtons, faire en sorte que la MT ajoute un bâton :
Ʃ = {I}

(e1, I) → (e1, I, d)
(e1, #) → (e1, I, FIN)


2) Soustraire un bâton sur Ʃ = {I} et arrêter la tête de lecture de la MT sur la première case vide située à droite du mot :

(e1, I) → (e2, #, d)
(e1, #) → (e1, #, FIN)
(e2, I) → (e2, I, d)
(e2, #) → (e2, #, FIN)


3) Inverser les 0 et les 1 dans la MT
Ʃ = {0, 1}, MT (01101) = 10010

(e1, 0) → (e1, 1, d)
(e1, 1) → (e1, 0, d)
(e1, #) → (e1, #, FIN)


Etant donné que les explications sur le fonctionnement de la machine ont déjà été faites, est-il nécessaire que je développe des explications sur le fonctionnement de ces exemples ou la réponse "pure" est-elle suffisante ?

Layla Yakoub

Merci Layla. Cependant vos machines comportaient des erreurs que je viens de corriger.

Ces machines sont très simples mais elles permettent bien de comprendre, lorsqu'on n'est pas entraîné à la spécification de MT, le fonctionnement basique d'une MT : transitions, rôle des états. Sauf si la demande en est faite, je crois qu'il n'est pas nécessaire de commenter le "code" de ces petites machines — il se lit de lui-même. D'autres corrections de machines, plus complexes, sont attendues.

Merci beaucoup Layla!

Malgré la précision ajoutée sur "Heuristique : Comment savoir quand je dois ajouter un état/changer d'état ?" , le changement d'état dans une machine de Turing me reste souvent problématique... Aussi je me permets de vous redemander quelques éclaircissements sur celui-ci (je suis désolée...).

En vous remerciant,

Cordialement,

camille Fouché

Camille, ne soyez pas désolée, ce forum est fait pour répondre à toutes vos interrogations.

N. B. : je viens de m'apercevoir, en lisant les MT de Laya, qu'elles comportaient chacune une erreur : les voilà corrigées.

Considérons la spécification suivante :

Soustraire un bâton sur Ʃ = {I} et arrêter la tête de lecture de la MT sur la première case vide située à droite du mot.

(e1, I) → (e2, #, d)
(e1, #) → (e1, #, FIN)
(e2, I) → (e2, I, d)
(e2, #) → (e2, #, FIN)

L'idée de cette petite MT est d'effacer le premier bâton du mot si le mot est différent de 0 (mot vide : #), ne rien faire sinon. Pourquoi la première transition comporte un changement d'état ?


En voici la raison : Lorsque "je suis" (admettons que je suis la MT) dans l'état e1, que je lis le premier bâton du mot (s'il existe), je veux l'effacer, donc j'écris # à la place de I dans le résultat de ma transition, et je me pose la question suivante pour savoir si je reste en e1 ou si je dois changer d'état : à l'étape suivante, si je lis encore un bâton, devrai-je encore l'effacer ? Je sais que non ; donc je ne peux rester en e1, ce qui aurait pour effet de répéter ma transition, donc d'effacer le second bâton, puis le troisième, etc. Or je veux cette fois parcourir le reste du mot, i.e. la suite de bâtons restants, afin de me situer sur la première case vide située à droite du mot : ce sera le rôle de l'état e2 dans lequel, lorsque je verrai un bâton, je le laisserai et irai à droite pour m'arrêter sur la première case vide trouvée :


Je reviendrai sur d'autres exemples plus tard, si besoin est.

AO

Bonjour,

Je vous remercie, cette fois c'est vraiment plus clair ! Enfin je crois... Pour en être sûre, je souhaiterais savoir si l'étape
(e1, #) → (e1, #, FIN), correspond à l'éventualité que le mot soit vide? Et dans ce cas on ne fait rien? Mais cela signifie-t-il alors que
la tête de lecture de la MT est toujours, à l'état initial, placée sur le début du mot?
J'ai vraiment peur de m'embrouiller...

D'autre part, pour ce qui est des conventions, et pour m'en assurer, peut-on noter indifféremment e0 ou e1 l'état initial?

Enfin, serait-il possible d'avoir une exemple avec un alphabet différent et une tâche différente, par exemple la machine de Turing qui reconnait les palindromes sur Ʃ = {a,b}? (même si j'essaie d'y réfléchir...)

En vous remerciant par avance,

Cordialement,

c.f.

Si ça peut aider, voici deux MT supplémentaires, n'hésitez pas à me dire si elles sont fautives et/ou pas lisibles.

Une MT qui efface une lettre sur deux dans un mot :




Une MT qui reconnaît les mot dont le nombre de lettres est pair :

Sinclair,

merci d'avoir posté ces deux MT que l'on a vues en cours. Attention, dans la seconde MT, Ʃ = {a, b, c...}∪{OUI, NON}.

Camille,

en effet, (e1, #) → (e1, #, FIN) correspond à l'éventualité que le mot soit vide. La tête de lecture peut finir n'importe où tant qu'on ne précise pas, dans le sujet, quelque chose d'autre.

Tout à fait, on peut, on devrait même, commencer par l'état e₀, façon plus "propre", plus matheuse de faire, mais cela n'a pas d'importance.

Maintenant, voici une MT qui reconnaît les palindromes sur Ʃ = {a,b} :

On supprime le premier symbole du mot puis on vérifie si le dernier symbole correspond bien au premier ; si oui on le supprime et et on réitère jusqu'à n'avoir plus de symboles, auquel cas on a un palindrome ; sinon on s'arrête et on écrit NON. (J'appelle l'état e_x simplement x, plus rapide.)

(0,a) → (1,#,R) /* J'efface le premier symbole. Si il n'y a plus de symbole, j'ai un palindrome. */
(0,b) → (2,#,R)
(0,#) → (0,OUI,FIN)

(1,a) → (1,a,R) /* J'ai vu un "a" dans l'état 0 ; je vais à la fin du mot, sur le dernier symbole du mot */
(1,b) → (1,b,R)
(1,x) → (3,#,L)

(2,a) → (2,a,R) /* J'ai vu un "b" dans l'état 0 ; je vais à la fin du mot, sur le dernier symbole du mot */
(2,b) → (2,b,R)
(2,x) → (4,#,L)

(3,a) → (5,#,L) /* Je vérifie si ce dernier symbole est "a" */
(3,b) → (3,NON,FIN)

(4,b) → (5,#,L) /* Je vérifie si ce dernier symbole est "b" */
(4,a) → (4,NON,FIN)

(5,a) → (5,a,L) /* Je reviens au début du mot, sur le premier symbole du mot, puis je boucle en 0 */
(5,b) → (5,b,L)
(5,#) → (0,#,R)

Monsieur,

Je vous remercie pour cet exemple et vos explications.

Cordialement,

c.f.

Bonjour,

Toujours à essayer d'écrire enfin correctement et seule une machine de Turing, je me permets de vous demander
votre aide sur un autre exemple.

Je suis en train d'essayer d'écrire la machine de Turing qui " qui reconnaît les mots de
Ʃ= {a, b} de longueur 5".

Mon problème provient du fait qu'il faut compter les lettres (alors que la machine n'additionne pas...). Je me demande alors s'il est nécessaire de multiplier les états?... (J'ai peur d'être encore loin d'une correcte réalisation...).

Accepteriez-vous de me mettre sur la voie avec une indication pour cette MT?

En vous remerciant par avance,

Cordialement,

c.f

Mademoiselle,

Votre intuition est bonne : il faut en effet multiplier les états, de sorte que chaque état e_x (0≤x≤4) indique le fait que le reste de la division par 5 du nombre de symboles déjà parcourus (i.e. qui précèdent la position de la tête de lecture) est x. Autrement dit que :

avec : s le symbole qu'elle lit lorsqu'elle est dans cet état, lg la longueur, mot_s le segment initial (du mot) dont la dernière lettre est s.

Je vous laisse finir... Postez votre version et je la corrigerai si besoin est.

* i.e. que lg(mot_s) ∈ [x] où [x] ∈ ℤ/5ℤ.

AO

Sinclair,

Pourriez-vous s'il vous plaît nous copier-coller vos notes de cours sur les organigrammes dans le sujet consacré ? Je vous le demande car je sais la qualité de vos prises de notes.

En vous remerciant d'avance,
AO

Monsieur,

Avec vos indications, j'ai essayé de poursuivre et je me permets de vous soumettre une première ébauche... Mais je ne suis pas vraiment satisfaite, car j'ai l'impression que ma machine peut bien reconnaître si un mot est de longueur 5, mais je ne pense pas qu'elle fonctionne dans tous les cas (je continue d'y réfléchir)...

MT qui reconnait les mots de Ʃ= {a, b} de longueur 5.

Ʃ = {a,b}U{OUI,NON}

x ∈ Ʃ - {#}

(e0, x) -> (e1,x,R)
(e0,#) -> (e0, OUI, FIN)

(e1,x) -> (e2,x,R)
(e1,#) -> (e1, NON, FIN)

(e2,x) -> (e3,x,R)
(e2,#) -> (e2, NON, FIN)

(e3,x) -> (e4,x,R)
(e3,#) -> (e3, NON, FIN)

(e4,x) -> (e0,x,R)
(e4,#) -> (e4, NON, FIN)

D'autre part, je me permets, à la vieille de l'examen..., de vous redemander s'il serait possible d'avoir des précisions supplémentaires sur Organigrammes et programmation.

En vous remerciant,

Cordialement,

c.f.

Mademoiselle,

Vous avez bien compris le fonctionnement des MT : votre machine est la bonne et elle fonctionne bien dans tous les cas.

Concernant les organigrammes, et puisque aucun étudiant n'a pris le temps de copier-coller ses notes, je vais vous mettre en lien le document qui m'a servi de base pour mon cours ; nous avons abordé les exemples 1, 2, 3, 4 et 7. La compréhension de ces seuls exemples vous suffiront à réaliser l'exercice de l'examen final.

AO

Monsieur,

Je vous remercie, ainsi que pour les liens ajoutés des documents concernant les Organigrammes de programmation.

Cordialement,

c.f.