El autómata celular de Codd es un autómata celular (AC) 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 AC de von Neumann pero con menos estados: 8 en lugar de 29. Codd demostró que era posible hacer una máquina autorreproductora en su AC, de forma similar al constructor universal de von Neumann , pero nunca dio una implementación completa.
En las décadas de 1940 y 1950, John von Neumann planteó el siguiente problema: [1]
Fue capaz de 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 sencilla con ocho estados. [2] Esto modificó la pregunta de von Neumann:
Tres años después del trabajo de Codd, Edwin Roger Banks mostró un CA de 4 estados en su tesis doctoral que también era capaz de computación y construcción universales, pero nuevamente no implementó una máquina autorreproductora. [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. Una simulación del diseño de Devore se demostró en la tercera conferencia de Vida Artificial en 1992, mostrando los pasos finales de construcción y activación del patrón de descendencia, pero la autorreplicación completa no se simuló hasta la década de 2000 utilizando 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 que las necesarias para la autorreproducción en reglas anteriores, a costa de eliminar la capacidad de computación y construcción universales. [4]
La 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 distintas 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 "extendido" utilizado en la imagen de la parte superior aparece aquí como "70116011".
Codd diseñó un ordenador autorreplicante en el autómata celular, basado en la máquina W de Wang . Sin embargo, el diseño era tan colosal que evadió 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.