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 concjuntoconjunto 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 como 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 α-recursiona teoria da α-recursão, 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.
