programming languages - programming - ¿Alguien puede explicar la Regla 110 de la manera más simple posible?

maquina electromecanica de turing

Question

No puedo comprender lo que dice el artículo de Wikipedia o la respuesta aquí . ¿Puede alguien explicar la Regla 110 en términos simples? ¿Cómo garantiza la integridad de Turing?

Answer 1

En 1970 John Conway ha inventado Juego de la Vida .

Desde entonces, creo que casi todos los programadores intentaron escribir su implementación; ciertamente lo hice hace mucho tiempo, y fue muy divertido.

Este juego es en realidad un autómata celular , que establece reglas simples entre generaciones de celdas en un plano bidimensional infinito. Por ejemplo, si en la generación actual, la celda tiene menos de 2 vecinos vivos (valor de bit 1 ), entonces debería morir en la siguiente generación de soledad. Si tiene más de 3 vecinos vivos, debe morir de hacinamiento. Si la celda vacía (valor de bit 0 o muerta) tiene exactamente 3 vecinos, hará que nazca (se convierta en 1 ).

Desde entonces, se descubrió que Juego de la vida es sorprendentemente complejo: puede generar muchos patrones muy complejos que continúan evolucionando. Además, se demostró que es Turing-complete, es decir, puede codificar algoritmos arbitrariamente complejos utilizando la combinación de células de partida como un programa, y ​​la combinación final como resultado. Sin embargo, tomó pocos años para encontrar la forma de generar realmente formas complicadas, como planeadores o armas .

Ahora volvamos a lo que es la regla 110. En pocas palabras, la regla 110 es una variación unidimensional de Game of Life.

110 es solo una representación numérica decimal de la cadena binaria 01101110, que es una forma corta del sistema de reglas de cómo la actual generación de celdas (bits) se convertirá en la siguiente , similar al sistema de reglas de Juego de la Vida de celdas que mueren de soledad o hacinamiento y están Nacido de tener exactamente tres vecinos.

Al igual que en Game of Life, se ha demostrado que la regla 110 está completa en Turing. Puede codificar un algoritmo arbitrariamente complejo utilizando la combinación de celdas de inicio (bits) como su programa, y ​​la combinación de bits final como resultado.

Answer 2

Intentaré elaborar: no creo que esté buscando más detalles de la prueba que ya es bastante compleja en el artículo, aunque claramente omite muchos detalles.

Para citar el artículo, cite : "En un autómata celular elemental, un patrón unidimensional de 0 y 1 evoluciona según un conjunto simple de reglas. El hecho de que un punto en el patrón sea 0 o 1 depende de la nueva generación de su valor actual, así como el de sus dos vecinos. El autómata de la Regla 110 tiene el siguiente conjunto de reglas ... " (vea la tabla de wikipedia que sigue)

El punto de partida, que puede ver como los datos, pero que puede tomarse como una representación del código (representando el código como datos es necesario para cualquier prueba de que Turing está completo; esto se remonta a los resultados originales de Turing), es una secuencia de 0 y 1, a menudo, pero no necesariamente, rodeados en ambos lados por celdas que contienen solo 0. La regla 110 muestra cómo evoluciona esa secuencia. Por ejemplo, si hay un patrón de 3 1 en una fila, el 1 medio "morirá" (se convertirá en un 0) en la siguiente fila. Lo que suceda con sus dos vecinos depende de cómo el patrón se extienda más allá de ellos. Los diagramas triangulares que ve son una representación gráfica de la evolución del autómata desde el estado original, codificando 1 como negro y 0 como blanco y representando la evolución desde arriba hacia abajo. El estado inicial a menudo es muy corto en longitud para mostrar cómo los patrones muy complejos pueden evolucionar desde los estados iniciales simples.

Dos características inusuales de la prueba de integridad de Turing son que, en primer lugar, parece muy poco probable que una regla tan simple pueda hacer todo lo que su lenguaje de programación favorito podría hacer, y en segundo lugar, lo que hace que el primer hecho sea menos sorprendente, es que la prueba Requiere un fondo de repetición infinitamente largo en el que trabajar su magia. Sin embargo, no puedo ver nada fundamentalmente deshonesto sobre esto; no más que suponer una cinta en blanco potencialmente infinita o semi-infinita, como lo hizo originalmente Turing.

Para comprender la prueba correctamente, debería conocer cómo se codifican los datos (y, posteriormente, el código) en el patrón de inicio, y también parece que la familiaridad con los sistemas de etiquetas cíclicas ayudaría enormemente. No soy la persona para explicar eso.

Aunque parezca más difícil entender la situación con un autómata celular 2-D, como el "Juego de la vida" de Conway, me pareció instructivo jugar con ese juego, al estudiar "planeadores", "planeadores" y "trufas". Y otras construcciones divertidas. (Un tren soplador construye pistolas planeador y una pistola planeador dispara planeadores). Estos también se pueden utilizar para establecer la integridad de Turing para este autómata.

También puede encontrar la página de conversación informativa (no está solo para no entender el punto, vea la entrada que comienza "las imágenes no tienen ningún sentido para mí ..." ).

Answer 3

Mi intento de una explicación sucinta de los términos del laico:

• La regla 110 es un autómata celular elemental: una regla para transformar un patrón finito de 1 y 0 en otro patrón de 1 y 0.
• Cuando la Regla 110 se aplica de forma iterativa en ciertas secuencias de bits de entrada, surgen patrones dependiendo de las subsecuencias encontradas en los bits de entrada. Dadas las iteraciones suficientes, puede suceder lo siguiente:
  • La subsecuencia original aparece en la misma ubicación que en la entrada original.
  • La subsecuencia original se conserva, pero se "mueve" a una ubicación diferente en el campo de bits.
  • Dos subsecuencias que se mueven una hacia la otra interactúan y se "pasan" una a la otra.
  • Dos subsecuencias se combinan para crear una nueva subsecuencia.
• A diferentes subsecuencias se les puede dar un significado simbólico como ''1'', ''0'', ''pulso de reloj'' o ''regla de producción'' que corresponden a los elementos de un sistema de etiquetas cíclicas.
• Con muchas iteraciones de la Regla 110 en un campo de bits de entrada cuidadosamente construido, la interacción de las subsecuencias simula el comportamiento de un sistema de etiquetas cíclicas.
• Se puede usar un sistema de etiquetas cíclicas para simular una máquina universal de Turing. Así, un sistema de etiquetas cíclico es Turing-completo.
• Como la Regla 110 puede simular un sistema de etiquetas cíclico, también es Turing-complete.

Answer 4

Una implementación en python:

(Se recomienda: los programadores reales de Python te matarán por esto)

import time

seed = raw_input("Feed me a string! (At least 3 characters long please)/n>")

lastline = ''>''
iterator = 0

while (iterator<len(seed)):
    temp = (ord(seed[iterator]))%2
    if (temp == 1):
        lastline += ''#''
    else:
        lastline += '' ''
    iterator += 1

stop = 0
while (stop != 1): #Keep printing as long as CTRL-C isn''t pressed
    #dummy = raw_input(lastline)
    print lastline
    iterator = 0
    nextline = ''>''


    while (iterator<len(seed)):    #Convert entire string

        if (len(seed) < 3): # if wrong
            print "You had ONE JOB!"
            stop = 1

        elif (iterator == 0): # if at start
            if (lastline[1] == '' ''):
                nextline += '' ''
            else:
                nextline += ''#''

        elif (iterator+1 == len(seed)): # if at end
            if (lastline[iterator+1] == '' ''):
                nextline += '' ''
            else:
                nextline += ''#''

        else: #if in middle
            if (lastline[iterator] == ''#'' and lastline[iterator+1] == ''#'' and lastline[iterator+2] == ''#''): #111
                nextline += '' ''
            elif (lastline[iterator] == ''#'' and lastline[iterator+1] == ''#'' and lastline[iterator+2] == '' ''): #110
                nextline += ''#''
            elif (lastline[iterator] == ''#'' and lastline[iterator+1] == '' '' and lastline[iterator+2] == ''#''): #101
                nextline += ''#''
            elif (lastline[iterator] == ''#'' and lastline[iterator+1] == '' '' and lastline[iterator+2] == '' ''): #100
                nextline += '' ''
            elif (lastline[iterator] == '' '' and lastline[iterator+1] == ''#'' and lastline[iterator+2] == ''#''): #011
                nextline += ''#''
            elif (lastline[iterator] == '' '' and lastline[iterator+1] == ''#'' and lastline[iterator+2] == '' ''): #010
                nextline += ''#''
            elif (lastline[iterator] == '' '' and lastline[iterator+1] == '' '' and lastline[iterator+2] == ''#''): #001
                nextline += ''#''
            else: # (lastline[iterator-1] == '' '' and lastline[iterator] == '' '' and lastline[iterator+1] == '' ''): #000
                nextline += '' ''

        iterator += 1

    lastline = nextline
    time.sleep(0.02)