¿Demostrando que el problema de parada es indecidible sin reducciones ni Diagonalización?

Question

Actualmente estoy enseñando una clase sobre la computabilidad y recientemente cubrió la prueba de que la detención problema es indecidible. Sé de tres grandes a prueba de vías que se pueden utilizar aquí:

1. Diagonalización - demostrar que si la detención problema se decidable, se podría construir una máquina que, si se ejecutan en sí mismo, se ve obligado a hacer lo contrario de lo que dice que hará.
2. La recursividad teorema de - mostrar que si la detención problema se decidable, entonces se podría construir una máquina que obtiene su propia descripción, se determina si se detiene en su entrada, luego hace todo lo contrario.
3. Reducción de - mostrar que algunas de las otras indecidible problema se reduce a detener el problema.

Aunque estoy totalmente de entender estas pruebas y piensan que son matemáticamente hermoso, muchos de mis estudiantes están teniendo problemas con ellos, porque ninguna de las pruebas directamente a la dirección de por qué no se puede saber si un programa va a detener. Nada de lo dispuesto en el por encima de los ingresos a lo largo de la línea de "cálculos pueden evolucionar de una manera que es tan complicado que no podemos predecir lo que va a suceder cuando empezamos a ellos" o "las máquinas no pueden introspectiva sobre sí mismos a ese nivel de detalle." A menudo me doy estas intuiciones a mis alumnos cuando les pregunten por qué el resultado se mantiene, pero no soy consciente de ningún pruebas de que forma.

¿Hay pruebas de la undecidability de la detención problema que directamente explorar por qué es imposible que un programa de decidir qué otro programa va a hacer?

Gracias!

Answer 1

Esto no es lo que usted pidió, porque no es una prueba. Pero es un argumento.

Considere la posibilidad de algunos famosos y sin resolver el problema de matemáticas, tales como el doble conjetura de los números primos. (O la conjetura de Collatz, la conjetura de Goldbach, o, hasta hace poco, la conjetura de Fermat.) Estoy seguro de que usted recordar que la conjetura es que hay arbitrariamente grandes números de $p$ $p+2$ que son primos. ("El doble de los números primos")

Es fácil escribir un programa de ordenador que, dada una entrada de $N$, busca un par de gemelos de los números primos mayores que $N$, y que se detiene cuando encuentra un par.

El doble de los números primos conjetura es verdadera si, y sólo si, este programa se detiene en todas las entradas.

Por lo tanto, si hay una manera confiable de saber si un programa se detiene en todas las entradas, el doble de los números primos conjetura sería fácil de resolver, y podríamos concluir, por el hecho de que no se ha resuelto que los matemáticos son todos un montón de tontos.

Ahora, tal vez sus estudiantes no se preocupan por el doble conjetura de los números primos y tal vez no están seguros de que los matemáticos no son todos un montón de tontos. Pero ellos están familiarizados con los problemas y enigmas en general, y que probablemente está familiarizado con la idea de que a veces no sólo es difícil de encontrar soluciones, pero también puede ser difícil de ver antes de tiempo si no hay una solución. Probablemente puede ser persuadido de que usted puede conseguir un ordenador para buscar exhaustivamente por la solución a un problema, y detener la impresión y si encuentra uno.

Una solución a la paralización problema significaría que una gran clase de problemas puede ser resuelto fácilmente. Habría que escribir un programa para buscar una solución, y entonces, en lugar de ejecutar, analizar el programa para ver si iba a detener. Si la respuesta fue que sí, que iba a saber que había una solución, y todo lo que tenía que hacer para encontrar que era para ejecutar el programa. Por otro lado, si el programa no iba a detener, usted no tiene que preocuparse de correr porque usted sabe que no había solución.

Que sería un mundo muy diferente de la que realmente vivimos, y esto podría ser posible para persuadir a los estudiantes de eso.

Answer 2

Estoy de acuerdo en que las habituales pruebas no son muy "informativo", en el sentido de que no suelen satisfacer a un estudiante el deseo de saber por qué este es el caso. Un "informativo" la prueba es de suponer que construir el objeto en cuestión-pero obviamente no se puede construir un objeto para mostrar que no existe! Yo no excluye la posibilidad de encontrar un "algo informativo" de la prueba, pero creo que tal prueba, si es que existe, puede ser bastante complicada que convincente, pero no argumento matemático podría ser mejor.

Apelando a la idea que usted ha mencionado, que "los cálculos pueden evolucionar de una manera que es tan complicado que no podemos predecir lo que va a suceder cuando empezamos a ellos", parece ser una buena aproximación (posiblemente usando la secuencia de Collatz como un ejemplo de un cálculo que, claramente, evoluciona en formas que aún no comprendemos muy bien.)

Un enfoque complementario podría ser pedir a los estudiantes a considerar el programa de analizadores. Estos son los programas que tomar un programa como entrada y salida "sí" si se puede demostrar que tiene algunas propiedades (como detener), "no" si se puede demostrar que no es así, y "no sabe" si no pueden probar. Hay ejemplos del mundo real de estos programas, y se puede demostrar que algunos son más sofisticados que otros, y atando el argumento de la real, el software puede ayudar a algunos estudiantes a obtener una mejor conceptual agarre.

Ahora se pregunta: ¿qué pasa si nos encontramos con uno de estos programa de analizadores en, digamos, el estándar de la intérprete de Python? El programa analizador no puede verdaderamente decir "sí" o "no", porque no sabes qué programa Python que el intérprete le pedirá que ejecute.

Incluso si estipulamos que la secuencia de comandos que el intérprete de Python que se ejecuta en ser proporcionado por el analizador, el guión en sí podría ser un intérprete para algún otro lenguaje de programación (ad infinitum).

Incluso si estipulamos que el programa que está siendo analizado tomar ninguna entrada, podría ser un intérprete de Python con cualquier secuencia de comandos de Python codificado en ella. (Creo que hay herramientas disponibles para Python para hacer esto.)

Ahora bien, este razonamiento no es absolutamente a prueba de agua, pero la idea es enfatizar que usted puede hacer que los programas arbitrariamente complicada, y para tratar de conseguir a través de, "oh, no importa cuán sofisticado mi programa analizador es, siempre habrá algún programa que es tan complicada que está fuera de su alcance."

Answer 3

Me doy cuenta de que esto no es exactamente lo que usted está pidiendo, porque todavía utiliza diagonalización, pero creo que es un nuevo enfoque de la detención problema.

Me gustaría comenzar con la paradójica afirmación:

El menor número natural que no puede ser descrito únicamente en catorce palabras o menos.

Esta paradoja es que, obviamente, no es una declaración precisa, por lo que no es realmente una paradoja matemática. En particular, ¿qué significa ser "describe?"

Pero en la teoría de la recursividad, se puede definir lo que entendemos por "descrito" y el tamaño de una declaración.

Si podemos resolver la suspensión problema, podríamos escribir un programa que calcula, para cualquier $N$ el menor número natural que no es igual a$\phi_n(m)$$n,m\leq 2^{N}$. Esencialmente, tendríamos, por cada una de las $n,m<2^N$, pedir la suspensión del programa si $\phi_n(m)$ se detiene, y, en caso afirmativo, calcular el valor y la excluyen.

Decir que este programa calcula $\rho(N)$. Suponiendo que la detención problema tiene una solución, entonces se $\rho$ es recursiva, de modo que hay un $n_0$ tal que $\rho=\phi_{n_0}$. Pero, a continuación,$\rho(n_0)=\phi_{n_0}(n_0)$. Este rendimientos de su contradicción. $\rho(n_0)$ no puede ser el resultado de cualquier $\phi_n(m)$$m,n<2^{n_0}$. Pero $\rho(n_0)=\phi_{n}(m)$$m=n=n_0<2^{n_0}$.

Por alguna razón, me gusta comenzar con este informal paradoja, y luego trabajar desde allí para tratar de formalizar, y viendo que, en la formalización, hemos llegado a mostrar que la detención problema no tiene solución.

Como otros han señalado, dudo que usted puede evitar de diagonalización en algún momento. En particular, usted está hablando acerca de los programas en los que se analizan los programas, por lo que el "yo estoy mintiendo" paradoja es siempre un riesgo en un sistema.

Sin embargo, usted puede ser capaz de hablar acerca de otros problemas insolubles. Hilbert 10 del problema, la búsqueda de un programa que lleva a una ecuación de diophantine y devuelve si tiene solución, sería fácil de resolver con un subconjunto limitado de la detención problema.

También puede intentar encontrar limitada subconjuntos de las funciones recursivas para que usted pueda resolver la suspensión problema.