Conjuntos recursivamente enumeráveis: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Linha 50:
== Propridedades ==
== Remarcações ==
De acordo com a tese de Church-Turing, qualquer função efetivamente calculável é calculável por uma máquina de Turing,e, assim, um concjunto S é recursivamente enumerável se e somente se existe algum algoritmo que produz uma enumeração de S. No entanto, isso não pode ser tomado como uma definição formal, visto que a tese de Church-Turing é uma conjectura informal, ao invés de um axioma formal. A definição de um conjunto recursivamente enumerável como o domínio de uma função parcial, em vez de o intervalo de uma função total recursiva, é bastante comum na literatura. Essa escolha é motivada pelo fato de que nas teorias de recursividade generalizada, como α-recursion teoria, a definição correspondente aos domínios foi feita para ser mais natural. Todavia, outros textos utilizam a definição em termos de enumerações, que é equivalente para conjuntos recursivamente enumeráveis.
== Referências ==
| |||