CO-P é recursivamente enumerável?
-
29-09-2020 - |
Pergunta
p é re, mas é o complemento da classe de idiomas decidível no tempo polinomial também recursivamente enumerável?
Se ambos são, então, isso torna P recursivo?
Solução
co- $ \ mathsf {p}=mathsf {p} $ .Para ver isso, escolha seu problema favorito $ a $ em co- $ \ mathsf {p} $ ,Deixe $ t $ ser uma máquina de Turing para o complemento da $ a $ (em $ \ mathsf {p} $ ) e construa uma nova máquina de Turing $ t '$ que simula $ T $ , aceita se $ t $ rejeita e rejeita se $ t $ Aceita.
Licenciado em: CC-BY-SA com atribuição
Não afiliado a cs.stackexchange