{"id":2850,"date":"2012-03-19T00:01:16","date_gmt":"2012-03-18T23:01:16","guid":{"rendered":"http:\/\/sciencetonnante.wordpress.com\/?p=2850"},"modified":"2012-03-19T00:01:16","modified_gmt":"2012-03-18T23:01:16","slug":"les-quines-des-programmes-informatiques-auto-replicateurs","status":"publish","type":"post","link":"https:\/\/scienceetonnante.com\/blog\/2012\/03\/19\/les-quines-des-programmes-informatiques-auto-replicateurs\/","title":{"rendered":"Les quines : des programmes informatiques auto-r\u00e9plicateurs"},"content":{"rendered":"
\n

\"\"<\/a>Les cellules de notre organisme sont capables de se r\u00e9pliquer \u00e0 l’identique, et \u00e7a nous parait bien naturel. Et pourtant, la question de l’auto-r\u00e9plication est loin d’\u00eatre \u00e9vidente.<\/p>\n

Pour s’en rendre compte, essayez-vous au petit d\u00e9fi suivant : \u00e9crire un programme informatique qui produise en sortie son propre code source<\/strong>. \u00c7a para\u00eet simple, non ?<\/p>\n

Vous allez voir que \u00e7a n’est pas le cas, et que l’\u00e9criture d’un tel programme n\u00e9cessite de se creuser un peu les m\u00e9ninges.<\/p>\n

Un essai na\u00eff<\/h3>\n

A premi\u00e8re vue, le d\u00e9fi parait facile. Il suffit d’utiliser la fonction print<\/em>, ou son \u00e9quivalent dans le langage de programmation consid\u00e9r\u00e9. Alors allons-y, on commence \u00e0 \u00e9crire son programme par une ligne d’introduction du genre<\/p>\n

begin mon_programme<\/pre>\n
Puis on poursuit par une ligne de code qui permet d’imprimer la ligne pr\u00e9c\u00e9dente<\/p>\n
print(\"begin mon_programme\")<\/pre>\n
Ensuite il nous faut une ligne qui imprime celle qu’on vient d’\u00e9crire<\/p>\n
print(\"print(\"begin mon_programme\")\")<\/pre>\n
et la suite<\/p>\n
print(\"print(\"print(\"begin mon_programme\")\")\")<\/pre>\n
Bon, pas besoin de continuer plus loin : vous voyez que \u00e7a ne marche pas ! Bien s\u00fbr, il existe une solution qui est d’ouvrir le propre fichier source du programme, de le lire et de l’imprimer. Mais cette solution est consid\u00e9r\u00e9e comme de la triche : le d\u00e9fi suppose qu’on ne fournisse aucune donn\u00e9e d’entr\u00e9e \u00e0 notre programme<\/strong>.<\/p>\n
Apr\u00e8s un peu de r\u00e9flexion et quelques essais infructueux, j’ai pens\u00e9 que le d\u00e9fi \u00e9tait impossible. Mais rassurez-vous, c’est possible ! Dans son livre G\u00f6del, Escher et Bach<\/em>, Douglas Hofstadter a baptis\u00e9 ce genre de programmes un quine<\/em><\/strong>, en r\u00e9f\u00e9rence au logicien\u00a0Willard van Orman Quine, qui a beaucoup \u00e9tudi\u00e9 les paradoxes de ce genre. Alors comment \u00e9crire un quine ?<\/p>\n
Un quine en fran\u00e7ais<\/h3>\n
Pour comprendre le principe g\u00e9n\u00e9rique de l’\u00e9criture d’un quine dans un langage de programmation, on peut commencer par en trouver un en fran\u00e7ais. Voici une solution possible:<\/p>\n
Ecrivez, puis \u00e9crivez entre guillemets \u00ab\u00a0Ecrivez, puis \u00e9crivez entre guillemets\u00a0\u00bb<\/em><\/span><\/p>\n
Si vous appliquez \u00e0 la lettre cette instruction en fran\u00e7ais, vous allez la reproduire ! Si un quine est possible en fran\u00e7ais, il doit \u00eatre possible dans un langage de programmation.<\/p>\n
Si on d\u00e9cortique un peu ce quine en fran\u00e7ais, on peut voir qu’il est compos\u00e9 de deux parties : la premi\u00e8re partie est la partie active<\/strong>, il s’agit de l’instruction proprement dite. La seconde partie, celle qui est entre guillemets, peut \u00eatre appel\u00e9e les donn\u00e9es<\/strong>. Il s’agit d’une cha\u00eene de texte, mais dont la signification est de permettre de construire la partie active. On peut examiner l’analogie biologique de cette construction.<\/p>\n
Je vous ai dit que les cellules de notre organisme sont un bon syst\u00e8me auto-r\u00e9plicateur. Il se trouve que nos cellules fonctionnent un peu comme notre quine en fran\u00e7ais. La cellule elle-m\u00eame peut \u00eatre vue comme la partie active, car c’est elle la machine qui va effectuer des op\u00e9rations. L’ADN lui est vu comme les donn\u00e9es, c’est de l’information, et cette information contient le plan de montage de la partie active.<\/p>\n
La beaut\u00e9 de l’histoire, c’est que quand la cellule se divise, elle r\u00e9plique \u00e0 la fois sa partie active et son plan de montage. L’instruction Ecrivez, puis \u00e9crivez entre guillemets \u00ab\u00a0Ecrivez, puis \u00e9crivez entre guillemets\u00a0\u00bb<\/span><\/em> est finalement tr\u00e8s analogue \u00e0 ce que fait la cellule qui applique une instruction du genre \u00ab\u00a0Duplique-toi et duplique aussi ton ADN\u00a0\u00bb.<\/p>\n
Un vrai quine informatique<\/h3>\n
\u00c9crire un quine dans un langage de programmation, c’est donc possible, mais \u00e7a n’est pas non plus super trivial. La page wikipedia<\/a> r\u00e9f\u00e9rence des quines \u00e9crits dans diff\u00e9rents langages. Pour vous donner une id\u00e9e, en voici un en C<\/p>\n
#include<stdio.h>\nchar*i=\"\\\\#include<stdio.h>\",n='\\n',q='\"',*p=\n\"%s%cchar*i=%c%c%s%c,n='%cn',q='%c',*p=%c%c%s%c,*m=%c%c%s%c%c;%s%c\",*m=\n\"int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}\"\n;int main(){return!printf(p,i+1,n,q,*i,i,q,*i,q,n,q,p,q,n,q,m,q,n,m,n);}<\/pre>\n
Pas tr\u00e8s lisible, hein ? La bonne nouvelle, c’est qu’on peut d\u00e9montrer que tout langage de programmation poss\u00e8de un quine, et m\u00eame une infinit\u00e9 (PS pour les matheux : c’est une cons\u00e9quence d’un th\u00e9or\u00e8me de type \u00ab\u00a0point fixe\u00a0\u00bb.)<\/p>\n
Souvent dans un quine, il est possible d’ins\u00e9rer des morceaux qui ne changent en rien l’ex\u00e9cution du programme, tout en conservant sa propri\u00e9t\u00e9 de quine. Un peu comme si on ins\u00e9rait des commentaires, par exemple<\/p>\n
[Ceci est un commentaire] Ecrivez, puis \u00e9crivez entre guillemets \u00ab\u00a0[Ceci est un commentaire]\u00a0Ecrivez, puis \u00e9crivez entre guillemets\u00a0\u00bb<\/span><\/em><\/p>\n
Ces morceaux de code qui ne modifient pas la propri\u00e9t\u00e9 d’autor\u00e9plication, et qui semblent ne servir \u00e0 rien, sont appel\u00e9s des introns<\/strong>. L\u00e0 aussi c’est une analogie biologique, car le terme d’intron d\u00e9signe normalement le nom de ces morceaux d’ADN qui font partie de notre code g\u00e9n\u00e9tique mais qui ne sont pas interpr\u00e9t\u00e9s.<\/p>\n
Dans les quines, les introns permettent de faire des choses tr\u00e8s bizarres : des multiquines<\/strong>. Par exemple un multiquine C-Java, c’est un code C qui une fois ex\u00e9cut\u00e9 fournit en sortie un code Java, qui lui m\u00eame ex\u00e9cut\u00e9 fournit le code C d’origine. Tordu, hein ? Et pas facile \u00e0 \u00e9crire, et encore moins \u00e0 lire ! Et on est pas oblig\u00e9s de se limiter \u00e0 2 langages. On peut le faire avec 3, 4, 5…il y a m\u00eame un grand malade qui a fait un multiquine pour 11 langages de programmation cons\u00e9cutifs<\/a> (je ne connais m\u00eame pas de nom la moiti\u00e9 de ces langages).<\/p>\n
Vers des machines auto-r\u00e9plicatrices<\/h3>\n
Au del\u00e0 de ces performances qui peuvent vous laisser indiff\u00e9rents, les quines permettent de se poser des tas de questions sur l’auto-r\u00e9plication. Et l’auto-r\u00e9plication \u00ab\u00a0physique\u00a0\u00bb est loin d’\u00eatre un probl\u00e8me simple. De nombreux chercheurs essayent de mettre au point une machine auto-r\u00e9plicatrice, c’est-\u00e0-dire qui puisse construire une copie d’elle-m\u00eame \u00e0 partir des ressources disponibles dans son environnement. Eh bien \u00e7a n’est pas facile !<\/p>\n
Il existe \u00e0 ce jour quelques tentatives int\u00e9ressantes, mais semble-t-il aucune qui soit totalement convaincante. Par exemple celle-ci, fruit de travaux men\u00e9s \u00e0 l’Universit\u00e9 de Cornell<\/a><\/p>\n
[youtube=http:\/\/www.youtube.com\/watch?v=K_EWzxRn8Xo]<\/p>\n
Cette vid\u00e9o est assez bluffante, mais on est pas dans l’autor\u00e9plication pure, puisque le robot n’utilise pas vraiment son environnement brut, mais exploite des cubes qui lui sont fournis. Ca n’est donc pas encore consid\u00e9r\u00e9 comme une preuve pure qu’une machine auto-r\u00e9plicatrice soit possible. D’un autre c\u00f4t\u00e9 c’est rassurant, \u00e7a nous met pour l’instant \u00e0 l’abri d’une invasion de la Terre par des robots auto-r\u00e9plicateurs !<\/p>\n
Une tr\u00e8s bonne source sur les quines, sur le site de David Madore<\/a><\/em><\/p>\n
Le m\u00eame furieux qui a fait le multiquine \u00e0 11 langage a r\u00e9cemment post\u00e9 une vid\u00e9o d’un quine avec microcontrolleur Arduino<\/a> et des LEDs !<\/em><\/p>\n<\/div>\n","protected":false},"excerpt":{"rendered":"
Les cellules de notre organisme sont capables de se r\u00e9pliquer \u00e0 l’identique, et \u00e7a nous parait bien naturel. Et pourtant, la question de l’auto-r\u00e9plication est loin d’\u00eatre \u00e9vidente. Pour s’en rendre compte, essayez-vous au petit d\u00e9fi suivant : \u00e9crire un programme informatique qui produise en sortie son propre code source. \u00c7a para\u00eet simple, non ?<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[45],"tags":[43],"class_list":{"0":"post-2850","1":"post","2":"type-post","3":"status-publish","4":"format-standard","6":"category-informatique","7":"tag-algorithmique"},"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"post_mailing_queue_ids":[],"_links":{"self":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/2850","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/comments?post=2850"}],"version-history":[{"count":0,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/posts\/2850\/revisions"}],"wp:attachment":[{"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/media?parent=2850"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/categories?post=2850"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/scienceetonnante.com\/blog\/wp-json\/wp\/v2\/tags?post=2850"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}