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 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 [ ¿según quién? ] , se considera fundamental para la teoría de los autómatas , los sistemas complejos y la 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 informáticas) también era central para la teoría biológica , permitiéndonos "disciplinar nuestros pensamientos sobre las máquinas, tanto naturales y artificiales." [5]
El objetivo de Von Neumann, como lo 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 se debe cruzar para que las máquinas puedan evolucionar. [4] Su respuesta fue especificar una máquina abstracta que, cuando se ejecutara, 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í 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 fotocopiadora universal que puede hacer copias de cualquier descripción. Después de que se ha utilizado el constructor universal para construir una nueva máquina codificada en la descripción, se utiliza la fotocopiadora 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. Fundamentalmente, la máquina autorreproductora puede evolucionar acumulando mutaciones de la descripción, no de la máquina misma, 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 celdas, cada una de las cuales puede estar en uno de 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 rigen estas actualizaciones son idénticas para todas las células.
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 "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 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 algún otro lugar de la cuadrícula de celdas. La descripción no puede contener instrucciones para construir una cinta descriptiva igualmente larga, del mismo modo que un contenedor no puede contener un contenedor del mismo tamaño. Por lo tanto, la máquina incluye una fotocopiadora independiente 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.
Tradicionalmente se ha entendido que el diseño de Von Neumann es 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. Los ejemplos incluyen crecimiento trivial similar a un cristal , replicación de plantillas y 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 las estructuras 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 Evoloop , son algo evolucionables pero aún no admiten una evolución abierta. Por lo general, los replicadores simples no contienen completamente la maquinaria de construcción, existiendo un grado en el que el replicador es información copiada por el entorno que lo rodea. 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 . El tema de la contribución ambiental a la replicación está algo abierto, ya que existen diferentes concepciones sobre 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 tanto un componente activo del mecanismo de construcción en la reproducción, como 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 fotocopiadora 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 de 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 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 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 puede evolucionar mediante selección natural . [4] Como dijo Brenner:
Turing inventó la computadora con programas almacenados 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 y 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 arte del constructor en uno". Esto está mal. El guión del código 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 lo 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 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 esto es lógicamente posible. Al utilizar una arquitectura que separa un constructor programable (“universal”) de propósito general 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 así desarrollar máquinas más complejas (la imagen a continuación ilustra esta posibilidad). Este es un resultado muy importante, ya que antes 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 está definida de manera similar por una "cabeza" de máquina determinada por el estado y separada de una cinta de memoria. [5]
En la práctica, cuando consideramos la implementación particular de autómatas que persiguió Von Neumann, concluimos que no produce mucha dinámica evolutiva porque las máquinas son demasiado frágiles: la gran mayoría de las perturbaciones causan 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 (las descripciones de) los subsistemas no involucrados en la autorreproducción en sí, tal como lo conceptualiza el autómata adicional D que consideraba que realiza todas las funciones no directamente. involucrado en la reproducción (ver Figura arriba con el Sistema de Autómatas de Autorreplicació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 Copier ( B ) no evolucionarían, dejando toda la evolución (y el crecimiento de la complejidad) al autómata D. [4] En su obra inacabada, Von Neumann también considera brevemente los conflictos y las interacciones entre sus máquinas autorreproductoras, para comprender 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 los 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 (inactivas).
Arthur Burks y otros ampliaron el trabajo de von Neumann, brindando un conjunto de detalles mucho más claro y completo sobre el diseño y funcionamiento del autorreplicador de von Neumann. El trabajo de JW Thatcher es particularmente digno de mención, 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 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 de la CA original de 29 estados, pero ninguno capaz de replicarse completamente: la configuración no puede duplicar su cinta ni puede activar su descendencia; la configuración sólo puede construir. [8] [9]
En 2004, D. Mange et al. informó 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 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 se autorreplican dentro de la CA original de 29 estados de von Neumann. [9] Buckley afirma que el cruce de señales dentro de 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 replicarse, para ser capaz (en teoría) de hacer más de una copia. Tal como se publicó, el diseño de Nobili-Pesavento de 1995 no cumple con este requisito, pero el diseño de Nobili de 2007 sí; lo mismo ocurre con las configuraciones de Buckley.
En 2009, Buckley publicó con Golly una tercera configuración para autómatas celulares de 29 estados de von Neumann, que pueden realizar una autorreplicación holística o una 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 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 asíncrono, en lugar de sobre un autómata celular síncrono.[12] [13]
Según la definición de von Neumann, la construcción universal implica únicamente la construcción de configuraciones pasivas. Como tal, el concepto de construcción universal no constituía más que un recurso literario (o, en este caso, matemático). Facilitó otras pruebas, como que una máquina bien construida puede emprender 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 proporcionadas 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 ejecutarse 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 toma 63 mil millones de pasos de tiempo para replicar. Un simulador que funcione a 1.000 pasos por segundo tardaría más de dos 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 toma sólo unos minutos, aunque se requiere una cantidad significativa de memoria.
{{citation}}: Mantenimiento CS1: varios nombres: lista de autores ( enlace )