Linguagem recursivamente enumerável: diferenças entre revisões

sem resumo de edição
m (Bot: Adicionando: sh:Rekurzivno prebrojiv jezik)
{{esboço}}
 
Uma [[linguagem formal]] é dita '''recursivamente enumerável''' se ela é computável, ou seja, se existe um [[algoritmo]] que reconhece esta linguagem mas que não necessariamente para qualquer entrada. Uma linguagem é computável quando existe uma [[máquina de Turing]] que sempre pára, com "sim" ou "1" para instâncias positivas. Para cadeias fora da linguagem a máquina de Turing pode não parar, contrariamente ao que acontece com as [[linguagem recursiva|linguagens recursivas]].
 
O décimo [[Problemas de Hilbert|problema]] de [[Hilbert]] abrange a classe das linguagens recursivamente enumeráveis.
Utilizador anónimo