Reduções entre problemas indecidíveis

Sinto muito se esta pergunta tem alguma resposta trivial que estou perdendo. Sempre que estudo algum problema que foi provado indecidível, observo que a prova depende de uma redução para outro problema que foi provado indecidível. Entendo que ele cria algum tipo de ordem sobre o grau de dificuldade de um problema. Mas minha pergunta é - ficou provado que todos os problemas indecidíveis podem ser reduzidos a outro problema indecidível. Não é possível que exista um problema indecidível que possa provar não ter redução a qualquer outro problema indecidível (portanto, para provar a indecidibilidade desse problema, não se pode usar reduções). Se usarmos reduções para criar uma ordem no grau de computabilidade, esse problema não poderá ser atribuído a esse grau.

computability reductions undecidability swarnim_narayan
fonte

Resposta curta: longe de trivial! Veja a hierarquia aritmética .

Hendrik Jan

E quanto a isto: Se é uma linguagem indecidível e ser o menor elemento em

. Em seguida,

é redutível (e vice-versa) para

. Se você também adicionar um elemento a

(digamos o menor elemento que não esteja em

), terá uma redução de 1 a 1.

L

$L$

x min L

$x \min L$

L

$L$

L^{'} = L ∖ {x}

$L' = L \setminus \{x\}$

L

$L$

L^{'}

$L'$

L

$L$

Gål GD

Respostas:

Como Hendrik Jan mencionou, existem de fato diferentes graus de indecidibilidade. Por exemplo, o problema de decidir se uma máquina de Turing para em todas as entradas é mais difícil do que o problema da parada, no seguinte sentido: mesmo dado um oráculo ao problema da parada, não podemos decidir se uma determinada máquina de Turing para em todas as entradas .

Uma técnica importante usada para mostrar relações como essas é a diagonalização . Usando a diagonalização, dado um problema , sempre podemos encontrar um problema mais difícil, a saber, o problema de parada para máquinas de Turing com acesso a um oráculoO novo problema é mais difícil no seguinte sentido: uma máquina de Turing com acesso Oracle a não pode resolver . Nesse sentido, não há problema "mais difícil". $P$ $P$ $P'$ $P$ $P'$

Yuval Filmus
fonte

Obrigado pela resposta. Eu entendi o que você está dizendo. Podemos construir problemas "mais difíceis" a partir de problemas "mais difíceis". Mas esses esquemas de construção de problemas mais difíceis a partir dos mais difíceis (por exemplo, dizem que a diagonalização é um desses esquemas como você mencionou) necessariamente cobrem "todos" os problemas indecidíveis existentes (isto é, eles garantem a construção do conjunto de todos os problemas indecidíveis). Não é possível que alguns sejam deixados de fora na construção e não possam ser construídos a partir de outros indecidíveis?

swarnim_narayan

Pelo contrário, sabemos que a maioria dos problemas será deixada de fora, uma vez que existem apenas muitos problemas definíveis, mas muitos problemas no total. Mais concretamente, você pergunta como definir problemas "realmente difíceis", o análogo teórico da recursão dos grandes cardeais. Se é nisso que você está interessado, faça uma nova pergunta focada nesse aspecto.

Yuval Filmus

Um problema semelhante aparece ao construir hierarquias de funções de crescimento rápido recursivo; nesse caso, sabe-se que, em certo sentido, não há como construir uma hierarquia agradável e exaustiva.

Yuval Filmus