A meta-indecidibilidade é possível?

Existem problemas que são decidíveis, outros são indecidíveis, há semidecidibilidade etc.

Nesse caso, pergunto-me se um problema pode ser meta-indecidível. Isso significa (pelo menos na minha cabeça) que não podemos dizer se é decidível ou não.

Talvez seja sabido que a decidibilidade é indecidível (tudo é meta-indecidível) e não existe um algoritmo para provar a decidibilidade de qualquer coisa; portanto, a decidibilidade deve ser comprovada manualmente, caso a caso.

Talvez minha pergunta não faça sentido. Talvez eu esteja assumindo que somos máquinas de carbono executando algoritmos muito complexos e é por isso que a pergunta faz sentido apenas na minha cabeça.

Entre em contato se a pergunta precisar de mais esclarecimentos. Eu posso precisar disso neste momento.

Obrigado.

computability decidability undecidability Trylks
fonte

Vamos considerar a afirmação "a teoria monádica (de segunda ordem) de todas as ordens lineares é computável". Há razões para acreditar (mas não tenho certeza de que a independência tenha sido comprovada) de que essa afirmação é independente (ou seja, indecidível) no ZFC. Mais detalhes sobre as razões podem ser encontrados em books.google.es/books?id=y3YpdW-sbFsC&pg=PA397

boumol

Quando você diz "decidibilidade é indecidível", qual é a entrada?

Mahdi Cheraghchi

Ele também pode estar interessado em en.wikipedia.org/wiki/Turing_degree, mas não está claro como a pergunta é feita. :)

Daniel Apon

Boumol Shelah ("A teoria monádica da ordem", Ann. Math. 102 (3), 1975) provou (assumindo CH) que "a teoria monádica da ordem é indecidível" (Teorema 7 (B), p. 409).

Yuval Filmus

L = {\begin{cases} halting problem & if the continuum hypothesis holds \\ \emptyset & otherwise \end{cases}

$L = \begin{cases} \text{halting problem} & \text{if the continuum hypothesis holds} \\ \emptyset & \text{otherwise} \end{cases}$

Respostas:

Aqui está um rápido esboço para mostrar que não existe uma máquina de Turing para decidir se uma classe arbitrária de problemas é decidível.

$T$ $T(n)$ $n$

$M$ $T$ $\mathit{true}$ $\mathit{false}$

$T$ $T'$

$T$ $M(T')$ $\mathit{false}$

$T$ $T'$ $M(T')$ $\mathit{true}$

$M(T')$ $\mathit{true}$ $T$ $\mathit{false}$ $M$ $T$

cody
fonte

Ei, Cody! eu espero que você esteja bem. Você estará em Pittsburgh neste verão?

Michael Wehar

Ei! Não tenho certeza. Envie-me um e-mail!

Cody

Idéia muito legal!

Ideia: Podemos explorar o axioma da compreensão na teoria dos conjuntos ZF para definir uma linguagem que depende de uma afirmação independente.

Etapa 1: tome sua afirmação favorita que seja independente da ZF, como a CA - o axioma da escolha.

Etapa 2: defina um idioma L = {x in {0,1} | x = 0 se AC e x = 1 se NÃO AC}. Observe que L é {0} ou {1}. Agora, L é decidível, mas não podemos fornecer com certeza um programa que decida L. Podemos fornecer o programa que decide {0} ou poderíamos fornecer o programa que decide {1}, mas não sabemos com certeza qual deles decide L.

Etapa 3: use essa idéia para definir um idioma que seja decidível se for AC e indecidível se NÃO for AC. Seja H o conjunto de paradas que é indecidível. Defina L = {x | x é uma string se AC e x estiver em H se NÃO AC}. Se AC, então L = o conjunto de todas as strings e L é decidível. Se NÃO for AC, então L = H e L são indecidíveis. Se L é decidível ou não, é independente de ZF.

Michael Wehar
fonte