El constructor universal de John von Neumann es una máquina autorreplicante en un entorno de autómatas celulares (CA). Fue diseñado en la década de 1940, sin el uso de una computadora. Los detalles fundamentales de la máquina se publicaron en el libro de von Neumann Theory of Self-Reproducing Automata , completado en 1966 por Arthur W. Burks después de la muerte de von Neumann. [2] Aunque normalmente no es tan conocido como el otro trabajo de von Neumann, se considera fundamental para la teoría de autómatas , los sistemas complejos y la vida artificial . [3] [4] De hecho, premio NobelSydney Brenner consideró que el trabajo de Von Neumann sobre los autómatas que se reproducen a sí mismos (junto con el trabajo de Turing en las máquinas informáticas) también es fundamental para la teoría biológica , lo que nos permite "disciplinar nuestros pensamientos sobre las máquinas, tanto naturales como artificiales". [5]
El objetivo de Von Neumann, como se especifica 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 se debe traspasar 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 ('plano' o programa para) sí mismo, 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 fotocopiadora universalque puede hacer copias de cualquier descripción. Una vez que se ha utilizado el constructor universal para construir una nueva máquina codificada en la descripción, la fotocopiadora 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 hacen esto al revés, copiando la descripción y luego construyendo una máquina. Fundamentalmente, la máquina que se reproduce a sí misma puede evolucionar acumulando mutaciones de la descripción, no la máquina en sí, ganando 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 usó consiste en una cuadrícula bidimensional de celdas, cada una de las cuales puede estar en uno de los 29 estados en cualquier momento. En cada paso de tiempo, cada celda actualiza su estado dependiendo de los estados de las celdas circundantes en el paso de tiempo anterior. Las reglas que gobiernan estas actualizaciones son idénticas para todas las celdas.
El constructor universal es un cierto patrón de estados celulares 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 "modelo" para la máquina. La máquina lee estas instrucciones una a una y realiza las acciones correspondientes. Las instrucciones indican a la máquina que utilice 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 descriptiva, en algún otro lugar de la cuadrícula de celdas. La descripción no puede contener instrucciones para crear una cinta descriptiva igualmente larga, al igual que un contenedor no puede contener un contenedor del mismo tamaño. Por lo tanto, la máquina incluye la fotocopiadora separada que lee la cinta de descripción y pasa una copia a la máquina recién construida. El nuevo conjunto resultante de constructor universal y fotocopiadoras más cinta descriptiva es idéntico al anterior, y procede a replicarse nuevamente.
Propósito [ editar ]
El diseño de Von Neumann se ha entendido tradicionalmente como una demostración de los requisitos lógicos para la autorreplicación de la máquina. [3] Sin embargo, está claro que máquinas mucho más simples pueden lograr la autorreplicación. Los ejemplos incluyen el crecimiento trivial similar a un cristal , la replicación de la plantilla y los bucles de Langton . Pero von Neumann estaba interesado en algo más profundo: construcción, universalidad y evolución. [4] [5]
Tenga en cuenta que (en especial, las estructuras CA auto-replicantes más simples bucle de Byl y el bucle de Chou-Reggia ) no pueden existir en una amplia variedad de formas y por lo tanto tienen muy limitada capacidad de evolución . Otras estructuras de CA, como Evoloop, son algo evolutivas, pero aún no admiten la evolución abierta. Por lo general, los replicadores simples no contienen por completo la maquinaria de construcción, existiendo 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 ejemplificarse como una máquina física. De hecho, este constructor universal puede verse como una simulación abstracta de unensamblador universal . El tema de la contribución ambiental a la replicación está algo abierto, ya que existen diferentes concepciones de la materia prima y su disponibilidad.
La idea crucial 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 de la fotocopiadora universal, tiene un doble uso; siendo a la vez un componente activo del mecanismo de construcción en la reproducción, y siendo el objetivo de un proceso de copia pasiva . 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 copiadora universal. [4] La combinación de un constructor universal y una fotocopiadora, 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ó el experimento de Avery-MacLeod-McCarty que identificó al ADN como el portador molecular de información genética en organismos vivos. [6] La molécula de ADN se procesa mediante 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 puede conducir a variantes viables del autómata, que luego pueden evolucionar mediante selección natural . [4] Como dijo Brenner:
Turing inventó la computadora de programa almacenado, y von Neumann demostró que la descripción está separada del constructor universal. Esto no es trivial. El físico Erwin Schrödinger confundió el programa y el constructor en su libro de 1944 ¿Qué es la vida ?, en el que veía los cromosomas como ″ plan de arquitecto y oficio de constructor en uno ″. Esto está mal. El script de código contiene solo una descripción de la función ejecutiva, no la función en sí. [5]
- Sydney Brenner
Evolución de la complejidad [ editar ]
El objetivo de Von Neumann, como se especifica 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 se debe cruzar 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. Mediante el uso de una arquitectura que separa un constructor programable de propósito general ("universal") de una fotocopiadora de propósito general, mostró cómo las descripciones (cintas) de las máquinas pueden acumular mutaciones en la autorreplicación y, por lo tanto, desarrollar máquinas más complejas (la siguiente imagen ilustra esta posibilidad.). Este es un resultado muy importante, ya que antes de eso, se podría haber 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 se define de manera similar por una "cabeza" de máquina determinada por el estado separada de una cinta de memoria.[5]
En la práctica, cuando consideramos la implementación de autómatas particular que persiguió Von Neumann, llegamos a la conclusión de que no produce mucha dinámica evolutiva porque las máquinas son demasiado frágiles: la gran mayoría de las perturbaciones hacen que se desintegren de manera efectiva. [3] Por lo tanto, es el modelo conceptual esbozado en sus conferencias de Illinois [2] 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 autorreproducción en sí, como lo conceptualiza el autómata adicional D que él consideraba realizar todas las funciones no involucradas directamente en la reproducción. (Ver la Figura anterior con el Sistema de Automata de Autoreplicación de Von Neumann con la capacidad de evolucionar). De hecho, en los organismos biológicos solo se han observado variaciones muy pequeñas del código genético, lo que coincide con el razonamiento de Von Neumann de que el constructor universal ( A ) y copiadora ( B ) no se evolucionan en sí mismas, dejando toda la evolución (y el crecimiento de la complejidad) al autómata D . [4]En su obra inconclusa, Von Neumann también considera brevemente el conflicto y las interacciones entre sus máquinas que se reproducen a sí mismas, 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 que se reproducen a sí mismas. [2] : 147
Implementaciones [ editar ]
En la teoría de los autómatas, el concepto de constructor universal no es trivial debido a la existencia de patrones del Jardín del Edén . Pero una definición simple es que un constructor universal puede construir cualquier patrón finito de células no excitadas (inactivas).
Arthur Burks y otros ampliaron el trabajo de von Neumann, dando un conjunto de detalles mucho más claro y completo con respecto al diseño y funcionamiento del autorreplicador de von Neumann. El trabajo de JW Thatcher es particularmente notable, ya que simplificó enormemente el diseño. Aún así, su trabajo no produjo un diseño completo, celda por celda, 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] Usaron un autómata celular de 32 estados en lugar de la especificación original de 29 estados de von Neumann , extendié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 de la CA original de 29 estados, pero no uno capaz de replicarse por completo: 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. informó de una 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 usa 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 de la 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 autorreplicadores. [9] Buckley también señala que a los efectos de la evolución, cada replicador debe volver a su configuración original después de replicar, para ser capaz (en teoría) de hacer más de una copia. Según 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 mismo ocurre con 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 una autorreplicación holística o una autorreplicación por 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, propuso 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 [ editar ]
| Implementación | Fuente | Conjunto de reglas | Área rectangular | Número de celdas | Longitud de la cinta | Proporción | Período | Compresión de código de cinta | Longitud del código de cinta | Tipo de código de cinta | Mecanismo de replicación | Tipo de replicación | Tasa de crecimiento |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Nobili-Pesavento, 1995 [1] | [14] | Nobili 32 estados | 97 × 170 | 6.329 | 145,315 | 22,96 | 6,34 × 10 10 | ninguno | 5 bits | binario | constructor holístico | no repetible | lineal |
| Nobili, 2007 | SR_CCN_AP.EVN [15] | Nobili 32 estados | 97 × 100 | 5.313 | 56,325 | 10.60 | 9,59 × 10 9 | codificación limitada de longitud de ejecución | 5 bits | binario | constructor holístico | repetible | super-lineal |
| Buckley, 2008 | codon5.rle [16] | Nobili 32 estados | 112 × 50 | 3.343 | 44,155 | 13.21 | 5,87 x 10 9 | retracción automática | 5 bits | binario | constructor holístico | repetible | lineal |
| Buckley, 2008 [9] | replicator.mc [17] | von Neumann 29 estados | 312 × 132 | 18.589 | 294,844 | 15,86 | 2,61 × 10 11 | retracción automática | 5 bits | binario | constructor holístico | repetible | lineal |
| Buckley, 2008 | codon4.rle [16] | Nobili 32 estados | 109 × 59 | 3,574 | 37,780 | 10,57 | 4,31 x 10 9 | autorretracción / generación de bits | 4 bits | binario | constructor holístico | repetible | lineal |
| Buckley, 2009 | codon3.rle | Nobili 32 estados | 116 × 95 | 4.855 | 23.577 | 4.86 | 1,63 x 10 9 | retracción automática / generación de bits / superposición de código | 3 bits | binario | constructor holístico | repetible | super-lineal |
| Buckley, 2009 | PartialReplicator.mc [16] | von Neumann 29 estados | 2063 × 377 | 264,321 | N / A | - | ≈1,12 x 10 14 | ninguno | 4 bits | binario | constructor parcial | repetible | lineal |
| Goucher y Buckley, 2012 | phi9.rle [18] | Nobili 32 estados | 122 × 60 | 3957 | 8920 | 2,25 | - | retracción automática / generación de bits / superposición de código / longitud de ejecución limitada | 3+ bits | ternario | constructor holístico | repetible | super-lineal |
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 más que un dispositivo literario (o, en este caso, matemático). Facilitó otras pruebas, como que una máquina bien construida puede participar en la autorreplicación, mientras que la construcción universal en sí misma simplemente se asumió en 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 [ editar ]
Todas las implementaciones de la máquina de reproducción automática de von Neumann requieren recursos considerables para ejecutarse en la 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 que tiene 145,315 celdas de largo y ocupa 63 mil millones de pasos de tiempo para replicar. Un simulador que se ejecute a 1000 pasos por segundo tardaría más de 2 años en realizar la primera copia. En 1995, cuando se publicó la primera implementación, los autores no habían visto replicar su propia máquina. Sin embargo, en 2008, el algoritmo hashlife se amplió para admitir los conjuntos de reglas de 29 y 32 estados en Golly.. En una PC de escritorio moderna, la replicación ahora solo toma unos minutos, aunque se requiere una cantidad significativa de memoria.
Galería de animación [ editar ]
Ejemplo de un brazo de lectura de 29 estados.
Ver también [ editar ]
- Autómata celular de codd
- Bucles de Langton
- Autómatas celulares Nobili
- Quine , un programa que se produce a sí mismo como salida
- Máquina de Papá Noel
- Wireworld
Referencias [ editar ]
- ^ a b c Pesavento, Umberto (1995), "Una implementación de la máquina de autorreproducción de von Neumann" (PDF) , Artificial Life , MIT Press, 2 (4): 337–354, doi : 10.1162 / artl.1995.2.337 , PMID 8942052 , archivado desde el original (PDF) el 21 de junio de 2007
- ↑ a b c d e 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
- ^ a b c d e McMullin, B. (2000), "John von Neumann y el crecimiento evolutivo de la complejidad: mirando hacia atrás, mirando hacia adelante ..." , Vida artificial , 6 (4): 347–361, doi : 10.1162 / 106454600300103674 , PMID 11348586
- ^ a b c d e f g h i j k l Rocha, Luis M. (1998), "Autoorganización seleccionada y la semiótica de los sistemas evolutivos" , Evolutionary Systems , Springer, Dordrecht: 341–358
- ^ a b c d e f Brenner, Sydney (2012), "Script de código de la vida" , Nature , 482 : 461, doi : 10.1038 / 482461a , PMID 22358811
- ^ a b c d Rocha, Luis M. (2015), "Capítulo 6. Von Neumann y la selección natural". (PDF) , Notas de la conferencia del curso de computación inspirada biológicamente I-485, Universidad de Indiana (PDF)
- ^ Pattee, Howard, H. (1995), "Evolución de la autorreferencia: símbolos de la materia y cierre semántico" , Inteligencia artificial de comunicación y cognición , 12 (1-2): 9-27
- ^ a b Nobili, Renato; Pesavento, Umberto (1996), "Generalized von Neumann's Automata", en Besussi, E .; Cecchini, A. (eds.), Proc. Mundos artificiales y estudios urbanos, Conferencia 1 (PDF) , Venecia: DAEST
- ^ a b c d e Buckley, William R. (2008), "Soluciones de cruce de señales en autómatas celulares autoreplicantes 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
- ^ Sarna, Daniel; Stauffer, A .; Peparaolo, L .; Tempesti, G. (2004), "A Macroscopic View of Self-replication", Proceedings of the IEEE , 92 (12): 1929-1945, doi : 10.1109 / JPROC.2004.837631
- ^ "Copia archivada" . Archivado desde el original el 29 de enero de 2011 . Consultado el 29 de enero de 2011 .CS1 maint: archived copy as title (link)
- ^ Nehaniv, Chrystopher L. (2002), "Autorreproducción en autómatas celulares asincrónicos", Conferencia de la 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
- ^ Takada, Yousuke; Isokawa, Teijiro; Peper, Ferdinand; Matsui, Nobuyuki (2004), "Universal Construction on Self-Timed Cellular Automata", en Sloot, PMA (ed.), ACRI 2004, LNCS 3305 , págs. 21-30
- ^ "Constructor universal autorreproductor de Von Neumann" .
- ^ Los autómatas celulares de John von Neumann [1]
- ^ a b c andykt. "Caramba, un simulador de Juego de la vida" . SourceForge .
- ^ [2]
- ^ "Autorreplicación" . 4 espacios proyectivos complejos .
Enlaces externos [ editar ]
- Golly: el acelerador de simulación de autómatas celulares Implementación muy rápida de transición de estado y soporte para JvN, GoL, Wolfram y otros sistemas.
- Constructor universal autorreproductor de von Neumann El código fuente original de Nobili-Pesavento, animaciones y archivos Golly de los replicadores.
- Autómatas celulares de 29 estados de John von Neumann implementados en OpenLaszlo por Don Hopkins
- Un catálogo de autómatas celulares autorreplicantes. Este catálogo complementa el Proc. Automata 2008 volumen.
