Decidir Decidability é Decidable?

Eu estou querendo saber se decidir a decidibilidade do problema é um problema decidível. Acho que não, mas após as pesquisas iniciais não consigo encontrar nenhuma literatura sobre esse problema.

Edição principal do meu original:

Parece uma leitura ingênua da sua pergunta, seja o problema$P$

Dado um idioma, L , é decidível?$P=$$L$

Então você pergunta

é decidível?$P$

Como DW e David observaram, a resposta é "sim, é", embora não saibamos qual dos dois decisores triviais é o correto. A fim de enquadrar seu problema para que não seja tão trivial, sugiro isso. Primeiro, vamos restringir as coisas um pouco, considerando apenas aqueles línguas , que são as línguas aceites por alguns TM M . A razão para fazer isso é que, se um idioma não é aceito por nenhuma TM, ele não é re-reconhecível e, portanto, não pode ser recursivo (decidível). Então podemos reformular P como$L(M)$$M$$P$

Dada uma descrição, ⟨ M ⟩ de uma TM, M é G ( M ) decidíveis?$P'=$$\langle M\rangle$$M$$L(M)$

Agora é uma linguagem das descrições da MT, em vez de uma linguagem das línguas como P parecia (sob uma interpretação generosa), e agora é perfeitamente razoável perguntar se a linguagem P ' é decidível. Sob essa leitura, a linguagem { ⟨ M ⟩ | M  é um TM e  L ( M )  é decidível } consistindo de descrições TM não é decidível. Essa é uma conseqüência fácil do teorema de Rice . Então agora temos duas respostas: meu "não" e o "sim" do DW, dependendo da interpretação.$P'$$P$$P'$

Como vimos nas diferentes respostas, parte da resposta está na formulação do problema certo.

Em 1985, Joost Engelfriet escreveu "A não computabilidade da computabilidade" (Boletim do EATCS número 26, junho de 1985, páginas 36-39) como resposta a uma pergunta feita por um estudante inteligente. Infelizmente, o BEATCS naquela época era apenas papel e o artigo não deixava vestígios eletrônicos.

O autor assume que temos um formalismo (lógico) com os operadores e variáveis ​​booleanos usuais. Sua definição precisa não é importante. Uma fórmula F ( m , n ) especifica uma função f : N → N se s (para todos os m , n ∈ N ) f ( m ) = n ⇔ F ( m _ , n _ ) é verdadeira, onde m _ é o numeral representando o número m .$\Psi$$F(m,n)$$f:\Bbb N \to \Bbb N$$m,n\in \Bbb N$$f(m)=n$ $\Leftrightarrow$ $F(\underline m,\underline n)$$\underline m$$m$

Eu cito:

$\Phi$$\Bbb N \to \Bbb N$$f$$f$

A parte divertida está na seguinte observação feita no artigo:

$\Phi$

Sim. É sempre decidível.

Para qualquer problema P, seja Q o problema de determinar se P é decidível ou não. Eu afirmo que Q é decidível. Aqui está o porquê. Tautologicamente, P é decidível ou não. Portanto, um dos dois programas está correto: (1) print "yup P is decidable"ou (2) print "nope P is not decidable". Pode não ser trivial descobrir qual desses dois programas está correto, um deles está correto; portanto, uma decisão para Q certamente existe . Portanto, o problema Q é decidível.

Isso lembra a seguinte pergunta clássica: É decidível dizer se a conjectura de Collatz é verdadeira? A resposta é sim. Isso pode parecer estranho, pois ninguém sabe se a Conjectura de Collatz é verdadeira (esse é um famoso problema em aberto). No entanto, o que sabemos é que a conjectura de Collatz é verdadeira ou não. No primeiro caso, o programa print "yup it's true"é decisivo. Neste último caso, o programa print "nope it's not true"é decisivo. Não sabemos qual é um decisor válido, mas isso é suficiente para provar que existe um decisor válido. Portanto, o problema é decidível.