Document ID: /fineweb-2-swissfilter-quality_10-filterrobots/filtered/07065.jsonl.gz/492

Constructeur de von Neumann
Dans les années 50, John von Neumann a développé un modèle appelé
constructeur universel. Il s'agit d'un automate cellulaire, dont
la conception a initié toute la recherche dans le domaine de l'auto-réplication
des machines.
Le pionnier, dans le domaine du matériel bio-inspiré, fut John von Neumann. Mathématicien surdoué et figure
emblématique du développement dans le domaine des ordinateurs, von Neumann a consacré les dernières années de sa vie à
la théorie des automates. Malheureusement interrompue par sa mort en 1957, cette recherche s'inspirait du parallèle
existant entre les automates artificiels, tels les ordinateurs par exemple, et les automates naturels, comme le
système nerveux, les organismes évolutifs, etc. Pour entreprendre la réalisation physique de sa théorie des automates,
von Neumann a développé un modèle connu sous le nom de constructeur universel. Il s'agit d'un automate
cellulaire qui devint le point de départ des recherches sur les machines autoréplicatives entreprises dans les
décennies suivant la conception de ce modèle.
Dans l'oeuvre de von Neumann, l'autoréplication apparaît toujours comme un cas particulier de construction
universelle: sa machine Uconst est capable de construire une autre machine M, pour autant qu'elle dispose de
sa description D(M). Cette approche étant conservée dans la conception de son automate cellulaire, ce dernier
s'avère être bien plus qu'une simple machine autoréplicative. La complexité de ses desseins se reflète dans la
complexité de sa structure, basée sur trois composants distincts:
- Une bande de mémoire, contenant la description (une chaîne unidimensionnelle d'éléments) de la machine
à construire. Dans le cas particulier de l'autoréplication, la bande de mémoire contient la description du
constructeur universel lui-même.
- Le constructeur proprement dit, une machine capable de lire la bande de mémoire et d'interpréter son contenu.
- Un bras constructeur, dirigé par le constructeur, utilisé pour construire le rejeton (la machine décrite dans
la bande de mémoire). Le bras se déplace dans l'espace et met les éléments du rejeton dans l'état approprié.
Figure 1: Construction universelle (à gauche) et autoréplication (à droite)
dans l'automate de von Neumann.
Outre cette complexité déjà considérable, von Neumann postule la présence d'un ordinateur universel Ucomp (en pratique,
une machine universelle de Turing, soit un automate capable d'opérer n'importe quel calcul fini). Cet ordinateur est
attaché au constructeur universel et se réplique avec lui. L'implémentation du constructeur universel sous forme
d'automate cellulaire est d'une complexité considérable. Chaque cellule pouvant prendre 29 états et l'état futur d'une
cellule dépendant de son propre état présent et de celui de ses quatre voisins cardinaux, le comportement de l'automate
satisfait exhaustivement 295=20'511'149 règles de transition. Si l'on considère que
la taille du constructeur de von Neumann avoisine les 100'000 éléments, il est facile de comprendre pourquoi l'automate
n'a jamais été complètement simulé à ce jour.
Dans le cadre du projet Embryonique, nous avions réalisé une implémentation matérielle d'un ensemble d'éléments de
l'automate de von Neumann. En concevant soigneusement la structure matérielle de chaque élément, nous avions
considérablement réduit l'espace mémoire requis pour loger les règles de transition. Usant de la même technique, nous avons
encodé une cellule de l'automate de von Neumann dans chaque élément du BioWall. Bien que les 3'200 éléments de ce dernier
soient insuffisants pour implémenter le constructeur universel dans sa totalité, il nous permet de matérialiser plusieurs
portions significatives (organes, dans la terminologie de von Neumann) de la machine.
Pour en savoir plus
- J.-L. Beuchat, J.-O. Haenni. "Von Neumann's 29-State Cellular
Automaton: A Hardware Implementation". IEEE Trans. on Education, Vol.
43, No 3, pp. 300-308, August 2000.
- J. von Neumann. The Theory
of Self-Reproducing Automata. A.W. Burks (ed.), University of Illinois
Press, Urbana, IL, 1966.