Comportamiento indemostrable de una máquina de turing

Sí, su comprensión es básicamente correcta: este es (hasta donde sabemos) un resultado posible. El tema es que puede haber modelos de ZFC en los que haya números naturales "no estándar". Estos números no estándar corresponden a instancias no estándar de SAT, que el algoritmo$\alpha$podría fallar en resolver, a pesar de que resuelve todas las instancias reales de SAT.

Resulta que el tiempo de ejecución no estándar no es un problema, si$\alpha$corre en tiempo polinomial$p$, considere el algoritmo$\alpha'$que realiza$\alpha$para$p$-muchos pasos, y luego, si aún no se ha detenido, se detiene y emite 1 (digamos). Entonces$\alpha'$resuelve todas las instancias reales de SAT, e incluso de forma no estándar$\alpha'$corre en tiempo polinomial. Entonces, el problema realmente se trata de instancias no estándar de SAT.

Esto es análogo al teorema de incompletitud de Gödel: aunque no hay un número natural real que codifique una prueba de$0=1$a partir de los axiomas de ZFC (esperamos :P), habrá un modelo de ZFC que contenga algún número natural no estándar$n$que (piensa el modelo) codifica una prueba de$0=1$de$ZFC$- es decir, una "prueba no estándar".

Puede ser útil distinguir diferentes formas posibles$P = NP$podría ser cierto, pero no demostrablemente cierto. Para poder$P = NP$, debe haber una máquina de Turing$T$que resuelve SAT en tiempo polinomial. Pero:

1. Puede ser imposible probar que siempre se detiene.
2. Podría ser posible probar que siempre se detiene, pero imposible probar que siempre produce un resultado correcto.
3. Podría ser posible probar que siempre se detiene, pero imposible probar que se detiene en tiempo polinomial.

Esto no debería ser tan extraño. Muchos problemas matemáticos no resueltos pueden formularse en términos de preguntas sobre una máquina de Turing. Por ejemplo, la conjetura de Collatz es verdadera si y solo si cierta máquina de Turing siempre se detiene.

Existe una posibilidad de que la solución no sea constructiva: por ejemplo, tiene un universo en el que ninguna máquina de Turing resuelve SAT en tiempo polinomial, y tiene otro universo en el que es imposible que todas las máquinas de Turing no resuelvan SAT en tiempo polinomial. Esto último no es constructivamente equivalente a encontrar una máquina de Turing que resuelva SAT en tiempo polinomial; nunca has encontrado uno.

Esto se puede reformular un poco. El teorema de Ladner establece que si$\mathrm{P}\neq \mathrm{NP}$entonces existe un lenguaje NP-intermedio (un lenguaje se llama NP-intermedio si está en$\mathrm{NP}\setminus \mathrm{P}$y no es NP-completo). Por lo tanto, es teóricamente posible probar el resultado de la independencia de la siguiente manera: construya un universo en el que no exista un lenguaje NP-intermedio (entonces$\mathrm{P}=\mathrm{NP}$), y construir otro en el que es imposible que todos los idiomas no sean NP-intermedios (por lo que$\mathrm{P}\neq \mathrm{NP}$). Una vez más, no se encontraría ninguna máquina de Turing.

(En la respuesta de Noah, parece que si existe tal$\alpha$, el algoritmo que resuelve todas las instancias reales de SAT en tiempo polinomial, entonces deberíamos aceptar$\mathrm{P}=\mathrm{NP}$como una verdad que es independiente de ZFC. No estoy seguro si dado algún algoritmo$\alpha$, la expresion "$\alpha$resuelve SAT en tiempo polinomial" es$\Pi_1$(en PA/ZFC) o no. Si lo es, entonces, dado cierto algoritmo$\alpha$, siempre que sabemos que$\phi:=$"$\alpha$resuelve SAT en tiempo polinomial" es independiente de PA/ZFC, entonces de hecho podemos concluir que$\phi$es cierto , ya que PA/ZFC demuestra ser cierto$\Sigma_1$-frases, y si$\neg\phi$fuera cierto, PA/ZFC lo probaría).