stringtranslate.com

Constructor universal de von Neumann

La primera implementación del constructor universal autorreproductor de von Neumann. [1] Se muestran tres generaciones de máquinas: la segunda casi ha terminado de construir la tercera. Las líneas que se extienden hacia la derecha son las cintas de instrucciones genéticas, que se copian junto con el cuerpo de las máquinas. La máquina mostrada se ejecuta en una versión de 32 estados del entorno de autómatas celulares de von Neumann, no en su especificación original de 29 estados.

El constructor universal de John von Neumann es una máquina autorreplicante en un entorno de autómata celular (CA). Fue diseñado en la década de 1940, sin el uso de una computadora. Los detalles fundamentales de la máquina fueron publicados en el libro de von Neumann Theory of Self-Reproducing Autómatas , completado en 1966 por Arthur W. Burks después de la muerte de von Neumann. [2] Se considera fundamental para la teoría de autómatas , sistemas complejos y vida artificial . [3] [4] De hecho, el premio Nobel Sydney Brenner consideró que el trabajo de von Neumann sobre autómatas autorreproductores (junto con el trabajo de Turing sobre máquinas de computación) también era central para la teoría biológica , permitiéndonos "disciplinar nuestros pensamientos sobre las máquinas, tanto naturales como artificiales". [5]

El objetivo de von Neumann, tal como se especificó en sus conferencias en la Universidad de Illinois en 1949, [2] era diseñar una máquina cuya complejidad pudiera crecer automáticamente de manera similar a los organismos biológicos bajo selección natural . Preguntó cuál es el umbral de complejidad que debe cruzarse para que las máquinas puedan evolucionar. [4] Su respuesta fue especificar una máquina abstracta que, cuando se ejecuta, se replicaría a sí misma. En su diseño, la máquina autorreplicante consta de tres partes: una "descripción" de ('modelo' o programa para) sí misma, un mecanismo constructor universal que puede leer cualquier descripción y construir la máquina (sin descripción) codificada en esa descripción, y una máquina copiadora universal que puede hacer copias de cualquier descripción. Después de que el constructor universal se ha utilizado para construir una nueva máquina codificada en la descripción, la máquina copiadora se utiliza para crear una copia de esa descripción, y esta copia se pasa a la nueva máquina, lo que da como resultado una réplica funcional de la máquina original que puede seguir reproduciéndose. Algunas máquinas harán esto al revés, copiando la descripción y luego construyendo una máquina. Es fundamental que la máquina autorreproductora pueda evolucionar acumulando mutaciones de la descripción, no de la máquina en sí, adquiriendo así la capacidad de crecer en complejidad. [4] [5]

Para definir su máquina con más detalle, von Neumann inventó el concepto de autómata celular . El que utilizó consiste en una cuadrícula bidimensional de células, cada una de las cuales puede estar en uno de los 29 estados en cualquier momento. En cada paso de tiempo, cada célula actualiza su estado en función de los estados de las células circundantes en el paso de tiempo anterior. Las reglas que rigen estas actualizaciones son idénticas para todas las células.

El constructor universal es un patrón determinado de estados de celda en este autómata celular. Contiene una línea de celdas que sirven como descripción (similar a la cinta de Turing ), codificando una secuencia de instrucciones que sirven como un "plano" para la máquina. La máquina lee estas instrucciones una por una y realiza las acciones correspondientes. Las instrucciones indican a la máquina que use su "brazo de construcción" (otro autómata que funciona como un sistema operativo [4] ) para construir una copia de la máquina, sin la cinta de descripción, en alguna otra ubicación en la cuadrícula de celdas. La descripción no puede contener instrucciones para construir una cinta de descripción igualmente larga, al igual que un contenedor no puede contener un contenedor del mismo tamaño. Por lo tanto, la máquina incluye la máquina de copia separada que lee la cinta de descripción y pasa una copia a la máquina recién construida. El nuevo conjunto resultante de máquinas de construcción universal y copia más la cinta de descripción es idéntico al anterior, y procede a replicarse nuevamente.

Objetivo

Sistema de Autómatas Autorreplicantes de Von Neumann con capacidad de evolucionar (Figura adaptada de las Notas de Clase de Luis Rocha en la Universidad de Binghamton [6] ). i) el sistema autorreplicante está compuesto por varios autómatas más una descripción separada (una codificación formalizada como una 'cinta' de Turing ) de todos los autómatas: Constructor Universal (A), Copiador Universal (B), Sistema Operativo (C), funciones extra no involucradas con la replicación (D), y descripción separada Φ(A,B,C,D) que codifica todos los autómatas. ii) (Arriba) El Constructor Universal produce (decodifica) autómatas a partir de su descripción ( modo activo de descripción); (Abajo) El Copiador Universal copia la descripción de los autómatas (modo pasivo de descripción); Las mutaciones Φ(D') a la descripción Φ(D) (no los cambios en el autómata D directamente) se propagan al conjunto de autómatas producidos en la siguiente generación, permitiendo que el sistema (autómatas + descripción) continúe replicándose y evolucionando (D → D'). [4] El proceso activo de construcción a partir de una descripción es paralelo a la traducción del ADN , el proceso pasivo de copia de la descripción es paralelo a la replicación del ADN y la herencia de descripciones mutadas es paralela a la herencia vertical de mutaciones del ADN en biología, [4] [5] y fueron propuestas por Von Neumann antes del descubrimiento de la estructura de la molécula de ADN y cómo se traduce y replica por separado en la célula. [6]

Tradicionalmente, se ha entendido el diseño de von Neumann como una demostración de los requisitos lógicos para la autorreplicación de las máquinas. [3] Sin embargo, está claro que máquinas mucho más simples pueden lograr la autorreplicación. Algunos ejemplos incluyen el crecimiento trivial similar al de un cristal , la replicación de plantillas y los bucles de Langton . Pero von Neumann estaba interesado en algo más profundo: la construcción, la universalidad y la evolución. [4] [5]

Nótese que las estructuras de CA autorreplicantes más simples (especialmente, el bucle de Byl y el bucle de Chou–Reggia ) no pueden existir en una amplia variedad de formas y, por lo tanto, tienen una capacidad de evolución muy limitada . Otras estructuras de CA, como el Evoloop, son algo evolutivas, pero aún no admiten una evolución abierta. Comúnmente, los replicadores simples no contienen completamente la maquinaria de construcción, ya que existe un grado en el que el replicador es información copiada por su entorno circundante. Aunque el diseño de Von Neumann es una construcción lógica, en principio es un diseño que podría instanciarse como una máquina física. De hecho, este constructor universal puede verse como una simulación abstracta de un ensamblador universal físico . La cuestión de la contribución del entorno a la replicación está algo abierta, ya que existen diferentes concepciones de la materia prima y su disponibilidad.

La idea fundamental de von Neumann es que la descripción de la máquina, que se copia y se transmite a la descendencia por separado a través del copiador universal, tiene un doble uso: es un componente activo del mecanismo de construcción en la reproducción y el objetivo de un proceso de copia pasivo . Este papel lo desempeña la descripción (similar a la cinta de instrucciones de Turing ) en la combinación de von Neumann de constructor universal y copiador universal. [4] La combinación de un constructor y copiador universal, más una cinta de instrucciones, conceptualiza y formaliza i) la autorreplicación y ii) la evolución abierta, o el crecimiento de la complejidad observado en los organismos biológicos. [3]

Esta idea es aún más notable porque precedió al descubrimiento de la estructura de la molécula de ADN por Watson y Crick y cómo se traduce y replica por separado en la célula, aunque siguió al experimento de Avery-MacLeod-McCarty que identificó al ADN como el portador molecular de la información genética en los organismos vivos. [6] La molécula de ADN es procesada por mecanismos separados que llevan a cabo sus instrucciones ( traducción ) y copian ( replican ) el ADN para las células recién construidas. La capacidad de lograr una evolución abierta radica en el hecho de que, al igual que en la naturaleza, los errores ( mutaciones ) en la copia de la cinta genética pueden conducir a variantes viables del autómata, que luego pueden evolucionar a través de la selección natural . [4] Como lo expresó Brenner:

Turing inventó el ordenador con programa almacenado y von Neumann demostró que la descripción es independiente del constructor universal. Esto no es trivial. El físico Erwin Schrödinger confundió el programa con el constructor en su libro de 1944 ¿Qué es la vida?, en el que veía los cromosomas como «el plan del arquitecto y el oficio del constructor en uno». Esto es un error. El código fuente contiene sólo una descripción de la función ejecutiva, no la función en sí. [5]

—Sydney  Brenner

Evolución de la complejidad

El objetivo de von Neumann, como se especificó en sus conferencias en la Universidad de Illinois en 1949, [2] era diseñar una máquina cuya complejidad pudiera crecer automáticamente de manera similar a los organismos biológicos bajo selección natural . Se preguntó cuál es el umbral de complejidad que debe cruzarse para que las máquinas puedan evolucionar y crecer en complejidad. [4] [3] Sus diseños de "prueba de principio" mostraron cómo es lógicamente posible. Al usar una arquitectura que separa un constructor programable de propósito general ("universal") de una copiadora de propósito general, mostró cómo las descripciones (cintas) de las máquinas podrían acumular mutaciones en la autorreplicación y, por lo tanto, desarrollar máquinas más complejas (la imagen a continuación ilustra esta posibilidad). Este es un resultado muy importante, ya que antes de eso, podría haberse conjeturado que existe una barrera lógica fundamental para la existencia de tales máquinas; en cuyo caso, los organismos biológicos, que evolucionan y crecen en complejidad, no podrían ser "máquinas", como se entiende convencionalmente. La idea de von Neumann fue pensar en la vida como una máquina de Turing, que, a su vez, se define por una "cabeza" de máquina determinada por su estado y separada de una cinta de memoria. [5]

En la práctica, cuando consideramos la implementación particular de autómatas que Von Neumann persiguió, concluimos que no produce mucha dinámica evolutiva porque las máquinas son demasiado frágiles: la gran mayoría de las perturbaciones hacen que efectivamente se desintegren. [3] Por lo tanto, es el modelo conceptual esbozado en sus conferencias de Illinois [2] el que es de mayor interés hoy porque muestra cómo una máquina puede, en principio, evolucionar. [7] [4] Esta idea es aún más notable porque el modelo precedió al descubrimiento de la estructura de la molécula de ADN como se discutió anteriormente. [6] También es digno de mención que el diseño de Von Neumann considera que las mutaciones hacia una mayor complejidad deben ocurrir en los (descripciones de) subsistemas no involucrados en la auto-reproducción en sí, como lo conceptualizó el autómata adicional D que él consideró que realiza todas las funciones no directamente involucradas en la reproducción (ver la Figura anterior con el Sistema de Autómatas de Auto-Replicación de Von Neumann con la capacidad de evolucionar). De hecho, en los organismos biológicos solo se han observado variaciones muy menores del código genético, lo que coincide con el razonamiento de Von Neumann de que el constructor universal ( A ) y el Copiador ( B ) no evolucionarían por sí mismos, dejando toda la evolución (y el crecimiento de la complejidad) al autómata D . [4] En su trabajo inacabado, Von Neumann también considera brevemente el conflicto y las interacciones entre sus máquinas autorreproductoras, hacia la comprensión de la evolución de las interacciones ecológicas y sociales a partir de su teoría de las máquinas autorreproductoras. [2] : 147 

Una demostración de la capacidad de la máquina de von Neumann para admitir mutaciones heredables. (1) En un paso temporal anterior, se agregó manualmente una mutación a la cinta de la máquina de segunda generación. (2) Las generaciones posteriores muestran el fenotipo de la mutación (un dibujo de una flor) y transmiten la mutación a sus hijos, ya que la cinta se copia cada vez. Este ejemplo ilustra cómo el diseño de von Neumann permite el crecimiento de la complejidad (en teoría), ya que la cinta podría especificar una máquina que sea más compleja que la que la realiza.

Implementaciones

En la teoría de autómatas, el concepto de constructor universal no es trivial debido a la existencia de patrones del Jardín del Edén (configuraciones que no tienen predecesor). Pero una definición simple es que un constructor universal es capaz de construir cualquier patrón finito de células no excitadas (quiescentes).

Arthur Burks y otros ampliaron el trabajo de von Neumann y ofrecieron un conjunto mucho más claro y completo de detalles sobre el diseño y el funcionamiento del autorreplicador de von Neumann. El trabajo de J. W. Thatcher es particularmente notable, ya que simplificó enormemente el diseño. Sin embargo, su trabajo no produjo un diseño completo, célula por célula, de una configuración capaz de demostrar la autorreplicación.

Renato Nobili y Umberto Pesavento publicaron el primer autómata celular autorreproductor completamente implementado en 1995, casi cincuenta años después del trabajo de von Neumann. [1] [8] Utilizaron un autómata celular de 32 estados en lugar de la especificación original de 29 estados de von Neumann , ampliándola para permitir un cruce de señales más fácil, una función de memoria explícita y un diseño más compacto. También publicaron una implementación de un constructor general dentro del CA original de 29 estados, pero no uno capaz de una replicación completa: la configuración no puede duplicar su cinta, ni puede activar su descendencia; la configuración solo puede construir. [8] [9]

En 2004, D. Mange et al. informaron sobre la implementación de un autorreplicador que es consistente con los diseños de von Neumann. [10]

En 2007, Nobili publicó una implementación de 32 estados que utiliza codificación de longitud de ejecución para reducir en gran medida el tamaño de la cinta. [11]

En 2008, William R. Buckley publicó dos configuraciones que son autorreplicantes dentro del CA original de 29 estados de von Neumann. [9] Buckley afirma que el cruce de señales dentro de los autómatas celulares de 29 estados de von Neumann no es necesario para la construcción de autorreplicantes. [9] Buckley también señala que, para los fines de la evolución, cada replicador debería volver a su configuración original después de replicarse, para ser capaz (en teoría) de hacer más de una copia. Tal como se publicó, el diseño de 1995 de Nobili-Pesavento no cumple con este requisito, pero el diseño de 2007 de Nobili sí lo hace; lo mismo es cierto para las configuraciones de Buckley.

En 2009, Buckley publicó con Golly una tercera configuración para los autómatas celulares de 29 estados de von Neumann, que pueden realizar tanto la autorreplicación holística como la autorreplicación mediante construcción parcial. Esta configuración también demuestra que el cruce de señales no es necesario para la construcción de autorreplicadores dentro de los autómatas celulares de 29 estados de von Neumann.

CL Nehaniv en 2002, y también Y. Takada et al. en 2004, propusieron un constructor universal implementado directamente sobre un autómata celular asincrónico, en lugar de sobre un autómata celular sincrónico. [12] [13]

Comparación de implementaciones

Según la definición de von Neumann, la construcción universal implica la construcción de configuraciones pasivas únicamente. Como tal, el concepto de construcción universal no constituía nada más que un recurso literario (o, en este caso, matemático). Facilitaba otras pruebas, como la de que una máquina bien construida puede autorreplicarse, mientras que la construcción universal en sí misma simplemente se suponía sobre un caso mínimo. La construcción universal bajo este estándar es trivial. Por lo tanto, si bien todas las configuraciones dadas aquí pueden construir cualquier configuración pasiva, ninguna puede construir el órgano de cruce en tiempo real ideado por Gorman. [9]

Practicidad y costo computacional

Todas las implementaciones de la máquina autorreproductora de von Neumann requieren recursos considerables para funcionar en una computadora. Por ejemplo, en la implementación de 32 estados de Nobili-Pesavento que se muestra arriba, mientras que el cuerpo de la máquina tiene solo 6.329 celdas no vacías (dentro de un rectángulo de tamaño 97x170), requiere una cinta de 145.315 celdas de largo y tarda 63 mil millones de pasos de tiempo en replicarse. Un simulador que funcione a 1.000 pasos de tiempo por segundo tardaría más de 2 años en hacer la primera copia. En 1995, cuando se publicó la primera implementación, los autores aún no habían visto replicarse su propia máquina. Sin embargo, en 2008, el algoritmo hashlife se amplió para admitir los conjuntos de reglas de 29 y 32 estados de Golly . En una PC de escritorio moderna, la replicación ahora toma solo unos minutos, aunque se requiere una cantidad significativa de memoria.

Galería de animación

Véase también

Referencias

  1. ^ abcd Pesavento, Umberto (1995), "Una implementación de la máquina autorreproductora de von Neumann" (PDF) , Artificial Life , 2 (4), MIT Press: 337–354, doi :10.1162/artl.1995.2.337, PMID  8942052, archivado desde el original (PDF) el 21 de junio de 2007
  2. ^ abcde von Neumann, John; Burks, Arthur W. (1966), Teoría de los autómatas que se reproducen a sí mismos. (Libro escaneado en línea) , University of Illinois Press , consultado el 28 de febrero de 2017
  3. ^ abcde McMullin, B. (2000), "John von Neumann y el crecimiento evolutivo de la complejidad: mirando hacia atrás, mirando hacia adelante..." , Artificial Life , 6 (4): 347–361, doi :10.1162/106454600300103674, PMID  11348586, S2CID  5454783
  4. ^ abcdefghijkl Rocha, Luis M. (1998), "Autoorganización seleccionada y la semiótica de los sistemas evolutivos", Evolutionary Systems , Springer, Dordrecht, págs. 341–358, doi :10.1007/978-94-017-1510-2_25, ISBN 978-90-481-5103-5
  5. ^ abcdef Brenner, Sydney (2012), "El código de escritura de la vida" , Nature , 482 (7386): 461, doi :10.1038/482461a, PMID  22358811, S2CID  205070101
  6. ^ abcd Rocha, Luis M. (2015), "Capítulo 6. Von Neumann y la selección natural.", Apuntes de clase del curso SSIE-583-Computación inspirada en la biología y sistemas evolutivos, Universidad de Binghamton
  7. ^ Pattee, Howard, H. (2012), "Autorreferencia en evolución: materia, símbolos y cierre semántico", LEYES, LENGUAJE Y VIDA , Biosemiótica, vol. 12, págs. 9-27, doi :10.1007/978-94-007-5161-3_14, ISBN 978-94-007-5160-6{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )
  8. ^ ab Nobili, Renato; Pesavento, Umberto (1996), "Autómatas generalizados de von Neumann", en Besussi, E.; Cecchini, A. (eds.), Proc. Mundos artificiales y estudios urbanos, Conferencia 1 (PDF) , Venecia: DAEST
  9. ^ abcde Buckley, William R. (2008), "Soluciones de cruce de señales en autómatas celulares autorreplicantes de von Neumann", en Andrew Adamatzky ; Ramon Alonso-Sanz; Anna Lawniczak ; Genaro Juárez Martínez; Kenichi Morita; Thomas Worsch (eds.), Proc. Automata 2008 (PDF) , Luniver Press, págs. 453–503
  10. ^ Mange, Daniel; Stauffer, A.; Peparaolo, L.; Tempesti, G. (2004), "Una visión macroscópica de la autorreplicación", Actas del IEEE , 92 (12): 1929–1945, doi :10.1109/JPROC.2004.837631, S2CID  22500865
  11. ^ ab Nobili, Renato (2007). «Los autómatas celulares de John von Neumann». Archivado desde el original el 29 de enero de 2011. Consultado el 29 de enero de 2011 .
  12. ^ Nehaniv, Chrystopher L. (2002), "Autorreproducción en autómatas celulares asincrónicos", Conferencia NASA/DoD de 2002 sobre hardware evolutivo (15-18 de julio de 2002, Alexandria, Virginia, EE. UU.) , IEEE Computer Society Press, págs. 201-209
  13. ^ Takada, Yousuke; Isokawa, Teijiro; Peper, Fernando; Matsui, Nobuyuki (2004), "Construcción universal sobre autómatas celulares autocronometrados", en Sloot, PMA (ed.), ACRI 2004, LNCS 3305 , págs.
  14. ^ abc andykt (18 de julio de 2023). "Caramba, un simulador de Juego de la vida". SourceForge .
  15. ^ "Autorreplicación". Complex Projective 4-Space . 12 de noviembre de 2012.

Enlaces externos