{"id":687,"date":"2016-10-15T21:14:00","date_gmt":"2016-10-15T17:14:00","guid":{"rendered":"https:\/\/iremi.univ-reunion.fr\/?p=687"},"modified":"2025-06-27T18:44:00","modified_gmt":"2025-06-27T14:44:00","slug":"fractran","status":"publish","type":"post","link":"https:\/\/iremi.univ-reunion.fr\/?p=687","title":{"rendered":"Fractran"},"content":{"rendered":"\n<p>Fractran est un langage de programmation Turing-complet, ainsi que le prouve son cr\u00e9ateur :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/Fractran_by_Conway3.pdf\" type=\"application\/pdf\" style=\"width:100%;height:270px\" aria-label=\"Contenu embarqu\u00e9 Fractran_by_Conway3.\"><\/object><a id=\"wp-block-file--media-6765acd7-a8fb-4918-928b-9fac882825b1\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/Fractran_by_Conway3.pdf\">Fractran_by_Conway3<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/Fractran_by_Conway3.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-6765acd7-a8fb-4918-928b-9fac882825b1\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>L&rsquo;int\u00e9r\u00eat essentiel de Fractran est qu&rsquo;il est bas\u00e9 sur les fractions. Ce langage permet donc de faire travailler \u00e0 la fois <\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>les algorithmes<\/li>\n\n\n\n<li>le calcul sur les fractions<\/li>\n\n\n\n<li>la d\u00e9composition en facteurs premiers<\/li>\n<\/ul>\n\n\n\n<p><\/p>\n\n\n\n<p>Voici <a href=\"https:\/\/scratch.mit.edu\/projects\/135874298\/fullscreen\/\">un exemple<\/a> de programme Fractran, pour voir le principe. Et <a href=\"https:\/\/scratch.mit.edu\/projects\/135671803\/fullscreen\/\">un programme de multiplication<\/a> en Fractran (bas\u00e9 sur la d\u00e9composition en facteurs premiers).<\/p>\n\n\n\n<p>Voici maintenant un interpr\u00e9teur Fractran en Sofus :<\/p>\n\n\n\n<figure class=\"wp-block-image size-full\"><img loading=\"lazy\" decoding=\"async\" width=\"422\" height=\"416\" src=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/fractransofus.png\" alt=\"\" class=\"wp-image-696\" srcset=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/fractransofus.png 422w, https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/fractransofus-300x296.png 300w\" sizes=\"auto, (max-width: 422px) 100vw, 422px\" \/><\/figure>\n\n\n\n<p>et en Python :<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>from fractions import *\n\nprogramme = &#091;Fraction(1,2),Fraction(2,3),Fraction(3,4),Fraction(4,5)]\n\ndef estEntier(fraction):\n\treturn fraction.denominator == 1\n\n\ndef fonction(n):\n    position = 0\n    nombre = n\t\n    while position&lt;len(programme):\n        if estEntier(nombre*programme&#091;position]):\n            nombre *= programme&#091;position]\n            position = 0\t\t\n\telse:\n\t\tposition  += 1\t\n    return int(nombre)\n\nfor n in range(1,200):\n    if fonction(n) == n:\n        print(n,fonction(n))<\/code><\/pre>\n\n\n\n<p>(le programme Fractran a \u00e9t\u00e9 invent\u00e9 par un \u00e9l\u00e8ve, sous forme de graphe, en SNT)<\/p>\n\n\n\n<p>En fait, un programme Fractran est une sorte d&rsquo;<a href=\"https:\/\/iremi.univ-reunion.fr\/?page_id=619\" data-type=\"page\" data-id=\"236\">automate binaire<\/a>, le fait que la multiplication par la fraction r\u00e9ussit ou \u00e9choue, conditionnant le chemin \u00e0 prendre (retourner au d\u00e9part en changeant de nombre, ou aller \u00e0 la fraction suivante). Le programme Fractran ci-dessus (en Python) donne alors le graphe suivant :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/jeufrac1.pdf\" type=\"application\/pdf\" style=\"width:100%;height:780px\" aria-label=\"Contenu embarqu\u00e9 jeufrac1.\"><\/object><a id=\"wp-block-file--media-f1262499-fae8-4354-9e50-086107124b6a\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/jeufrac1.pdf\">jeufrac1<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/jeufrac1.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-f1262499-fae8-4354-9e50-086107124b6a\">T\u00e9l\u00e9charger<\/a><\/div>\n\n\n\n<p>Cela a \u00e9t\u00e9 l&rsquo;occasion d&rsquo;un jeu en ext\u00e9rieur, coanim\u00e9 par des \u00e9l\u00e8ves de 2nde (SNT) et des \u00e9l\u00e8ves de l&rsquo;Alefpa, la <em>course des fractions<\/em> : chaque fraction est un point du lyc\u00e9e, o\u00f9 sont install\u00e9s des \u00e9l\u00e8ves accueillant les concurrents, leur demandant leur nombre, v\u00e9rifiant si la multiplication du nombre (du concurrent) par la fraction (de la station) r\u00e9ussit.<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Si la multiplication r\u00e9ussit, on envoie le concurrent vers le d\u00e9part (en suivant la fl\u00e8che bleue) o\u00f9 il donne au ma\u00eetre du jeu son nouveau nombre, et l\u00e0 il repart avec son nouveau nombre.<\/li>\n\n\n\n<li>Si la multiplication \u00e9choue, le concurrent garde son nombre actuel et est guid\u00e9 vers l&rsquo;\u00e9tape suivante (fl\u00e8che rouge).<\/li>\n<\/ul>\n\n\n\n<p>Au d\u00e9part du jeu (point d&rsquo;interrogation sur le graphe), le concurrent se voit confier un nombre entier (d\u00e9pendant du concurrent, ce n&rsquo;est pas le m\u00eame entier pour tout le monde), puis est guid\u00e9 vers la premi\u00e8re fraction. Ensuite, chaque fois qu&rsquo;un concurrent arrive (en suivant une fl\u00e8che bleue) au d\u00e9part, il donne son nombre actuel au ma\u00eetre du jeu, qui v\u00e9rifie si le nombre a chang\u00e9 depuis le dernier passage.  Dans le cas contraire (le coureur est pass\u00e9 par une fl\u00e8che rouge), il d\u00e9clare que la course est finie, et note en vis-\u00e0-vis du nombre de d\u00e9part, le nombre d&rsquo;arriv\u00e9e.<\/p>\n\n\n\n<p>Lorsque tous les concurrents ont fini la course, on dispose d&rsquo;une feuille de ce genre :<\/p>\n\n\n\n<figure class=\"wp-block-table\"><table class=\"has-fixed-layout\"><tbody><tr><td>24<\/td><td>1<\/td><\/tr><tr><td>25<\/td><td>1<\/td><\/tr><tr><td>27<\/td><td>1<\/td><\/tr><tr><td>30<\/td><td>1<\/td><\/tr><tr><td>32<\/td><td>1<\/td><\/tr><tr><td>35<\/td><td>7<\/td><\/tr><tr><td>36<\/td><td>1<\/td><\/tr><tr><td>55<\/td><td>11<\/td><\/tr><tr><td>56<\/td><td>7<\/td><\/tr><tr><td>60<\/td><td>1<\/td><\/tr><\/tbody><\/table><\/figure>\n\n\n\n<p>La question \u00e9tant \u00e9videmment<em> que calcule ce programme Fractran ?<\/em><\/p>\n\n\n\n<p>On peut aussi songer \u00e0 un projet o\u00f9 les concurrents flashent un QR-code pour g\u00e9olocaliser la prochaine \u00e9tape, mais dans ce cas les \u00e9tapes doivent \u00eatre suffisamment \u00e9loign\u00e9es pour ne pas souffrir du manque de pr\u00e9cision de la g\u00e9olocalisation.<\/p>\n\n\n\n<p><\/p>\n\n\n\n<p>Voici un r\u00e9sum\u00e9 de l&rsquo;article de Conway, en lien avec la conjecture de Collatz :<\/p>\n\n\n\n<div data-wp-interactive=\"core\/file\" class=\"wp-block-file\"><object data-wp-bind--hidden=\"!state.hasPdfPreview\" hidden class=\"wp-block-file__embed\" data=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/Collatz_Busser.pdf\" type=\"application\/pdf\" style=\"width:100%;height:430px\" aria-label=\"Contenu embarqu\u00e9 Collatz_Busser.\"><\/object><a id=\"wp-block-file--media-dff69432-3db3-4108-aa8e-1f5cc115db6c\" href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/Collatz_Busser.pdf\">Collatz_Busser<\/a><a href=\"https:\/\/iremi.univ-reunion.fr\/wp-content\/uploads\/2016\/10\/Collatz_Busser.pdf\" class=\"wp-block-file__button wp-element-button\" download aria-describedby=\"wp-block-file--media-dff69432-3db3-4108-aa8e-1f5cc115db6c\">T\u00e9l\u00e9charger<\/a><\/div>\n","protected":false},"excerpt":{"rendered":"<p>Fractran est un langage de programmation Turing-complet, ainsi que le prouve son cr\u00e9ateur : L&rsquo;int\u00e9r\u00eat essentiel de Fractran est qu&rsquo;il est bas\u00e9 sur les fractions. Ce langage permet donc de faire travailler \u00e0 la fois Voici un exemple de programme Fractran, pour voir le principe. Et un programme de multiplication en Fractran (bas\u00e9 sur la [&hellip;]<\/p>\n","protected":false},"author":6,"featured_media":1065,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[9,3,10],"tags":[18,30,31,83,79,80],"coauthors":[54],"class_list":["post-687","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-algorithmes-programmation-et-langages","category-arithmetique-et-algebre","category-machines-information-codage","tag-algorithmique","tag-cycle-3","tag-cycle-4","tag-fractions","tag-graphes","tag-snt"],"_links":{"self":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts\/687","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/users\/6"}],"replies":[{"embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=687"}],"version-history":[{"count":10,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts\/687\/revisions"}],"predecessor-version":[{"id":1066,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/posts\/687\/revisions\/1066"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=\/wp\/v2\/media\/1065"}],"wp:attachment":[{"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=687"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=687"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=687"},{"taxonomy":"author","embeddable":true,"href":"https:\/\/iremi.univ-reunion.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcoauthors&post=687"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}