Fusil de asalto Von Neumann

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 30 de octubre de 2021; las comprobaciones requieren 2 ediciones .

El autómata celular de von Neumann  es un autómata celular desarrollado por John von Neumann con la ayuda de Stanisław Ulam para investigar la posibilidad de crear máquinas autorreplicantes .

Definición

Configuración

En general, un autómata celular es un conjunto ordenado de autómatas finitos que intercambian información con autómatas vecinos. En un autómata celular de von Neumann, las células se ordenan en una red rectangular bidimensional e interactúan con cuatro células directamente adyacentes que forman una vecindad de von Neumann . Se supone que la cuadrícula tiene un tamaño infinito en ambas direcciones y las celdas son idénticas en términos de reglas de transición. El cambio en los estados de todas las células ocurre sincrónicamente.

Estados

Cada máquina de estado en el espacio de von Neumann puede tomar uno de los 29 estados:

1. estado base U
2. estados transitivos (o sensibles)
   1. S
   2. S0 _
   3. S00 _
   4. S01 _
   5. S000 _
   6. S1 _
   7. S 10
   8. S 11
3. estados confluentes
   1. C00 _
   2. C 10
   3. C01 _
   4. C 11
4. estado de transmisión normal
   1. T 00 derecha
   2. T 01 arriba
   3. T 02 izquierda
   4. T 03 abajo
5. estado de transmisión especial
   1. T 10 derecha
   2. T 11 arriba
   3. T 12 izquierda
   4. T 13 abajo

Cada uno de los estados de transmisión (8 estados) también se caracteriza por excitación/no excitación (flechas verde/azul), lo que da un total de 16 estados de transmisión. El estado excitado transfiere datos a una velocidad de 1 bit por reloj. Los estados confluentes tienen un retraso de un ciclo y, por lo tanto, pueden almacenar 2 bits de información.

Reglas de transición de estado de transferencia

El flujo de información entre celdas está determinado por la propiedad de directividad. Se aplican las siguientes reglas:

• Los estados de transmisión aplican un operador OR a las señales de entrada, es decir, una celda en un estado de transmisión (regular o especial) se excitará en el reloj t+1 si alguna de las señales de entrada se excita en el reloj t
• Los estados se transfieren entre las células transmisoras de acuerdo con la propiedad direccional.
• Los estados de transmisión ordinarios y especiales son "antagonistas":
  • Si la celda A en el reloj t en el estado de transmisión excitado normal apunta a la celda B en cualquier estado de transmisión especial , entonces en el reloj t+1 la celda B irá al estado base U. El estado de transmisión especial será "destruido".
  • Un evento similar ocurrirá si una celda en un estado de transmisión especial apunta a una celda de transmisión normal.

Reglas para la transición de estados confluentes

Las siguientes reglas se aplican a los estados confluentes:

• Las celdas confluentes no transfieren datos entre ellas.
• Las celdas confluentes reciben entradas de una o más celdas transmisoras normales y las proporcionan a las celdas transmisoras (regulares o especiales) que no apuntan a la celda actual.
• Los datos no se transmiten en la dirección opuesta a la celda transmisora.
• Los datos almacenados por una celda confluente se pierden si no tiene celdas transmisoras adyacentes (que no apunten a ella).
• Las celdas confluentes sirven como puentes entre las celdas transmisoras convencionales y las especializadas.
• Las celdas confluentes aplican el operador AND a las señales de entrada.
• Las celdas confluentes retrasan la señal un ciclo más que las celdas transmisoras convencionales.

Reglas de transición

En el estado inicial, la mayor parte del espacio celular está "vacío", es decir, lleno de células en estado U. Habiendo recibido una señal de entrada de una celda transmisora, una celda vecina en el estado U entra en un estado de tránsito, pasa por una serie de estados y termina en uno de los estados transmisores o confluentes. Este estado final está determinado por la secuencia de señales de entrada. Es decir, los estados de tránsito pueden considerarse como puntos de bifurcación en el camino desde el estado base hasta los estados transmisor y confluente. En las siguientes reglas, la secuencia de señales de entrada se indica entre paréntesis mediante una cadena binaria:

• la celda en el estado base U , habiendo recibido una señal, pasa al estado S (1)
• celda en estado S , sin recibir señal, pasa al estado S 0 (10)
  • celda en estado S 0 , sin recibir señal, pasa a S 00 (100)
    • la celda S 00 , sin recibir señal, pasa a S 000 (1000)
      • la celda S 000 , sin recibir señal, pasa a T 00 (10000)
      • la celda S 000 , habiendo recibido una señal, va a T 01 (10001)
    • la celda S 00 , habiendo recibido una señal, va a T 02 (1001)
  • la celda S 0 , habiendo recibido una señal, va a S 01 (101)
    • la celda S 01 , sin recibir señal, pasa a T 03 (1010)
    • la celda S 01 , habiendo recibido una señal, va a T 10 (1011)
• la celda S , habiendo recibido una señal, va a S 1 (11)
  • la celda S 1 , sin recibir señal, pasa a S 10 (110)
    • la celda S 10 , sin recibir señal, pasa a T 11 (1100)
    • la celda S 10 , habiendo recibido una señal, va a T 12 (1101)
  • la celda S 1 , habiendo recibido una señal, va a S 11 (111)
    • la celda S 11 , sin recibir señal, pasa a T 13 (1110)
    • la celda S 11 , habiendo recibido una señal, va a C 00 (1111)

Romper las reglas

• Una señal de entrada de una celda de transmisión especial, recibida por una celda en un estado de transmisión confluente o normal, pone a esa celda en el estado básico.
• Una señal de entrada de una celda transmisora ​​normal recibida por una celda transmisora ​​especial convierte esa celda en la celda base.

Modificaciones

Una de las variedades del autómata de von Neumann es el autómata de Nobili , en el que se introducen estados adicionales para dotar de memoria y la posibilidad de cruzar señales sin interferencias, para lo que se aprovecha la posibilidad de almacenar información por grupos de células. La última función requiere tres estados adicionales, razón por la cual el autómata Nobili tiene 32 estados, no 29. Es invención de Renato Nobili ( italiano:  Renato Nobili ), profesor de física en la Universidad de Padua , Italia . Von Neumann excluyó deliberadamente los estados destinados a los cruces de señales.

El estado confluente se cambia de tal manera que se transmiten dos señales que llegan simultáneamente independientemente una de la otra, o se almacenan y transmiten señales de entrada con un retardo.

Otra variación es el autómata de Hutton , que permite la replicación de estructuras de anillos (ver bucles de Langton en inglés  ) .

Véase también

• maquina von neumann

Enlaces

• J. von Neumann, Teoría de los autómatas que se reproducen a sí mismos. M.: Mir, 1971.

El juego de la vida de Conway y otros autómatas celulares
Clases de configuración	Oscilador Rastrillo Naturaleza muerta Astronave Pistola Locomotora devorador Reflector criador Longevidad Marcador de posición Jardín del Edén
Configuraciones	Planeador Bloquear R-pentominó Pentadecatlón
Términos	barrio moore barrio Von Neumann velocidad de la luz
Otras naves espaciales en una red bidimensional	Natural Día y noche Vida sin muerte buena vida semillas Otro modelo de pila de arena Fusil de asalto Von Neumann Mundo de alambre Hormiga Langton Criaturas Gusanos de Paterson
Nave espacial unidimensional	KA elemental ( Regla 30 regla 90 Regla 110 Artículo 184 ) Problema de sincronización del tirador
Software y algoritmos	Caramba Celebración de hashlife
investigadores de ka	John Horton Conway proyecto de ley gosper Martín Gardner Richard Kenneth Guy Brian Silverman John Wilder Tukey Juan von Neumann eduardo moore esteban wolframio