Conjuntos recursivamente enumeráveis: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 9:
A primeira condição sugere porque o termo semidecidível as 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. Na teorica da recursão, o Reticulado de conjuntos recursivamente enumeráveis sobre
== Definição Formal ==
Um conjunto S de números naturais é chamado recursivamente enumerável se existe uma função computável na qual o domínio é exatamente S, significando que a função é definida se e somente se sua entrada é membro de S.
A definição pode ser extendida para um conjunto arbitrário A usando número de Gödel para representar os elementos do conjunto e declarar um subconjunto de A para ser recursivamente enumerável se o conjunto dos números de Gödel correspondentes é recursivamente enumerável.
== Formulações equivalentes ==
== Exemplos ==
== Propridedades ==
== Remarcações ==
== Referências ==
| |||