{"id":1917,"date":"2024-04-04T14:39:38","date_gmt":"2024-04-04T12:39:38","guid":{"rendered":"https:\/\/actilud.com\/info\/?p=1917"},"modified":"2025-04-02T14:36:39","modified_gmt":"2025-04-02T12:36:39","slug":"la-machine-de-turing-defis-dinitiation","status":"publish","type":"post","link":"https:\/\/actilud.com\/info\/blog\/la-machine-de-turing-defis-dinitiation\/","title":{"rendered":"La machine de Turing : d\u00e9fis d&rsquo;initiation"},"content":{"rendered":"<h1>Le meilleur des mondes<\/h1>\n<p>Il s&rsquo;agit de rendre les gens heureux. Uniform\u00e9ment.<\/p>\n<p>Voici la situation de d\u00e9part et celle d&rsquo;arriv\u00e9e :<\/p>\n<p><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1832 aligncenter\" src=\"https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/03\/turing_meilleur_monde.png\" alt=\"\" width=\"547\" height=\"198\" srcset=\"https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/03\/turing_meilleur_monde.png 724w, https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/03\/turing_meilleur_monde-300x109.png 300w, https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/03\/turing_meilleur_monde-720x261.png 720w\" sizes=\"auto, (min-width: 960px) 75vw, 100vw\" \/><\/p>\n<p>Ici pas de difficult\u00e9: un seul \u00e9tat suffit.<\/p>\n<p>Voici une vid\u00e9o qui donne une solution possible et explique comment la programmer. Notre programme transforme toutes les \u00e9moticones tristes ou en col\u00e8re en \u00e9motic\u00f4nes souriantes, en \u00e9pargnant celles qui sont d\u00e9j\u00e0 de bonne humeur. Tous les signes sont affect\u00e9s. Le programme s&rsquo;arr\u00eate au premier blanc rencontr\u00e9. Il fait appel au signe <span id=\"symbol\" class=\"symbol large\">\u2200<\/span> <em>(pour tout)<\/em>.<\/p>\n<p style=\"text-align: center;\"><iframe loading=\"lazy\" src=\"https:\/\/drive.google.com\/file\/d\/1-aClTk56DXUWM7XBzlQmVPZrFWI8V2bC\/preview\" width=\"640\" height=\"360\" allowfullscreen=\"allowfullscreen\"><span style=\"display: inline-block; width: 0px; overflow: hidden; line-height: 0;\" data-mce-type=\"bookmark\" class=\"mce_SELRES_start\">\ufeff<\/span><\/iframe><\/p>\n<p>&nbsp;<\/p>\n<h1>Un d\u00e9tecteur de chiffre pair \/ impair<\/h1>\n<p>Soit un <em>chiffre<\/em> plac\u00e9 dans une case. La t\u00eate de lecture est positionn\u00e9e sur ce chiffre. Si le chiffre est pair, la machine doit s&rsquo;arr\u00eater dans l&rsquo;\u00e9tat \u00ab\u00a0pair\u00a0\u00bb. Si le chiffre est impair, la machine doit s&rsquo;arr\u00eater dans l&rsquo;\u00e9tat \u00ab\u00a0impair\u00a0\u00bb. La t\u00eate ne doit pas se d\u00e9placer.<\/p>\n<p>La collection est C={[0-9]} (les chiffres de 0 \u00e0 9). Aucune difficult\u00e9 particuli\u00e8re pour ce d\u00e9fi, il n&rsquo;y a qu&rsquo;un seul \u00e9tat \u00e0 d\u00e9finir. Les \u00e9tats \u00ab\u00a0pair\u00a0\u00bb et \u00ab\u00a0impair\u00a0\u00bb sont ind\u00e9finis, c&rsquo;est \u00e0 dire qu&rsquo;ils doivent figurer dans les instructions mais ne doivent pas \u00eatre programm\u00e9s. Ceci produit l&rsquo;arr\u00eat de la machine.<\/p>\n<p>Voici la solution :<\/p>\n<blockquote><p>Machine\u00a0: [D\u00e9tecteurPairImpair]<br \/>\n# D\u00e9tecte si un chiffre est pair ou impair. Ne d\u00e9place pas la t\u00eate.<br \/>\n\u00c9tat\u00a0: q0<br \/>\nq0, 0 , 0 , pair<br \/>\nq0, 2 , 2 , pair<br \/>\nq0, 4 , 4 , pair<br \/>\nq0, 6 , 6 , pair<br \/>\nq0, 8 , 8 , pair<br \/>\nq0, 1 , 1 , impair<br \/>\nq0, 3 , 3 , impair<br \/>\nq0, 5 , 5 , impair<br \/>\nq0, 7 , 7 , impair<br \/>\nq0, 9 , 9 , impair<\/p><\/blockquote>\n<h6>Remarquez dans ce listage, que lorsque la t\u00eate ne se d\u00e9place pas, il n&rsquo;y a pas d&rsquo;instruction de d\u00e9placement \u2192 ou \u2190.<\/h6>\n<h1>Le d\u00e9compteur d&rsquo;unit\u00e9s<\/h1>\n<p>Voici un d\u00e9fi amusant et facile \u00e0 r\u00e9aliser. On pose le chiffre 9 sur la bande et on positionne la t\u00eate sur le 9. La machine doit d\u00e9cr\u00e9menter le chiffre, afficher le r\u00e9sultat, et recommencer jusqu&rsquo;\u00e0 ce que le chiffre soit 0. L\u00e0, elle doit l&rsquo;effacer et s&rsquo;arr\u00eater. Bien s\u00fbr, le programme n&rsquo;a d&rsquo;int\u00e9r\u00eat qu&rsquo;en mode pas \u00e0 pas, marche ou course. Sur la bande, on doit voir successivement, dans la m\u00eame case, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0, \u2610. On peut, bien s\u00fbr, d\u00e9marrer \u00e0 partir de n&rsquo;importe quel autre chiffre.<\/p>\n<p>Aucune difficult\u00e9 de r\u00e9alisation; on ne d\u00e9place m\u00eame pas la t\u00eate. C&rsquo;est un premier pas vers une machine plus complexe, qui peut d\u00e9cr\u00e9menter n&rsquo;importe quel entier naturel. La collection est C={[0-9], \u2610\u00a0 }<\/p>\n<blockquote><p>Machine\u00a0: [D\u00e9cr\u00e9menteUnit\u00e9]<br \/>\n# D\u00e9cr\u00e9mente un chiffre jusqu&rsquo;\u00e0 ce qu&rsquo;il disparaisse.<br \/>\n# D\u00e9but : sur le chiffre<br \/>\n# Fin : sur le blanc qui remplace le chiffre<\/p>\n<p>\u00c9tat\u00a0: q0<br \/>\nq0, 9 , 8 , q0<br \/>\nq0, 8 , 7 , q0<br \/>\nq0, 7 , 6 , q0<br \/>\nq0, 6 , 5 , q0<br \/>\nq0, 5 , 4 , q0<br \/>\nq0, 4 , 3 , q0<br \/>\nq0, 3 , 2 , q0<br \/>\nq0, 2 , 1 , q0<br \/>\nq0, 1 , 0 , q0<br \/>\nq0, 0 , \u2610 , q0<\/p><\/blockquote>\n<h1>La machine \u00e0 encodage irr\u00e9versible<\/h1>\n<p>Soit la collection C={[A-Z], \u2610 , . }<\/p>\n<p>On \u00e9crit sur la bande une phrase avec les lettres majuscules. Comme dans les mots crois\u00e9s, on ignore les accents.\u00a0 On s\u00e9pare les mots par des blancs. On termine la phrase par un point.<\/p>\n<blockquote><p>Exemple: LA MACHINE DE TURING C EST GENIAL.<\/p><\/blockquote>\n<p>La t\u00eate est positionn\u00e9e sur la premi\u00e8re lettre de la phrase. Elle doit s&rsquo;arr\u00eater sur le point.<\/p>\n<p>\u00c9crire un programme qui transforme chaque lettre et le blanc, en une autre lettre ou un blanc. C&rsquo;est le syst\u00e8me classique par transposition; on \u00e9change 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 \u00e0 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.<\/p>\n<p>La machine doit \u00eatre \u00e0 encodage irr\u00e9versible: si on la fait fonctionner sur un texte d\u00e9j\u00e0 encod\u00e9, le texte doit \u00eatre sur-encod\u00e9 mais pas ramen\u00e9 \u00e0 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\u00e9rer quelques exceptions, mais pas trop.<\/p>\n<p>Ici, le programme est fastidieux car il y a 26 lettres, mais facile \u00e0 \u00e9crire; il ne demande qu&rsquo;un seul \u00e9tat. L&rsquo;int\u00e9r\u00eat r\u00e9side surtout dans l&rsquo;organisation du travail. Comment les \u00e9l\u00e8ves vont-ils proc\u00e9der pour encoder sans se tromper ? Il faut mettre en place une proc\u00e9dure de r\u00e9partition des lettres et surtout ne pas se jeter dans la programmation sans pr\u00e9paration.<\/p>\n<h1>La machine \u00e0 d\u00e9codage<\/h1>\n<p>C&rsquo;est le corollaire de la pr\u00e9c\u00e9dente machine ! R\u00e9aliser une machine qui permet de d\u00e9coder un message \u00e9crit par la pr\u00e9c\u00e9dente.<\/p>\n<p>Comme l&rsquo;interface d&rsquo;Actilud est assez ergonomique, les \u00e9l\u00e8ves peuvent r\u00e9utiliser l&rsquo;ancienne machine apr\u00e8s l&rsquo;avoir sauvegard\u00e9e, et, dans l&rsquo;\u00e9diteur d&rsquo;instructions, cliquer sur l&rsquo;ic\u00f4ne de permutation pour chaque lettre.<\/p>\n<figure id=\"attachment_1993\" aria-describedby=\"caption-attachment-1993\" style=\"width: 379px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" class=\"wp-image-1993 size-full\" src=\"https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/04\/turing_echange-1.png\" alt=\"\" width=\"379\" height=\"180\" srcset=\"https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/04\/turing_echange-1.png 379w, https:\/\/actilud.com\/info\/wp-content\/uploads\/2024\/04\/turing_echange-1-300x142.png 300w\" sizes=\"auto, (min-width: 960px) 75vw, 100vw\" \/><figcaption id=\"caption-attachment-1993\" class=\"wp-caption-text\">Apr\u00e8s avoir \u00e9dit\u00e9 une instruction, on peut permuter les lettres A et T, puis on valide.<\/figcaption><\/figure>\n<p>Apr\u00e8s avoir r\u00e9alis\u00e9 les deux machines, on peut expliquer le fonctionnement du\u00a0<em>cryptage asym\u00e9trique.<\/em>\u00a0Imaginons deux personnes, Alice et Bob, qui d\u00e9cident de correspondre de mani\u00e8re crypt\u00e9e \u00e0 l&rsquo;aide de la machine de Turing. Alice va r\u00e9aliser deux machines , une pour coder, une autre pour d\u00e9coder. Bob va faire de m\u00eame. Lorsqu&rsquo;ils se rencontrent, Alice donne \u00e0 Bob sa machine \u00e0 encoder, et Bob donne la sienne \u00e0 Alice. Puis ils se s\u00e9parent. Ainsi, Alice et Bob peuvent d\u00e9sormais crypter leurs messages avec la machine de leur correspondant. Pour d\u00e9crypter les messages re\u00e7us, ils doivent utiliser leur machine \u00e0 d\u00e9coder personnelle, qu&rsquo;ils rangent soigneusement dans un coffre. Il faut donc en tout, 4 machines pour assurer la communication, deux machines par correspondant.<\/p>\n<p>Le cryptage asym\u00e9trique est \u00e0 la base du protocole TLS utilis\u00e9 dans les \u00e9changes entre un navigateur et un site web via HTTPS. Le navigateur initie la communication avec le serveur du site web. Ce dernier lui r\u00e9pond en envoyant sa cl\u00e9 publique. Le navigateur envoie alors des informations de codage, qu&rsquo;il crypte avec la cl\u00e9 publique re\u00e7ue. Le serveur re\u00e7oit les informations, les d\u00e9code avec sa cl\u00e9 priv\u00e9e. Ceci permet aux deux correspondants de mettre en place un syst\u00e8me d&rsquo;\u00e9changes sym\u00e9triques, uniquement valable entre les deux protagonistes pendant la dur\u00e9e de la session.<\/p>\n<h1>La machine \u00e0 codage r\u00e9versible (sym\u00e9trique)<\/h1>\n<p>Cette fois, lorsque la machine a cod\u00e9 un texte, un second passage doit ramener le texte originel. C&rsquo;est le principe du cryptage r\u00e9versible (ou cryptage sym\u00e9trique). L\u00e0 encore, tout r\u00e9side dans l&rsquo;organisation du travail : comment proc\u00e9der pour que cela marche ? La phase de conception est fondamentale.<\/p>\n<p>Pour r\u00e9aliser 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\u00eame \u00e9tat.<\/p>\n<h1>Un d\u00e9tecteur de nombre pair \/ impair<\/h1>\n<p>Soit un <em>nombre<\/em> entier naturel \u00e9crit sur la bande, \u00e0 raison d&rsquo;un chiffre par case. Les chiffres se suivent.<\/p>\n<p>On commence quelque part \u00e0 l&rsquo;int\u00e9rieur du nombre. Si le nombre est pair, la machine doit s&rsquo;arr\u00eater sur le dernier chiffre dans l&rsquo;\u00e9tat \u00ab\u00a0pair\u00a0\u00bb. Si le nombre est impair, la machine doit s&rsquo;arr\u00eater sur le dernier chiffre dans l&rsquo;\u00e9tat \u00ab\u00a0impair\u00a0\u00bb.<\/p>\n<p>La collection sera C={[0-9],\u2610} (les chiffres de 0 \u00e0 9 et le blanc).<\/p>\n<p>Pour r\u00e9aliser ce d\u00e9fi, la machine doit d&rsquo;abord parcourir les chiffres vers la droite jusqu&rsquo;au dernier. Pour le trouver, elle doit\u00a0 parcourir la bande et passer les chiffres jusqu&rsquo;\u00e0 ce qu&rsquo;elle arrive sur le premier blanc. L\u00e0 elle recule d&rsquo;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&rsquo;\u00e9tat \u00ab\u00a0pair\u00a0\u00bb; cet \u00e9tat ne sera pas d\u00e9fini et donc la machine s&rsquo;arr\u00eate. Pour les autres chiffres la machine entre en l&rsquo;\u00e9tat \u00ab\u00a0impair\u00a0\u00bb, qui lui aussi n&rsquo;est pas d\u00e9fini et provoque donc un arr\u00eat.<\/p>\n<p>Pour r\u00e9aliser le d\u00e9fi, il faut utiliser deux \u00e9tats.<\/p>\n<p>La solution :<\/p>\n<blockquote><p>Machine : [D\u00e9tecteurNombrePairImpair]<br \/>\n# D\u00e9tecte si un nombre est pair ou impair. Se termine sur le dernier chiffre.<br \/>\n\u00c9tat : parcours<br \/>\nparcours, 0 , 0 , \u2192 , parcours<br \/>\nparcours, 1 , 1 , \u2192 , parcours<br \/>\nparcours, 2 , 2 , \u2192 , parcours<br \/>\nparcours, 3 , 3 , \u2192 , parcours<br \/>\nparcours, 4 , 4 , \u2192 , parcours<br \/>\nparcours, 5 , 5 , \u2192 , parcours<br \/>\nparcours, 6 , 6 , \u2192 , parcours<br \/>\nparcours, 7 , 7 , \u2192 , parcours<br \/>\nparcours, 8 , 8 , \u2192 , parcours<br \/>\nparcours, 9 , 9 , \u2192 , parcours<br \/>\nparcours, \u2610 , \u2610 , \u2190 , d\u00e9tection<br \/>\n\u00c9tat : d\u00e9tection<br \/>\nd\u00e9tection, 0 , 0 , pair<br \/>\nd\u00e9tection, 2 , 2 , pair<br \/>\nd\u00e9tection, 4 , 4 , pair<br \/>\nd\u00e9tection, 6 , 6 , pair<br \/>\nd\u00e9tection, 8 , 8 , pair<br \/>\nd\u00e9tection, 1 , 1 , impair<br \/>\nd\u00e9tection, 3 , 3 , impair<br \/>\nd\u00e9tection, 5 , 5 , impair<br \/>\nd\u00e9tection, 7 , 7 , impair<br \/>\nd\u00e9tection, 9 , 9 , impair<\/p><\/blockquote>\n<h1>La chenille : un d\u00e9fi \u00e0 trois \u00e9tats<\/h1>\n<p>Ce d\u00e9fi est int\u00e9ressant en mode pas \u00e0 pas, marche ou course.<\/p>\n<p>Soit une chenille form\u00e9e par plusieurs lettres O qui se suivent. Un peu plus loin sur la droite, apr\u00e8s quelques cases blanches, il y a une app\u00e9tissante lettre X. La chenille doit se d\u00e9placer jusqu&rsquo;\u00e0 la lettre X et la manger. Bien s\u00fbr, la chenille rampe : il ne faut pas s\u00e9parer les lettres O ! L&rsquo;id\u00e9e est de la d\u00e9placer en retirant le O de l&rsquo;extr\u00e9mit\u00e9 gauche pour le placer \u00e0 l&rsquo;extr\u00e9mit\u00e9 droite, et de reproduire ce traitement jusqu&rsquo;\u00e0 l&rsquo;arriv\u00e9e. Ainsi, la chenille se raccourcit et s&rsquo;\u00e9tire pour se d\u00e9placer. Au d\u00e9part, la t\u00eate est positionn\u00e9e sur le O le plus \u00e0 gauche. On termine sur la lettre O \u00e0 droite, qui doit remplacer le X. La collection est C={ O, X, \u2610 }<\/p>\n<blockquote><p>On commence par supprimer le O le plus \u00e0 gauche, puis on parcourt la liste des O vers la droite jusqu&rsquo;au bout. S&rsquo;il y a un blanc, on place un O, on recule au d\u00e9but de la chenille et on recommence le traitement. S&rsquo;il y a un X, on place le O et on s&rsquo;arr\u00eate.<\/p>\n<p>Il faut donc: un \u00e9tat pour supprimer le O le plus \u00e0 gauche; un \u00e9tat pour placer le O; un \u00e9tat pour reculer.<\/p><\/blockquote>\n","protected":false},"excerpt":{"rendered":"<p>Le meilleur des mondes Il s&rsquo;agit de rendre les gens heureux. Uniform\u00e9ment. Voici la situation de d\u00e9part et celle d&rsquo;arriv\u00e9e : Ici pas de difficult\u00e9: un seul \u00e9tat suffit. Voici une vid\u00e9o qui donne une solution possible et explique comment la programmer. Notre programme transforme toutes les \u00e9moticones tristes ou en col\u00e8re en \u00e9motic\u00f4nes souriantes, [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[15],"tags":[],"class_list":["post-1917","post","type-post","status-publish","format-standard","hentry","category-machine-de-turing-les-defis"],"_links":{"self":[{"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/posts\/1917","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/comments?post=1917"}],"version-history":[{"count":32,"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/posts\/1917\/revisions"}],"predecessor-version":[{"id":1989,"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/posts\/1917\/revisions\/1989"}],"wp:attachment":[{"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/media?parent=1917"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/categories?post=1917"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/actilud.com\/info\/wp-json\/wp\/v2\/tags?post=1917"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}