El autómata celular de Codd

El autómata celular de Codd es un autómata celular (CA) ideado por el informático británico Edgar F. Codd en 1968. Se diseñó para recrear el cálculo - y la universalidad de la construcción de CA de von Neumann, pero con menos estados: 8 en vez de 29. Codd mostró que era posible hacer una máquina que se autoreproduce en su CA, de un modo similar hacia el constructor universal de von Neumann, pero nunca dio una realización completa.

Historia

En los años 1940 y años 50, John von Neumann planteó el problema siguiente:

¿Era

capaz de construir un autómata celular con 29 estados, y con ello un constructor universal. Codd, añadiendo el trabajo de von Neumann, encontró una máquina más simple con ocho estados. Esto modificó la pregunta de von Neumann:

¿

Tres años después del trabajo de Codd, Edwin Roger Banks mostró CA de 4 estados en su Tesis doctoral que también era capaz de cálculo universal y construcción, pero otra vez no puso en práctica una máquina que se autoreproduce. John Devore, en su 1973 tesis de maestros, pellizcó las reglas de Codd de reducir enormemente la talla del diseño de Codd, hasta el punto de que se podría poner en práctica en los ordenadores de ese tiempo. Sin embargo, la cinta de datos para la autoréplica era demasiado larga; el diseño original de Devore estaba más tarde capaz de completar la utilización de la réplica Golly. Christopher Langton hizo otro pellizco al autómata celular de Codd en 1984 para crear los lazos de Langton, exponiendo la autoréplica con mucho menos células que esto necesario para la autoreproducción en reglas anteriores, a costa de quitar la capacidad de cálculo universal y construcción.

Comparación de CA rulesets

Especificación

CA de Codd tiene 8 estados y la vecindad de von Neumann con la simetría rotatoria.

La mesa debajo de espectáculos los trenes de la señal tenía que llevar a cabo tareas diferentes. Algunos trenes de la señal tienen que ser separados por dos impresos (declare 1) en el alambre para evitar la interferencia, por tanto el tren de la señal 'ampliar' usado a la imagen encima aparece aquí como '70116011'.

Constructor del ordenador universal

Codd diseñó un ordenador que se autoreproduce en el autómata celular, basado en la W-máquina de Wang. Sin embargo, el diseño era tan colosal que evadió la realización hasta 2009, cuando Tim Hutton construyó una configuración explícita. Había algunos errores menores en el diseño de Codd, por tanto la realización de Hutton se diferencia ligeramente, tanto en la configuración como en el ruleset.

Véase también

Enlaces externos



Buscar