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.
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 solo». 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
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
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]
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 se suponía simplemente 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]
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.
{{citation}}: CS1 maint: varios nombres: lista de autores ( enlace )