Para celebrar el cumpleaños de Alan Turing, Google publicó un garabato que muestra una máquina. ¿Qué tipo de máquina es el garabato? ¿Puede expresar un lenguaje completo de Turing?
Hay diferencias obvias en la máquina clásica de turing: una cinta finita, restricciones en cómo se puede conectar el estado, ...
El doodle aún estará disponible aquí.
(La pantalla en la parte superior derecha muestra la salida esperada).
La cinta en el medio se divide en cuadrados que pueden contener un espacio en blanco, un cero o uno. La cabeza se coloca sobre uno de los cuadrados y se usa para leer y escribir.
Debajo de la cinta puede ver una flecha verde en la que puede hacer clic para iniciar la máquina. Hay dos líneas de círculos al lado, algunas de las cuales están conectadas. Los llamaré "estados".
Después de que la máquina arranca, se enciende el primer estado a la derecha del botón verde, luego el siguiente a la derecha, y así sucesivamente ... Cada estado contiene uno de los siguientes comandos:
- en blanco = no hacer nada (solo pasar al siguiente estado)
- 1 = escribir uno en la cinta en la posición actual de la cabeza
- 0 = escribir un cero en la cinta en la posición actual del cabezal
- flecha hacia la izquierda = mover la cabeza un paso hacia la izquierda
- flecha hacia la derecha = mover la cabeza un paso hacia la derecha
- condición: si el valor debajo de la cabeza es igual al valor que se muestra en el cuadrado, vaya a la segunda línea de estados. si no, pase al siguiente estado a la derecha
- salto a la izquierda: regrese a un estado anterior (fijo) pero solo en la fila superior [¡Originalmente olvidé esa, gracias @Marzio!]
No hay forma de "superponer" dos saltos (uno sobre otro). La máquina se detiene cuando deja un estado y no hay un estado siguiente a la derecha.
(Después de que la máquina se detiene, el contenido de la cinta se compara con el contenido de la pantalla, pero no considero que sea parte de la funcionalidad prevista de la máquina).
Respuestas:
Asumiendo que:
... por lo tanto, incluso si el Doodle de AT quizás no esté Turing completo (debido al operador de salto solo a la izquierda no superpuesto disponible solo en la primera fila), es lo suficientemente poderoso como para caminar por la delgada línea de (des) capacidad de decisión: - re
EDITAR: GIRAR DOODLE ESTÁ GIRANDO COMPLETO
(Dejo la respuesta anterior arriba, porque no estoy seguro de que esta parte sea correcta :-)
¡Creo que incluso con un solo salto izquierdo no superpuesto, el Doodle de Turing está completo! . La idea (simple) es usar la propia cinta para almacenar el estado actual y usar varias celdas para representar un alfabeto más grande.
Por ejemplo, un TM de 2 estados y 8 símbolos se puede simular usando la siguiente representación de cinta:
El doodle de Turing puede:
La imagen completa está disponible aquí .
fuente
alen turing
. Disfruté leyendo estoEste es un extracto del documento original de Turing "Sobre números computables, con una aplicación al problema de Entscheidungs".
Un buen compañero moderno para el artículo que recomiendo es The Annotated Turing de Charles Petzold.
Como puede ver, Google solo intentó parecerse a una máquina que es muy similar a la descripción de Turing.
EDITAR: Suponiendo que el alfabeto completo de Google TM es el que se muestra al final del juego después de hacer clic en el icono del conejito , y tomando en cuenta el hecho de que está produciendo una secuencia infinita , obtuvo más filas y columnas (por lo que podemos suponer que podemos agregar cualquier ), ha dejado saltos (y también solapamiento saltos izquierda) en cualquier fila , tiene salto condicional e incondicional entre filas adyacentes, creo que es Turing completo .
fuente
En los rompecabezas, se permiten saltos en ambas líneas, pero no pueden superponerse. En el último garabato de secuencia de conejo al final del juego, permiten saltos en cada línea y se pueden anidar entre corchetes para que [()] esté permitido, pero ([)] parece no estar permitido.
Usaré los siguientes supuestos:
Con estos supuestos, la máquina de Doodle de Google se está completando .
Para cada estado TM (excepto el que se detiene) utilizamos 3 líneas de GDM. Cada línea corresponde a un posible símbolo de entrada , 0ϵ 0 1 ϵ 0 1 0 1
El GDM simula el TM de la siguiente manera:
Elija su TM universal favorito e impleméntelo en el procedimiento anterior para obtener un GDM universal.
fuente