El autómata celular de Codd es un autómata celular (CA) ideado por el científico informático británico Edgar F. Codd en 1968. Fue diseñado para recrear la universalidad de cálculo y construcción del CA de von Neumann pero con menos estados: 8 en lugar de 29. Codd mostró que era posible hacer una máquina auto-reproducible en su CA, de manera similar al constructor universal de von Neumann , pero nunca dio una implementación completa.
Historia
En las décadas de 1940 y 1950, John von Neumann planteó el siguiente problema: [1]
- ¿Qué tipo de organización lógica es suficiente para que un autómata pueda reproducirse?
Consiguió construir un autómata celular con 29 estados, y con él un constructor universal . Codd, basándose en el trabajo de von Neumann, encontró una máquina más simple con ocho estados. [2] Esta pregunta modificada de von Neumann:
- ¿Qué tipo de organización lógica es necesaria para que un autómata pueda reproducirse?
Tres años después del trabajo de Codd, Edwin Roger Banks mostró un CA de 4 estados en su tesis de doctorado que también era capaz de computación y construcción universales, pero nuevamente no implementó una máquina de autorreproducción. [3] John Devore, en su tesis de maestría de 1973, modificó las reglas de Codd para reducir en gran medida el tamaño del diseño de Codd, en la medida en que pudiera implementarse en las computadoras de esa época. Sin embargo, la cinta de datos para la autorreplicación era demasiado larga; Más tarde, el diseño original de Devore pudo completar la replicación con Golly . Christopher Langton hizo otro ajuste al autómata celular de Codd en 1984 para crear los bucles de Langton , exhibiendo autorreplicación con muchas menos células de las necesarias para la autorreproducción en reglas anteriores, a costa de eliminar la capacidad de cálculo y construcción universales. [4]
Comparación de conjuntos de reglas de CA
California | número de estados | simetrías | computación y construcción universal | tamaño de la máquina de reproducción automática |
---|---|---|---|---|
von Neumann | 29 | ninguno | sí | 130,622 células |
Codd | 8 | rotaciones | sí | 283,126,588 células [5] |
Devorar | 8 | rotaciones | sí | 94,794 células |
Banks IV ( Autómata celular Banks IV ) | 2 - 4 [6] [7] | rotaciones y reflexiones | sí | En algún lugar alrededor de 100.000.000.000 de células |
Bucles de Langton | 8 | rotaciones | No | 86 celdas |
Especificación
El CA de Codd tiene ocho estados determinados por un vecindario de von Neumann con simetría rotacional.
La siguiente tabla muestra los trenes de señales necesarios para realizar diferentes tareas. Algunos de los trenes de señales deben estar separados por dos espacios en blanco (estado 1) en el cable para evitar interferencias, por lo que el tren de señales 'extender' utilizado en la imagen de la parte superior aparece aquí como '70116011'.
propósito | tren de señales |
---|---|
ampliar | 70116011 |
extend_left | 4011401150116011 |
extender_derecha | 5011501140116011 |
retraer | 4011501160116011 |
retract_left | 5011601160116011 |
retract_right | 4011601160116011 |
Marcos | 701160114011501170116011 |
borrar | 601170114011501160116011 |
sentido | 70117011 |
gorra | 40116011 |
inject_sheath | 701150116011 |
inject_trigger | 60117011701160116011 |
Constructor de computadoras universal
Codd diseñó una computadora autorreplicante en el autómata celular, basada en la máquina W de Wang . Sin embargo, el diseño fue tan colosal que eludió la implementación hasta 2009, cuando Tim Hutton construyó una configuración explícita. [5] Hubo algunos errores menores en el diseño de Codd, por lo que la implementación de Hutton difiere ligeramente, tanto en la configuración como en el conjunto de reglas.
Ver también
Referencias
- ↑ von Neumann, John; Burks, Arthur W. (1966). " Teoría de los autómatas que se reproducen a sí mismos " . www.walenz.org. Archivado desde el original el 5 de enero de 2008 . Consultado el 28 de enero de 2012 .
- ^ Codd, Edgar F. (1968). Autómatas celulares . Academic Press, Nueva York.
- ^ Banks, Edwin (1971). Procesamiento y Transmisión de Información en Autómatas Celulares . Tesis doctoral, MIT, Departamento de Ingeniería Mecánica.
- ^ Langton, CG (1984). "Autorreproducción en autómatas celulares" (PDF) . Physica D: Fenómenos no lineales . 10 (1-2): 135-144. doi : 10.1016 / 0167-2789 (84) 90256-2 . hdl : 2027,42 / 24968 .
- ^ a b Hutton, Tim J. (2010). "Computadora autorreplicante de Codd" (PDF) . Vida artificial . 16 (2): 99-117. doi : 10.1162 / artl.2010.16.2.16200 . PMID 20067401 .
- ^ http://www.bottomlayer.com/bottom/banks/banks_commentary_03.htm
- ^ http://www.bottomlayer.com/bottom/banks/banks_thesis_1971.pdf
enlaces externos
- El repositorio de tablas de reglas tiene la tabla de transición para la CA de Codd .
- Golly : admite la CA de Codd junto con Game of Life y otros conjuntos de reglas.
- Descarga la máquina completa (13MB) y más detalles.
- [1] muestra más sobre Banks IV.