Reducciones entre problemas indecidibles

Lo siento si esta pregunta tiene alguna respuesta trivial que me falta. Cada vez que estudio algún problema que se ha demostrado que es indecidible, observo que la prueba se basa en una reducción a otro problema que se ha demostrado que es indecidible. Entiendo que crea algún tipo de orden sobre el grado de dificultad de un problema. Pero mi pregunta es: ¿se ha demostrado que todos los problemas que son indecidibles pueden reducirse a otro problema que es indecidible? ¿No es posible que exista un problema indecidible que pueda demostrar que no tiene reducción a ningún otro problema indecidible? Si usamos reducciones para crear un orden sobre el grado de computabilidad, entonces este problema no puede asignarse a ese grado.

computability reductions undecidability swarnim_narayan
fuente

Respuesta corta: lejos de ser trivial! Mira la jerarquía aritmética .

Hendrik

¿Qué hay de esto: Si

L

$L$ es un lenguaje indecidible y

x min L

$x \min L$ sea el elemento más pequeño en

L

$L$ . Entonces

L^{'} = L ∖ {x}

$L' = L \setminus \{x\}$ es reducible (y viceversa) a

L

$L$ . Si además agrega un elemento a

L^{'}

$L'$ (digamos que el elemento más pequeño no está en

L

$L$ ), entonces tiene una reducción de 1-1.

Pål GD

Respuestas:

Como mencionó Hendrik Jan, de hecho hay diferentes grados de indecidibilidad. Por ejemplo, el problema de decidir si una máquina de Turing se detiene en todas las entradas es más difícil que el problema de detención, en el siguiente sentido: incluso dado un oráculo al problema de detención, no podemos decidir si una máquina de Turing determinada se detiene en todas las entradas .

Una técnica importante utilizada para mostrar relaciones como estas es la diagonalización . Usando la diagonalización, dado un problema , siempre podemos encontrar un problema más difícil, a saber, el problema de detención para máquinas Turing con acceso a un oráculoEl nuevo problema es más difícil en el siguiente sentido: una máquina Turing con un oráculo de acceso a no puede resolver . En ese sentido no hay problema "más difícil". $P$ $P$ $P'$ $P$ $P'$

Yuval Filmus
fuente

Gracias por la respuesta. Entendí lo que estás diciendo. Podemos construir problemas "más difíciles" a partir de problemas "difíciles". Pero, ¿estos esquemas de construcción de problemas más difíciles de los más difíciles (por ejemplo, decir que la diagonalización es uno de los esquemas que usted mencionó) necesariamente cubren "todos" los problemas indecidibles existentes (es decir, están garantizados para construir el conjunto de todos los problemas indecidibles). ¿No es posible que algunos se queden fuera de la construcción y no puedan construirse a partir de otros indecidibles?

swarnim_narayan

Por el contrario, sabemos que la mayoría de los problemas se dejarán de lado, ya que solo hay innumerables problemas definibles, pero incontables muchos problemas en total. Más concretamente, preguntas cómo definir problemas "realmente difíciles", el análogo teórico de la recursión de los grandes cardenales. Si eso es lo que le interesa, haga una nueva pregunta centrada en este aspecto.

Yuval Filmus

Un problema similar aparece cuando se construyen jerarquías de funciones recursivas de rápido crecimiento, en cuyo caso se sabe que, en cierto sentido, no hay forma de construir una jerarquía agradable y exhaustiva.

Yuval Filmus