Constructeur universel
410173
30360009
2008-06-05T22:24:04Z
Antoinetav
19081
/* Liens externes */ lien mort
Le '''constructeur universel''' est une structure [[autoréplicante]] au sein d'un [[automate cellulaire]], tous deux créés par [[John von Neumann]] dans les années 1940<ref>John von Neumann, ''The theory of self reproducing automata'', A. W. Burks (Ed.), Univ. of Illinois Press, Illinois (1966)</ref>.
== Description ==
L'automate cellulaire utilisé par von Neumann comporte 29 états distincts. La structure autoréplicante utilise ces 29 états pour simuler des fils et des signaux. Un enregistrement formé par une succession de cellules encode une suite d'actions que la structure doit effectuer. À l'aide d'une tête d'écriture, cette structure peut créer de nouvelles cellules, permettant ainsi une réplication d'elle-même et de l'enregistrement.
== Interprétation ==
Le constructeur universel de von Neumann est la démonstration de la possibilité logique de l'autoréplication. Il s'agit cependant d'une structure extrêmement complexe et un certain nombre de structures plus simples furent créées au fil du temps (en particulier la [[boucle de Langton]]).
Le constructeur universel possède néanmoins, comme son nom l'indique, la propriété d'[[Machine de Turing#Machines de Turing universelles|universalité]] : il lui est possible de créer non seulement des copies d'elle-même, mais aussi des variantes.
Les structures autoréplicantes les plus simples (tout particulièrement la [[boucle de Byl]] et les [[boucles de Chou-Reggia]]) ne possèdent pas d'enregistrement séparé, leur algorithme de réplication étant contenu dans la structure elle-même, et leur evolutivité est limitée. D'autres structures, comme l'''[[evoloop]]'' sont plus évolutives.
Il faut noter que le concept d'universalité n'est pas limité au constructeur universel : il a été prouvé que le [[jeu de la vie]] est universel. Il serait donc possible dans cet automate cellulaire simple de créer un constructeur universel fonctionnant de manière similaire à celui conçu par von Neumann (même si personne n'a jamais réussi à le faire).
On peut noter également que la variante ''[[HighLife]]'' du jeu de la vie possède une structure autoréplicante, le réplicateur, composée initialement de seulement 12 cellules.
== Implémentation ==
Le constructeur universel fut implémenté pour la première fois par Umberto Pesavento et Renato Nobili en 1995, 50 ans après sa création<ref>Umberto Pesavento, ''An implementation of von Neumann's self-reproducing machine'' Artificial Life 2 (1995), pp 337-354</ref>.
Nobili et Pesavento présentèrent également une extension de l'automate cellulaire qui, en ajoutant trois états, permettait des croisements plus simples entre les fils et la création d'une structure plus compacte<ref>Renato Nobili, Umberto Pesavento, ''Generalised von Neumann's Automata I: a Revisitation'', in ''Artificial Worlds and Urban Studies'', E.Besussi and A.Cecchini (Eds.), DAEST Pubblication, Convegni 1, Venezia (1996)</ref>. Le problème continue à l'heure actuelle à être étudié<ref>W. R. Buckley, A. Mukherjee, ''Constructibility of Signal-Crossing Solutions in von Neumann 29-State Cellular Automata'', V.S. Sunderam et al. (Eds.) (2005), ICCS 2005, LNCS 3515, pp. 395–403</ref>.
== Practicité ==
Même si les automates cellulaires peuvent en règle général être exécutés rapidement, la taille énorme requise par l'enregistrement (plus de 84 000 cellules dans la structure originale, nécessitant donc une implémentation d'au moins 85 000 cellules de large) a empêché jusqu'à présent la réalisation complète d'une cycle entier de réplication. Le constructeur universel demeure donc d'un intérêt essentiellement théorique.
== Voir aussi ==
=== Liens internes ===
* [[Automate cellulaire]]
* [[Automate cellulaire de Codd]]
* [[Autoréplication]]
* [[Boucle de Langton]]
* [[Réplicateur de Clanking]]
* ''[[Wireworld]]''
=== Liens externes ===
* {{en}} [ftp://ftp.ira.uka.de/pub/cellular-automata/jvn/ Code source original de Nobili et Pesavento]
* {{en}} [http://www.sq3.org.uk/Evolution/JvN/ Images, code source mis à jour et fichiers exécutables pour Windows]
* {{pdf}} {{en}} [http://www.pd.infn.it/%7Ernobili/pdf_files/jvnconstr.pdf Publication de Nobili et Pesavento]
=== Bibliographie ===
<references/>
[[Catégorie:Automate cellulaire]]
[[en:Von Neumann universal constructor]]