Em matemática, lógica e ciência da computação, uma linguagem recursivamente enumerável é um tipo de Linguagem formal que também é chamada de linguagem Turing-reconhecível. Também é conhecida como tipo-0 na hierarquia de Chomsky das linguagens formais.
O décimo problema de Hilbert abrange a classe das linguagens recursivamente enumeráveis.
Definições
Existem três equivalentes definições importantes para o conceito de uma linguagem recursivamente enumerável:
Uma linguagem recursivamente enumerável formal é um subconjunto recursivamente enumerável no conjunto de todas as palavras possíveis sob o alfabeto da linguagem. Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá enumerar todas as cadeias válidas da linguagem. Note que, se a linguagem é infinita, o algoritmo de enumeração fornecido pode ser escolhido de forma que evite repetições, uma vez que podemos testar se a cadeia produzida para o número n é já é produzida para um número que é inferior a n. Se ela já é produzida, use a saída da entrada n+1 (recursivamente), mas mais uma vez, teste se é uma cadeia nova. Uma linguagem recursivamente enumerável é uma linguagem formal para a qual existe uma máquina de Turing que irá parar e aceitar quando se roda com qualquer cadeia da linguagem na entrada e pode parar e rejeitar ou entrar em loop quando se roda com qualquer cadeia que não é da linguagem. Esta é a diferença entre linguagem recursiva, que exige que a máquina de Turing sempre pare. Linguagem regular, linguagem livre de contexto e linguagem recursiva são todas recursivamente enumeráveis.
O teorema de Post mostra que RE, juntamente com seu complemento co-RE, correspondem ao primeiro nível da hierarquia aritmética.
Propriedades de fecho
As linguagens recursivamente enumeráveis são fechadas sob as seguintes operações. Isto é, se L e P são duas linguagens recursivamente enumeráveis, então as seguintes linguagens são também recursivamente enumeráveis: O Fecho de Kleene A concatenação A união A interseção
Note que as linguagens recursivamente enumeráveis não são fechadas sob diferença e complemento. A diferença L-P pode ou não ser recursivamente enumerável. Se L é recursivamente enumerável, então o complemento de L é recursivamente enumerável se e somente se L também for recursiva.
Teoria da computação
Referências Sipser, M. (1996), Introduction to the Theory of Computation, PWS Publishing Co. Kozen, D.C. (1997), Automata and Computability, Springer.
Ligações externas Lecture slides
Categoria:Teoria da computação Categoria:Matemática da computação