Sim, a diferença entre idiomas decidíveis e reconhecíveis é perfeitamente clara. A distinção está no comportamento de uma máquina de Turing (TM) tentando determinar a associação:
*
linguagem decidível (linguagem recursiva): Uma linguagem l é decidível se existir uma máquina de Turing que, para * cada sequência de entrada W, interrompa e responde corretamente "sim" se w ∈ L e "não" se w ∉ L. Isso significa que a TM sempre interrompe, independentemente de a entrada estar no idioma ou não.
* idioma reconhecível (linguagem recursivamente enumerável): Um idioma l é reconhecível se existir uma máquina de Turing que, para * cada sequência de entrada W, interrompe e responda "sim" se w ∈ L. No entanto, se w ∉ l, a TM pode parar e responder "não" ou pode correr para sempre (loop indefinidamente). A chave é que ela * sempre * fornece a resposta correta ("sim") se a string estiver no idioma; É permitido apenas não ser determinístico ou não fornecer uma resposta quando a string não estiver * no idioma.
Em termos mais simples:
*
Decidível: A TM sempre dá uma resposta definitiva (sim ou não) em tempo finito.
*
reconhecível: A MT fornece uma resposta "sim" em tempo finito se a entrada estiver no idioma, mas pode não dar uma resposta (ao fazer uma para sempre) se a entrada não estiver no idioma.
Cada linguagem decidível também é reconhecível. No entanto, o inverso não é verdadeiro; Existem idiomas reconhecíveis que não são decidíveis. O problema de interrupção é um exemplo clássico de um idioma reconhecível, mas não decidível. Pode -se construir uma MT que reconheça strings que representam máquinas de intervalo de Turing (simula a máquina e responde "sim" se interromper), mas nenhuma MT pode decidir se uma máquina de Turing arbitrária interromperá uma determinada entrada (porque isso resolveria o próprio problema de parada).
A diferença se resume a se a TM garante a rescisão para todos os insumos (decidíveis) ou apenas garante uma resposta "sim" em tempo finito para insumos no idioma (reconhecível). A diferença é fundamental na teoria da computação.
