Os idiomas reconhecíveis por Turing (também chamados de idiomas recursivamente enumeráveis) são idiomas para os quais existe uma máquina de Turing que interrompe e aceita cordas no idioma, mas pode fazer uma volta para sempre em cordas não no idioma. Isso contrasta com outros tipos de idiomas de maneira crucial:eles não necessariamente * decidem * membros; Eles apenas * reconhecem * isso.
Aqui estão alguns exemplos de idiomas reconhecíveis por Turing, contrastados com outras classes de idiomas:
Exemplos de idiomas reconhecíveis por Turing: *
A linguagem de todas as máquinas de Turing que param na sequência vazia: Podemos construir uma máquina de Turing que simula uma determinada máquina de Turing na corda vazia. Se a máquina simulada parar, nossa máquina aceitar. Se for para sempre, nossa máquina fará para sempre. Isso é reconhecível; Não há como dizer definitivamente que uma máquina * não * pare.
*
A linguagem de todas as declarações verdadeiras na aritmética de primeira ordem: O teorema da integridade de Gödel mostra que toda afirmação verdadeira pode ser comprovada. Uma máquina de Turing pode enumerar sistematicamente todas as provas possíveis e aceitar uma declaração se uma prova for encontrada. No entanto, se uma declaração for falsa, a máquina nunca será interrompida.
*
A linguagem de todas as gramáticas sem contexto que geram pelo menos uma série de comprimento 10: Uma máquina de Turing pode gerar sistematicamente todas as cordas de um determinado CFG e verificar seu comprimento. Se encontrar um de comprimento 10, aceita. Se o CFG não gerar nenhuma string, a máquina poderá ser executada indefinidamente para encontrar uma.
*
A linguagem de todos os pares de máquinas de Turing (M1, M2), de modo que o M1 interrompe quando recebe a codificação de M2 como entrada: Isso ilustra a complexidade. Podemos construir uma máquina que simula M1 na codificação de M2. Se o M1 parar, nossa máquina aceita. Caso contrário, ele loop. Isso destaca a indecidibilidade inerente a muitos problemas reconhecíveis por Turing.
Como eles diferem de outros tipos de idiomas: A principal diferença está no comportamento de interrupção:
*
idiomas decidáveis (recursivos): São idiomas para os quais existe uma máquina de Turing que sempre parte e decide corretamente se uma determinada sequência de entrada está no idioma ou não. Cada string recebe uma resposta definitiva de "sim" ou "não". Os exemplos incluem idiomas regulares, idiomas livres de contexto (com algumas restrições) e muitos outros que podem ser decididos por algoritmos com rescisão garantida.
*
idiomas reconhecíveis (recursivamente enumeráveis): Conforme discutido acima, esses idiomas são reconhecidos por máquinas de Turing que podem fazer uma pausa para sempre nas cordas que não estão no idioma. Eles são um * superconjunto * de idiomas decidíveis por Turing; Cada linguagem decidível também é reconhecível.
*
Idiomas não reconhecíveis por Turing: Esses idiomas não podem nem ser reconhecidos por uma máquina de Turing. Não há algoritmo, porém ineficiente, que possa identificar corretamente todas as seqüências do idioma. Um exemplo é o complemento do problema de interrupção (o idioma de todas as máquinas de Turing que * não * param na sequência vazia).
Resumindo:
| Classe de idioma | Comportamento de interrupção | Exemplo |
| -------------------
| Turing Decidable | Sempre interrompe, decide corretamente a associação | Idiomas regulares, idiomas livres de contexto (com restrições) |
| Turing-reconhecível | Interrompe e aceita cordas no idioma, pode fazer um loop de outra forma | Linguagem das máquinas de Turing que param na corda vazia |
| Não reconhecível não-torre | Nenhuma máquina de Turing pode reconhecê -la | Complemento do problema de interrupção |
A hierarquia é:Turing Decidable ⊂ Turing-reconhecível ⊂ Todos os idiomas. A inclusão é rigorosa; Existem idiomas reconhecíveis que não são decidíveis. E existem muitos idiomas além dos reconhecíveis.
