Consecuencias de resolver el problema de Halting

Question

¿Qué impacto tendría un dispositivo (es decir súper computadora o equipo relativista u otro método) que soluciona el problema de detener en matemáticas?

¿Habría problemas matemáticos izquierda para resolver?

¿Cuáles serían los mayores desafíos matemáticos izquierda?

¿Podríamos calcular si nuestro sistema axiomático es consistente?

¿Podríamos encontrar «el uno verdadero y final» teoría de conjunto completa?

Answer 1

Hay un sutil punto que debe tenerse en cuenta: Tenemos que saber que detener problema del que estamos hablando. Si nos estamos refiriendo a la detención problema para máquinas de Turing, lo que significa que podemos decidir la consistencia de hoy axiomática de los sistemas de sólo. Es decir, las matemáticas pueden evolucionar radicalmente si un algoritmo que resuelve el cese problema para máquinas de Turing fue inventado.

La razón por la que puede encontrarse en la definición de un sistema axiomático. Lo que queremos es un conjunto de axiomas que un algoritmo de decidir si una frase es un axioma o no. Por lo tanto nuevos procesos algorítmicos nos puede permitir crear nuevas, más expresivo axiomática de los sistemas que no pueden ser codificadas en máquinas de Turing.

Y tal vez esta nueva clase de algoritmos va tienen propiedades similares a las máquinas de Turing y no será capaz de resolver sus propios detener problema. A continuación, estas nuevas matemáticas del mismo modo tendrá incertidumbres y requieren de ingenio en el descubrimiento de teoremas.

Answer 2

Bien, un medio para resolver la paralización problema en sí no haría nada para nosotros si tomaría $2^{1000}$ pasos para probar si incluso un pequeño programa se detiene o no. Pero supongamos tenemos un mágico oracle que puede hacer esto para nosotros rápidamente. Por ejemplo, imagine que usted tenía un rollo con Chaitin constante inscrito en él.

Entonces ciertamente podríamos calcular si el sistema de axiomas (que voy a asumir que se recursivamente enumerable en el estándar de sentido) es consistente o no. Simplemente definir una máquina de $M$ como sigue: para cada $n$, $M$ enumera todas las posibles pruebas de longitud de $n$ (en nuestro idioma y con nuestro fijo el conjunto de axiomas) y comprueba si una contradicción (que es, $p \cap \not p$) puede ser derivada. Si en algún punto de una contradicción se deriva, se detiene. Así que si este programa se detiene o no es equivalente a la consistencia del axioma esquema. Por una variante de esto, nos gustaría ser capaces de determinar si cualquier declaración de interés (por ejemplo, la hipótesis de Riemann, el P versus NP problema, etc.) es comprobable desde nuestro axioma esquema.

Answer 3

Este dispositivo sólo resolvería problemas baja hacia abajo en la jerarquía. Por ejemplo, que $T$ ser el conjunto de oraciones en el lenguaje habitual de la teoría de números que son verdaderos en los números naturales (por lo que pido de verdad, no demostrativa de decir los axiomas habituales). Nuestro dispositivo hipotético sería irremediablemente inadecuada para determinar si es o no una sentencia en $T$. Es cierto que sería capaz de tratar con la mayoría de las frases interesantes.

Answer 4

Creo que tendría que caminar un cuidado de la línea. Si tuviéramos un oráculo para detener problema, podríamos esencialmente probar gran parte de la teoría de los números con una máquina, algo como:

1) n=0

2) la Prueba (en)la igualdad de fórmula para el n

Si es verdad, continuar.

Si su falsa parar.

3) n= n+1

4) GOTO 1

y luego usamos el oráculo. Esto funciona para la mayoría de los teoremas y conjeturas en la teoría de números.

Realmente se pone a la derecha en el borde de Goedels teorema de la incompletitud, porque en principio, puede comprobar la mayoría de primer orden frases acerca de los números enteros.