par Le meilleur des mondes
Il s’agit de rendre les gens heureux. Uniformément.
Voici la situation de départ et celle d’arrivée :
Ici pas de difficulté: un seul état suffit. On mettra dans la collection uniquement les émoticônes manifestant des émotions dites “négatives”, le blanc et l’émoticône souriant.
Un détecteur de chiffre pair / impair
Soit un chiffre placé dans une case. La tête de lecture est positionnée sur ce chiffre. Si le chiffre est pair, la machine doit s’arrêter dans l’état “pair”. Si le chiffre est impair, la machine doit s’arrêter dans l’état “impair”. La tête ne doit pas se déplacer.
La collection est C={[0-9]} (les chiffres de 0 à 9). Aucune difficulté particulière pour ce défi, il n’y a qu’un seul état à définir. Les états “pair” et “impair” sont indéfinis, c’est à dire qu’ils doivent figurer dans les instructions mais ne doivent pas être programmés. Ceci produit l’arrêt de la machine.
Voici la solution :
Machine : [DétecteurPairImpair]
# Détecte si un chiffre est pair ou impair. Ne déplace pas la tête.
État : q0
q0, 0 , 0 , pair
q0, 2 , 2 , pair
q0, 4 , 4 , pair
q0, 6 , 6 , pair
q0, 8 , 8 , pair
q0, 1 , 1 , impair
q0, 3 , 3 , impair
q0, 5 , 5 , impair
q0, 7 , 7 , impair
q0, 9 , 9 , impair
Remarquez dans ce listage, que lorsque la tête ne se déplace pas, il n’y a pas d’instruction de déplacement → ou ←.
Le décompteur d’unités
Voici un défi amusant et facile à réaliser. On pose le chiffre 9 sur la bande et on positionne la tête sur le 9. La machine doit décrémenter le chiffre, afficher le résultat, et recommencer jusqu’à ce que le chiffre soit 0. Là, elle doit l’effacer et s’arrêter. Bien sûr, le programme n’a d’intérêt qu’en mode pas à pas, marche ou course. Sur la bande, on doit voir successivement, dans la même case, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, ☐. On peut, bien sûr, démarrer à partir de n’importe quel autre chiffre.
Aucune difficulté de réalisation; on ne déplace même pas la tête. C’est un premier pas vers une machine plus complexe, qui peut décrémenter n’importe quel entier naturel. La collection est C={[0-9], ☐ }
Machine : [DécrémenteUnité]
# Décrémente un chiffre jusqu’à ce qu’il disparaisse.
# Début : sur le chiffre
# Fin : sur le blanc qui remplace le chiffreÉtat : q0
q0, 9 , 8 , q0
q0, 8 , 7 , q0
q0, 7 , 6 , q0
q0, 6 , 5 , q0
q0, 5 , 4 , q0
q0, 4 , 3 , q0
q0, 3 , 2 , q0
q0, 2 , 1 , q0
q0, 1 , 0 , q0
q0, 0 , ☐ , q0
La machine à encodage irréversible
Soit la collection C={[A-Z], ☐ , . }
On écrit sur la bande une phrase avec les lettres majuscules. Comme dans les mots croisés, on ignore les accents. On sépare les mots par des blancs. On termine la phrase par un point.
Exemple: LA MACHINE DE TURING C EST GENIAL.
La tête est positionnée sur la première lettre de la phrase. Elle doit s’arrêter sur le point.
Écrire un programme qui transforme chaque lettre et le blanc, en une autre lettre ou un blanc. C’est le système classique par transposition; on échange une lettre avec une autre. Par exemple, le A devient le T, le B devient le R, etc. Chaque signe lu doit avoir un correspondant. Chaque correspondant doit correspondre à un, et un seul, signe. Ainsi, si je traduis le A par un T, je ne peux plus traduire une autre lettre par le T. Ne pas oublier de traduire le blanc.
La machine doit être à encodage irréversible: si on la fait fonctionner sur un texte déjà encodé, le texte doit être sur-encodé mais pas ramené à sa version originelle. Cela veut dire que si je code le A par un T, il ne faut pas que le T se transforme en A. On peut tolérer quelques exceptions, mais pas trop.
Ici, le programme est fastidieux car il y a 26 lettres, mais facile à écrire; il ne demande qu’un seul état. L’intérêt réside surtout dans l’organisation du travail. Comment les élèves vont-ils procéder pour encoder sans se tromper ? Il faut mettre en place une procédure de répartition des lettres et surtout ne pas se jeter dans la programmation sans préparation.
La machine à décodage
C’est le corollaire de la précédente machine ! Réaliser une machine qui permet de décoder un message écrit par la précédente.
Comme l’interface d’Actilud est assez ergonomique, les élèves peuvent réutiliser l’ancienne machine après l’avoir sauvegardée, et, dans l’éditeur d’instructions, cliquer sur l’icône de permutation pour chaque lettre.
Après avoir réalisé les deux machines, on peut expliquer quelques éléments de cryptographie. Imaginons deux personnes, Alice et Bob, qui décident de correspondre de manière cryptée à l’aide de la machine de Turing. Alice va réaliser deux machines , une pour coder, une autre pour décoder. Bob va faire de même. Lorsqu’ils se rencontrent, Alice donne à Bob sa machine à encoder, et Bob donne la sienne à Alice. Puis ils se séparent. Ainsi, Alice et Bob peuvent désormais crypter leurs messages avec la machine de leur correspondant. Pour décrypter les messages reçus, ils doivent utiliser leur machine à décoder personnelle, qu’ils rangent soigneusement dans un coffre. Il faut donc en tout, 4 machines pour assurer la communication, deux machines par correspondant.
Malencontreusement, Bob laisse traîner la machine à encoder d’Alice sur son bureau et une pirate en herbe, Carole, qui passait par là, en fait une copie. Avec cette machine copiée, Carole peut donc se faire passer pour Bob, mais elle ne peut pas décoder la réponse d’Alice (Comme beaucoup de pirates en herbe, Carole est juste capable de lancer un script écrit par d’autres, mais elle ne le comprend pas.)
Appelez la machine à coder “clé publique” et la machine à décoder “clé privée” et vous aurez une illustration de ce qu’il se passe avec le protocole https sur Internet.
Lorsqu’un navigateur communique avec un site en https, le site lui envoie une “clé publique” (la machine à encoder) avec laquelle le navigateur va encoder ses messages avant de les envoyer au site. Le site va décoder le message reçu avec sa clé privée (la machine à décoder) et pourra ainsi répondre à la requête. Le processus est le même si on se place du point de vue du site : le site reçoit du navigateur une clé publique (une deuxième machine à encoder) et va encoder sa réponse, que le navigateur va décoder avec sa clé privée (une deuxième machine à décoder).
Évidemment, le cryptage employé sur le web n’a rien à voir avec celui de nos machines. Si on possède la machine à encoder, il n’y a aucune difficulté à trouver la machine à décoder, comme on vient de le faire. Ce n’est pas le cas, bien sûr, avec l’échange des clés publiques. Une clé publique ne permet pas de reconstituer une clé privée.
La machine à codage réversible
Cette fois, lorsque la machine a codé un texte, un second passage doit ramener le texte originel. C’est le principe du cryptage réversible. Là encore, tout réside dans l’organisation du travail : comment procéder pour que cela marche ? La phase de conception est fondamentale.
Pour réaliser ceci, il faut grouper les lettres par paires. Nous avons 26 lettres et un blanc, ce qui fait 13 paires et un signe qui ne sera pas traduit. Ici, si je traduis le A par un T, il faut que le T soit traduit par un A dans le même état.
Un détecteur de nombre pair / impair
Soit un nombre entier naturel écrit sur la bande, à raison d’un chiffre par case. Les chiffres se suivent.
On commence quelque part à l’intérieur du nombre. Si le nombre est pair, la machine doit s’arrêter sur le dernier chiffre dans l’état “pair”. Si le nombre est impair, la machine doit s’arrêter sur le dernier chiffre dans l’état “impair”.
La collection sera C={[0-9],☐} (les chiffres de 0 à 9 et le blanc).
Pour réaliser ce défi, la machine doit d’abord parcourir les chiffres vers la droite jusqu’au dernier. Pour le trouver, elle doit parcourir la bande et passer les chiffres jusqu’à ce qu’elle arrive sur le premier blanc. Là elle recule d’une case vers la gauche. Elle se retrouve alors sur le dernier chiffre. Si ce chiffre est 0, 2, 4, 6 ou 8, la machine entre dans l’état “pair”; cet état ne sera pas défini et donc la machine s’arrête. Pour les autres chiffres la machine entre en l’état “impair”, qui lui aussi n’est pas défini et provoque donc un arrêt.
Pour réaliser le défi, il faut utiliser deux états.
La solution :
Machine : [DétecteurNombrePairImpair]
# Détecte si un nombre est pair ou impair. Se termine sur le dernier chiffre.
État : parcours
parcours, 0 , 0 , → , parcours
parcours, 1 , 1 , → , parcours
parcours, 2 , 2 , → , parcours
parcours, 3 , 3 , → , parcours
parcours, 4 , 4 , → , parcours
parcours, 5 , 5 , → , parcours
parcours, 6 , 6 , → , parcours
parcours, 7 , 7 , → , parcours
parcours, 8 , 8 , → , parcours
parcours, 9 , 9 , → , parcours
parcours, ☐ , ☐ , ← , détection
État : détection
détection, 0 , 0 , pair
détection, 2 , 2 , pair
détection, 4 , 4 , pair
détection, 6 , 6 , pair
détection, 8 , 8 , pair
détection, 1 , 1 , impair
détection, 3 , 3 , impair
détection, 5 , 5 , impair
détection, 7 , 7 , impair
détection, 9 , 9 , impair
La chenille : un défi à trois états
Ce défi est intéressant en mode pas à pas, marche ou course.
Soit une chenille formée par plusieurs lettres O qui se suivent. Un peu plus loin sur la droite, après quelques cases blanches, il y a une appétissante lettre X. La chenille doit se déplacer jusqu’à la lettre X et la manger. Bien sûr, la chenille rampe : il ne faut pas séparer les lettres O ! L’idée est de la déplacer en retirant le O de l’extrémité gauche pour le placer à l’extrémité droite, et de reproduire ce traitement jusqu’à l’arrivée. Ainsi, la chenille se raccourcit et s’étire pour se déplacer. Au départ, la tête est positionnée sur le O le plus à gauche. On termine sur la lettre O à droite, qui doit remplacer le X. La collection est C={ O, X, ☐ }
On commence par supprimer le O le plus à gauche, puis on parcourt la liste des O vers la droite jusqu’au bout. S’il y a un blanc, on place un O, on recule au début de la chenille et on recommence le traitement. S’il y a un X, on place le O et on s’arrête.
Il faut donc: un état pour supprimer le O le plus à gauche; un état pour placer le O; un état pour reculer.