![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/R%25C3%25A9cursivement_%25C3%25A9num%25C3%25A9rable.svg/langpt-640px-R%25C3%25A9cursivement_%25C3%25A9num%25C3%25A9rable.svg.png&w=640&q=50)
Conjuntos recursivamente enumeráveis
De Wikipedia, a enciclopédia encyclopedia
Na Teoria da computabilidade, tradicionalmente chamada teoria da recursão, um conjunto S de números naturais é chamado recursivamente enumerável, computavelmente enumerável, semi-decidível, demonstrável ou Turing-reconhecível se:
- Existe um algoritmo tal que o conjunto de números de entrada para qual o algoritmo pára é exatamente o conjunto de números em S.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2a/R%C3%A9cursivement_%C3%A9num%C3%A9rable.svg/320px-R%C3%A9cursivement_%C3%A9num%C3%A9rable.svg.png)
Ou, equivalentemente,
- Existe um algoritmo que enumera os membros de S. Isso significa que sua saída é simplesmente uma lista de membros de S: s1, s2, s3, ... . Se necessário, esse algoritmo pode rodar para sempre.
A primeira condição sugere porque o termo semi-decidível às vezes é usado; o segundo sugere porque computavelmente enumerável é usado.
Na teoria de complexidade computacional, a classe de complexidade que contém todos os conjuntos recursivamente enumeráveis é RE (recursivamente enumerável). Na teorica da recursão, o Reticulado de conjuntos recursivamente enumeráveis sobre inclusão é denominado .