¿Cómo se completa la regla 110 Turing?

He leído la página de Wikipedia para la regla 110 en autómatas celulares, y sé más o menos cómo funcionan (un conjunto de reglas decide dónde dibujar el siguiente 1 o 0).

Acabo de leer que están Turing completo, pero ni siquiera puedo entender cómo 'programarías' en la 'regla 110'.

La universalidad es una noción algo informal. Lo que significa más o menos es que para cada función computable hay un "programa" P en el modelo, de modo que "ejecutar" P en cualquier entrada x siempre se "detiene" y "emite" la respuesta correcta. (Tenga en cuenta que las máquinas de Turing no aparecen aquí: son solo un ejemplo de un modelo de cálculo universal).$f$$P$$P$$x$

Las palabras citadas son aquellas que necesitan ser definidas. Para máquinas de Turing:

• Un programa se especifica como una lista de estados, un alfabeto de cinta, un estado inicial, estados finales y transiciones.
• Ejecutar una máquina Turing en una entrada x significa que inicializamos la cinta con una codificación de x y ejecutamos la máquina T en esta cinta de acuerdo con las reglas habituales.$T$ $x$$x$$T$
• Una máquina de Turing se detiene si alcanza un estado final. (Hay algunas variantes aquí).
• Lo que produce la máquina Turing (si se detiene) es el contenido de la cinta.

La regla 110, como modelo de cálculo, debe definirse formalmente de la misma manera. Una definición es razonable si uno puede simular computacionalmente el modelo de cómputo, en el siguiente sentido: hay una función computable tal que para cada programa P y entrada x (ambos codificados como números naturales), S ( P , x ) se detiene si P se detiene en x , y si S ( p , x ) se detiene, entonces su salida es idéntica a la salida de P en x .$S$$P$$x$$S(P,x)$$P$$x$$S(p,x)$$P$$x$

Si tiene curiosidad sobre la configuración particular de la Regla 110 como sistema informático, le sugiero que eche un vistazo al artículo de Matthew Cook que demuestra la universalidad de la Regla 110 (o más bien, de un sistema informático construido alrededor de la Regla 110).

En cuanto a otras reglas, como la Regla 30 y la Regla 90, no sabemos que no son universales. Puede haber sistemas informáticos convincentes construidos alrededor de ellos, lo cual es universal, pero simplemente no tenemos conocimiento de ninguno.

De la prueba de Matthew:

El enfoque que se adopta aquí no es diseñar un nuevo autómata celular, sino tomar el más simple que naturalmente exhibe un comportamiento complejo, y ver si podemos encontrar dentro de ese comportamiento complejo una forma de hacer que haga lo que queremos. No nos ocuparemos directamente de la tabla de búsqueda dada anteriormente, sino que analizaremos el comportamiento que la acción del autómata exhibe naturalmente con el tiempo.

El autor comienza probando que un "sistema de etiquetas" que elimina 2 símbolos en cada paso es universal compilando un programa de máquina de 2 estados. Después de eso, demuestra que un sistema de planeador puede implementar un sistema de etiquetas. Es un proceso paso a paso. Luego, estudia el espacio-tiempo de CA-110 para encontrar los planeadores y asociarlos al sistema de planeador correctamente.

Ahora, para su pregunta: ¿cómo 'programaría' en 'la regla 110'?

1. Busque la máquina de turing de 2 estados más simple y encuentre las cintas de las operaciones básicas OR, AND, XOR, NOT .

2. Compilarlos en el sistema de etiquetas.

3. Compile la implementación del sistema de etiquetas en la implementación del planeador.

4. Adáptelo correctamente a los planeadores CA-110 y tendrá las operaciones básicas en un autómata celular.

$1+1=2$

Una nota a un lado. Los planeadores son estructuras muy especiales. Las operaciones se verán como partículas que se mueven y colisionan (los planeadores), generando una salida diferente dependiendo de cómo estos planeadores comienzan o chocan.