Modelo de John von Neumann

   , , ,   

A principios de la década de 1950, von Neumann estudió los mecanismos que debe tener una máquina para que pueda tener la capacidad de construir otra máquina igual a la máquina creadora; de manera que diseñó un autómata celular con esas propiedades. A partir de la fecha de su muerte en 1957, dejó el proyecto sin terminar y desde entonces se han hecho varios intentos de completarlo; uno de los trabajos más destacados de reproducir y completar el trabajo de von Neumann se dio en el año 2000 por un grupo de especialistas en diseño de hardware en el Laboratorio de Sistemas Lógicos del Instituto de Tecnología Federal Suiza.

El constructor universal es uno de los conceptos que von Neumann definió y que es una parte fundamental en el diseño de esa máquina constructor universal, que es capaz de construir cualquier otra máquina constructor universal a partir de su descripción. Este proceso requiere que la descripción del constructor universal incluya su propia descripción, idea que fue tomada de modelos celulares vivos que contienen información de cómo construir otras células del mismo tipo:
  • La descripción muestra las características básicas de la máquina, al estilo de un genoma, que es interpretado para construir una copia del constructor universal.
  • La descripción es literalmente copiada, una vez que ha sido detectada y leída.
Stanislaw Ulam hizo la sugerencia (a von Neumann) de implementar sus ideas en un espacio bidimensional discreto. De manera que el universo creado por von Neumann lo define una matriz bidimensional infinita, cuyas entradas, llamadas células, son máquinas de estados finitos. Después de haber estudiado el modelo con varias opciones, llegó a definir 29 estados y una regla de transición.

Figura 1.3: Esquema de la máquina universal de John von Neumann
Image ca

En la figura 1.3 se muestra el esquema de la máquina autoreproductora diseñada por John von Neumann. El constructor universal está dividido en el control de la cinta (Tape control) y el control de construcción(Construction control); el control de la cinta obtiene la información de la máquina que se va a construir; y el control de construcción interpreta la descripción obtenida y construye el nuevo autómata por medio de un brazo constructor (Constructing arm). Podemos mencionar algunas características que tiene este constructor universal:

  • Universalidad construccional, significa que es capaz de construir cualquier autómata, si cuenta con su descripción.
  • Autoreproducción del constructor universal.
  • Autoreproducción de la máquina universal, ya que el constructor universal está definido con una máquina universal de Turing, y la cinta contiene la información completa.


Tabla 1.2: Espacio de estados de la máquina autoreproductora de von Neumann
Estado recesivo $ U$
Estados sensibles al ambiente $ S_\Theta, S_0, S_1, S_{00}, S_{01}, S_{10}, S_{11}, S_{000}$
Estados de transición ordinarios desactivados $ \uparrow , \downarrow , \leftarrow , \rightarrow$
Estados de transición ordinarios activados $ \Uparrow , \Downarrow , \Leftarrow , \Rightarrow$
Estados de transición especial desactivados $ \uparrow\cdot , \downarrow\cdot , \dot{\leftarrow}, \dot{\rightarrow}$
Estados de transición especial activados $ \Uparrow\cdot , \Downarrow\cdot , \dot{\Leftarrow} , \dot{\Rightarrow}$
Estado confluente desactivado $ C_{00}$
Estados confluentes activados $ C_{01}, C_{10}, C_{11}$

Cada célula del autómata puede tener uno de 29 posibles estados. Esos estados no son catalogados de manera numérica como usualmente se propone en las máquinas finitas de estados; la manera en que los diferentes estados son identificados tiene mucho que ver con su funcionalidad. En la tabla 1.2 se describen los conjuntos de estados posibles para cada célula. Enseguida una descripción de esos conjuntos de estados.

Una célula en el estado recesivo $ U$ no influye en otras células. Este estado se aplica a células que no se usan, ni en la descripción de la máquina, ni en el proceso de construcción.

Las células tienen 16 estados que permiten la transmisión de información entre células que no están en estado recesivo. Cada uno de estos estados de transmisión tienen una de cuatro direcciones: norte, sur, este y oeste; hay una distinción entre estados activos o inactivos. Además, se pueden distinguir estados de transmisión ordinarios y de propósito especial que propagan diferentes tipos de activación.

Los estados de transmisión ordinarios propagan activaciones ordinarias en su dirección de salida, por su parte, los estados de transmisión especial, también propagan activaciones especiales en su dirección de salida. Las propagaciones ordinarias introducen un retardo de un paso de tiempo en la propagación de la activación y actúan como una compuerta OR. Un estado cambia a activo si recibe una señal de activación ordinaria o especial desde uno de sus tres lados confluentes.

Los 4 estados confluentes se usan para transmitir activaciones, funcionan como compuertas AND, generan un retardo de dos tiempos en la transmisión de una activación y pueden dividir el flujo de transmisión, comportándose como un distribuidor. Un estado confluente puede ser $ C_{10}$ o $ C_{11}$ cuando todas las células vecinas estén en estado de transmisión ordinaria dirigidas hacia ellas, si cualquiera está en estado activado.

Figura 1.4: Evolución de los estados de transmisión y confluentes de la máquina de von Neumann
Image vnStatesEvols

En la figura 1.4 se pueden apreciar en 6 pasos de tiempo, las evoluciones del autómata celular de von Neumann en diferentes situaciones:

  • en la columna a se muestra cómo se propagan las señales de activación en actividades ordinarias,
  • en las columnas b y c se muestran las actividades de los estados confluentes, comportándose como compuertas AND (columna b) y OR (columna c).
Los 8 estados restantes se usan para construir los procesos, que también se llaman procesos dirigidos, que como excepción, sí pueden crear estados recesivos o cambiar de un estado recesivo a estados de transmisión no activados o a estados confluentes. Estos estados se llaman estados sensibles aunque cambian de estado en una unidad de tiempo.

Una célula que se encuentre en estado recesivo $ U$ puede cambiar su estado al estado sensible $ S_\Theta$ si recibe una señal de activación ordinaria o especial por alguno de sus lados, luego puede cambiar al estado sensible $ S_0$ si no recibe ninguna señal de activación, o a $ S_1$ en caso de que sí reciba.

Figura 1.5: Proceso de construcción de la máquina de von Neumann
Image constProc

La figura 1.5 muestra el ciclo constructivo en que pueden encontrarse las células en el autómata, mientras se encuentren en uno de esos 9 estados desactivados. Una célula que se encuentre en un estado sensible no ejerce influencia en sus vecinos.

Finalmente se describe una manera de cambiar el estado de transmisión o confluente a un estado recesivo, y se puede hacer de dos maneras: enviando una activación especial por uno de los 4 lados de un estado de transmisión ordinaria o de un estado confluente; y la otra manera es enviar una activación ordinaria por uno de los cuatro lados de un estado de transmisión especial.