Quando você está provando que um idioma é decidível, o que você está efetivamente fazendo?

Question

Quando você está provando que um idioma é decidível, o que você está efetivamente fazendo?

Answer 1

Se você perguntar como é feito, não tenho certeza, mas posso verificar.

Basicamente, a decisão é a linguagem para a qual se pode construir um algoritmo (ou seja, a máquina de Turing) que interromperá qualquer entrada finita (com aceitação ou rejeição da entrada). Indecidável é o idioma que não é decidível.

http://en.wikipedia.org/wiki/recursive_language ... mas mais sobre o assunto pode ser facilmente encontrado. Neste link, há apenas uma menção rápida do termo.

PS Então, ao construir o algoritmo acima mencionado, você está basicamente provando que a linguagem é decidível.