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é.

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 29⁵=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.

• 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.