algorithm - programming - que es turing completa

¿Qué se entiende por "encajar"?

Question

Mientras leía las reseñas de "Un nuevo tipo de ciencia" de Stephen Wolfram en Amazon, encontré la siguiente declaración:

Todos los estudiantes de ciencias de la computación (CS) conocen a Dovetailer, un programa muy simple de 2 líneas que enumera y ejecuta sistemáticamente todos los programas posibles para una computadora universal como Turing Machine (TM).

¿Alguien puede dar un "programa simple de 2 líneas" que ilustre "dovetaling"?

Answer 1

Bueno, un programa de máquina de turing es, de hecho, una tabla (estado x símbolo de la cinta), por lo que el programa simplemente enumera todas las tablas posibles. como eso:

for(int symbol_count = 1; true; symbol_count++)
{
for(int state_count = 1; state_count <= symbol_count; state_count++)
{
gen_table(symbol_count, state_count);
}
}

donde gen_table enumera todas las tablas de acción de tal tamaño (por ejemplo, tratar la tabla como un número grande y los estados como dígitos). Eso es más largo que dos líneas en C, probablemente, Wolfram usó algún otro lenguaje más poderoso.

Answer 2

Un estudiante de CS generalmente tiene a mano una codificación de máquinas de Turing a enteros, que necesitan cuando escriben su software. El emulador de la máquina de Turing toma como entrada una máquina de Turing y escribe como salida la salida de la máquina especificada. Es posible disponer que esta codificación tenga la propiedad de que cada entero es un programa diferente y válido.

Así que el ingenuo de dos líneas para enumerar y ejecutar todos los programas sería:

for (int i = 0; ; ++i)
printf("%d: %d/n", i, universal_turing_machine(i));

Esto ignorando que en C, int es un tipo de ancho fijo.

Ahora, obviamente, el programa no llega muy lejos, porque muy pronto llega a una i por la cual la máquina de Turing correspondiente no se detiene. Entonces, el truco de "cola de milano" es ejecutar una instrucción desde la primera máquina, luego una instrucción desde la segunda y otra desde la primera, luego una desde la tercera, la segunda, la primera, y así sucesivamente. Como cada máquina se detiene (si se detiene), por supuesto, puede detener el procesamiento o simplemente sentarse sin hacer nada en sus "intervalos de tiempo".

No sé muy bien cómo es eso de "dos líneas", considerando el cambio de contexto necesario entre las máquinas de Turing en cada paso. Pero el programa de cola de milano tiene un uso teórico (y probablemente no tiene uso en la práctica). Una cosa interesante de esto es que tiene la siguiente propiedad:

Si existe un programa P que resuelve un problema X en tiempo polinomial (y proporciona la información necesaria para probar la solución), entonces el programa de cola de milano resuelve X en tiempo polinomial.

La prueba es bastante simple (lleva un tiempo constante equivalente a ejecutar P*(P-1)/2 instrucciones de Turing para llegar al inicio del programa correcto P [*], y luego solo un tiempo polinomial peor para ejecutarlo de lo que tomaría para ejecutar ese programa por su cuenta). La nueva declaración de la propiedad que me parece más divertida es:

Si P = NP, entonces ya conocemos soluciones polinomiales para todos los problemas NP-completos.

Todavía no hemos demostrado que sean polinomiales. Una prueba de P = NP completaría esa prueba sin mostrar realmente cuál de los subprogramas es el que resuelve el problema. El propio programa de cola de milano puede darse cuenta de eso a medida que avanza: cuando cada máquina se detiene, usa el tiempo polinomial "¿es esto una solución para X para la entrada original?" Algoritmo implícito por X siendo NP. Si se trata de una solución, de salida y de alto. Si no lo es, sigue adelante.

[*] Bueno, quizás tiempo lineal, ya que a medida que creas cada nueva Máquina de Turing virtual, necesitas darle una copia de la entrada para trabajar. También en la práctica, los cambios de contexto probablemente no sean de tiempo constante, así que llámalo de forma cuadrática. Mano-onda-mano-onda es polinomio ¿OK?