Problemas "naturales" indecidibles no reducibles al problema de detención

Question

Hay muchos ejemplos conocidos de problemas indecidibles, una gran cantidad de ellos no relacionados directamente con máquinas de Turing o modelos equivalentes de computación, por ejemplo aquí: https://en.m.wikipedia.org/wiki/List_of_undecidable_problems

También se sabe que la estructura de los grados de turing es extremadamente complicada, y que hay problemas indecidibles no reducibles a los problemas de detención, siendo el ejemplo más básico "¿Se detiene una máquina de turing con un oráculo para el problema de detención?"

Así que mi pregunta es: ¿Existe algún ejemplo de problema no relacionado con máquinas abstractas que sea indecidible pero no reducible al problema de detención? (Es decir, que tenga un grado de turing distinto de 0')

Answer 1

Los problemas reducibles al problema de detención son exactamente los problemas de complejidad $\Delta^0_2$ en el jerarquía aritmética y, de hecho, hay muchos problemas naturales fuera de esta clase. En este sentido, estás pidiendo ejemplos naturales de problemas de decisión de alta complejidad aritmética.

• Verdad aritmética, para decidir si una sentencia aritmética dada $\sigma$ es cierto en el modelo estándar $\langle\mathbb{N},+,\cdot,0,1,<\rangle$ es indecidible, pero no reducible al problema de detención.

• $\Sigma^0_n$ verdad, restringida a sentencias de esta complejidad, para $n\geq 2$ es indecidible, pero no reducible al problema de detención.

• Verdad proyectiva, para decidir si una frase dada $\sigma$ es verdadera en el campo real $\langle\mathbb{R},+,\cdot,0,1,<,\mathbb{Z}\rangle$ con los enteros como predicado unario, es indecidible, pero no reducible al problema de detención.

• Verdad teórica de conjuntos en varios modelos, para decidir si una frase dada es verdadera en la estructura de conjuntos hereditariamente contables. $\langle H_{\omega_1},\in\rangle$ o al menos en el universo Zermelo $V_{\omega+\omega}$ o al menos el universo Zermelo-Grothendieck $\langle V_\kappa,\in\rangle$ es indecidible, pero no reducible al problema de detención.

• Decidir si una presentación de grupo c.e. dada es trivial tiene generalmente una complejidad $\Pi^0_2$ (porque hay que decir que cada generador es trivial), y esto será indecidible, pero no reducible al problema de halting. (Tenga en cuenta, para c.e. presentaciones con finitamente muchos generadores, esto es reducible al problema de detención).

• Decidir si un grafo c.e. dado sobre los números naturales es conexo tiene generalmente una complejidad $\Pi^0_2$ por lo que es indecidible y no reducible al problema de detención.

• Para decidir si una función computable dada es total tiene complejidad $\Pi^0_2$ ya que hay que decir que cada entrada tiene un cálculo de detención, y esto es completo para ese nivel de complejidad, por lo que es indecidible, pero no reducible al problema de detención.

• Decidir si una función computable dada es suryectiva tiene complejidad completa $\Pi^0_2$ por lo que es indecidible, pero no reducible al problema de detención. (Mientras tanto, decidir si es inyectiva es $\Pi^0_1$ y, por tanto, reducible al problema de detención).

Hay muchos más ejemplos. Véase, por ejemplo jerarquía de grados de irracionalidad . Todos los ejemplos superiores en la jerarquía equivalen a problemas de decisión indecidibles que no son reducibles al problema de detención.

Un doble a su pregunta. Hay una versión dual de su pregunta que es fascinante y objeto de un programa de investigación en teoría de la computabilidad. A saber, ¿existen problemas naturales de decisión que sean indecidibles, pero tales que el problema de detención no se reduzca a ellos?

Sin duda, la Solución de Friedberg-Muchnik del problema de Post muestra que hay grados de Turing c.e. indecidibles estrictamente por debajo del problema de detención, y por tanto hay problemas de decisión indecidibles estrictamente por debajo del problema de detención. Pero estos problemas se construyen especialmente para este propósito y, en este sentido, no se consideran como surgidos "naturalmente". Además, en general se considera una cuestión abierta si existen problemas de decisión naturales en esta clase (una propuesta: el conjunto de diferencias de primos). Aunque a menudo considero que estos usos de "natural" son vacíos, en la teoría de la computabilidad existe un programa de investigación para formular versiones sustantivas de la cuestión, a través de la conjetura de Martin y otros enfoques. Véase un análisis más detallado en mi artículo, Linealidad y illfoundedness en la jerarquía de gran fuerza de consistencia cardinal especialmente las secciones 9, 10 y 11, que se centran en la naturalidad y la teoría de la computabilidad.

Answer 2

Ya ha habido excelentes respuestas, con la propiedad de que (a excepción de (3) y (4) de la respuesta anterior ) son reducibles a una iteración del salto de Turing a lo largo de un buen orden computable. Así que permítanme añadir un par que no lo son.

El conjunto de los ordenamientos lineales computables que tienen un subordenamiento denso, es decir, incrustan una copia de los números racionales $\mathbb Q$ y se sabe que el conjunto de ordenaciones lineales computables que no están bien ordenadas, es decir, que tienen una secuencia descendente infinita, es $\Sigma^1_1$ completa. A la inversa, el conjunto de los bien ordenados computables es $\Pi^1_1$ completos. Estos conjuntos no sólo no son reducibles al problema de Halting, sino que ni siquiera la iteración del salto de Turing a lo largo de un buen orden computable permite calcularlos.

Answer 3

El problema de la "Adivinación Consistente" de Aaronson : Consideremos una función total $f : M \to \{0,1\}$ , donde:

• $M$ denota el conjunto de máquinas de Turing que aceptan o rechazan sus entradas, o que no terminan.

• $f(m) = 1$ siempre que $m$ termina en un estado de aceptación

• $f(m)=0$ siempre que $m$ termina en un estado de rechazo.

• El valor de $f(m)$ cuando $m$ no termina se deja sin especificar. Pero la función debe producir un valor en $\{0,1\}$ independientemente.

El problema es incalculable.

El problema anterior está relacionado con el problema LLPO en lógica constructiva: Decidir para un real computable $x$ si $x \leq 0$ o $x \geq 0$ . En cambio, el problema de detención corresponde al problema LPO en lógica constructiva: Decidir para un real computable $x$ si $x < 0$ o $x = 0$ o $x > 0$ . LPO es más fuerte.