Machine de Von Neumann

Machine de Von Neumann

Constructeur universel

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[1].

Sommaire

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'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 évolutivité est limitée. D'autres structures, comme l'evoloop sont plus évolutives.

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

Également, 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[2].

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[3]. Le problème continue à l'heure actuelle à être étudié[4].

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'un cycle entier de réplication. Le constructeur universel demeure donc d'un intérêt essentiellement théorique.

Voir aussi

Liens internes

Liens externes

Bibliographie

  1. ↑ John von Neumann, The theory of self reproducing automata, A. W. Burks (Ed.), Univ. of Illinois Press, Illinois (1966)
  2. ↑ Umberto Pesavento, An implementation of von Neumann's self-reproducing machine Artificial Life 2 (1995), pp 337-354
  3. ↑ 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)
  4. ↑ 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
Ce document provient de « Constructeur universel ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Machine de Von Neumann de Wikipédia en français (auteurs)

Игры ⚽ Поможем написать курсовую

Regardez d'autres dictionnaires:

  • Von Neumann (disambiguation) — von Neumann may refer to:* von Neumann (crater), a lunar impact crater * von Neumann (surname), a German surnameee also* von Neumann algebra * von Neumann architecture * von Neumann conjecture * von Neumann entropy * von Neumann machine * von… …   Wikipedia

  • Von Neumann machine — may refer to:.* Von Neumann architecture, a conceptual model of a computer architecture * Self replicating machines, a class of machines that can replicate themselves ** Universal Constructors, self replicating cellular automata ** Von Neumann… …   Wikipedia

  • Von Neumann cellular automaton — Von Neumann cellular automata are the original expression of cellular automata, the development of which were prompted by suggestions made to John von Neumann by his close friend and fellow mathematician Stanisław Ulam. Their original purpose was …   Wikipedia

  • Von Neumann architecture — The term Von Neumann architecture, aka the Von Neumann model, derives from a computer architecture proposal by the mathematician and early computer scientist John von Neumann and others, dated June 30, 1945, entitled First Draft of a Report on… …   Wikipedia

  • von Neumann, John — orig. Johann Von Neumann born Dec. 3, 1903, Budapest, Hung. died Feb. 8, 1957, Washington, D.C., U.S. Hungarian born U.S. mathematician. After receiving his Ph.D. from the University of Budapest, he emigrated to the U.S. to teach at Princeton… …   Universalium

  • Von Neumann universal constructor — John von Neumann s Universal Constructor is a self replicating machine in a cellular automata environment. It was designed in the 1940s, without the use of a computer. The fundamental details of the machine were published in von Neumann s book… …   Wikipedia

  • Von Neumann — John von Neumann Pour les articles homonymes, voir Neumann. John von Neumann …   Wikipédia en Français

  • von Neumann machine — Named after the mathematician John von Neumann (1903–57), a von Neumann machine is a computer built around (i) a control unit, an arithmetic and logic unit, a memory, and input and output facilities; (ii) a way of storing programs in memory; and… …   Philosophy dictionary

  • von Neumann machine — ▪ computer science  the basic design of the modern, or classical, computer. The concept was fully articulated by three of the principal scientists involved in the construction of ENIAC during World War II Arthur Burks, Herman Goldstine, and John… …   Universalium

  • Von Neumann syndrome — The von Neumann syndrome is a computing term coined by Prof. C. V. Ramamoorthy (after having listened to a keynote by Reiner Hartenstein, and named after John von Neumann s model of computer architecture). Ramamoorthy noted that for most… …   Wikipedia

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”