Podemos mostrar que um idioma não é computável enumerável, mostrando que não há verificador para ele?

11

Uma das definições de um conjunto computávelmente enumerável (ce, equivalente a recursivamente enumerável, equivalente a semidecidável) é o seguinte:

AΣ é ce sse existe uma língua decidíveisVΣ (chamado verificador) r para todos osxΣ ,

xA sse existe umayΣ rx,yV .

Portanto, uma maneira de mostrar que um idioma não é ce é mostrar que não existe um verificador decidível Vpara ele. Este método é útil para mostrar que os idiomas não estão na prática?

Anônimo
fonte
3
o que é ce (fez você re média?)
Ran G.
Não consigo pensar em uma situação em que isso seja útil para provar que um idioma não é CE. Espero que você possa facilmente substituir V por A em uma redução de muitos. Se você veio com alguma outra redução, seria de esperar que as "saídas negativas" x,yV não significaria tanto quanto y é existencialmente quantificada.
Lucas Cozinhe
@RanG., Re é a antiga terminologia, atualmente é normalmente referida como ce por pessoas que trabalham na teoria da computabilidade. (Se você estiver interessado sobre a razão para a mudança na terminologia sugiro verificar a página de Robert Soare.)
Kaveh
@Kaveh thanks. Todos os dias se aprende coisas novas ...
Ran G.

Respostas:

4

Na prática, geralmente não provamos apenas que um idioma é re ou não re. Se o idioma for re, queremos saber se é recursivo. Se não for re, queremos saber que tipo de diploma de Turing ele possui, não apenas que o grau de Turing não é re.

PPT0PP

Portanto, embora, em princípio, você possa mostrar que um idioma não é re, provando que não há verificador, na prática é mais informativo provar que o idioma não é re, mostrando que ele calcula algo que nenhum reestabelecimento pode calcular; a natureza desse 'algo' normalmente fornece informações úteis sobre o problema que está sendo estudado.

Carl Mummert
fonte
3

Para esclarecer a terminologia, uso: decidível = recursivo = computável, semidecidável = recursivamente enumerável = enumerável computacionalmente, co-semidecidável = co-recursivamente enumerável = co-computável enumerável.

Na prática, um método comum para mostrar que um idioma não é semidecidável é mostrar que não é decidível e que é co-semidecidível. Você então usa o fato de que qualquer idioma que seja semidecidível e co-semidecidável também poderá decidir concluir que seu idioma não é semidecidável. (observe que isso só funciona em uma direção: um idioma não pode ser nemidecidável nem co-semidecidável; nesse caso, você precisa de outro método)

Como exemplo: sabemos que decidir se um é ambíguo é indecidível, mas é fácil co-semidecidir: você apenas fornece uma string com duas análises diferentes. Isso implica que não é semidecidável se um é ambíguo.CFGCFG

Outro método é mostrar que o idioma está completo para algum nível superior da hierarquia aritmética .

É claro que é possível provar diretamente que não há verificador, mas isso geralmente é tedioso, pois geralmente repete a prova de que o problema da parada é indecidível. Observe que o argumento acima prova implicitamente que não há verificador, então acho que você poderia dizer que é um método para provar que não há verificador, mas então você pode considerar qualquer prova de não-semidecidibilidade como prova de que existe não mais verfier.

Alex ten Brink
fonte
Há uma falha no seu idioma. Um idioma não pode ser semi-decidível nem co-semidecidível. Idiomas indecidíveis são esses idiomas.
Dave Clarke
@ DaveClarke: eu adicionei algumas definições de terminologia. Está correto agora?
Alex-Brink
Não (semi-decidível) não (decidível) semidecidível.
Dave Clarke
@DaveClarke: adicionei uma nota dizendo que só funciona em uma direção.
Alex-Brink
3
Não estou convencido de que essa seja uma técnica que alguém possa usar. Por que não reduzir o problema a um problema conhecido "não semi-decidível".
30512 Dave Clarke