Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Is every recursively enumerable set $A \subseteq \mathbb{N}$ also recursive ?

I'm not particularly interested in a detailed proof or counterexample, just a quick argument why this affirmation should hold or not.

share|improve this question

1 Answer 1

up vote 8 down vote accepted

No, they are different.

For a set $A$ to be r.e. means (for example) that there is a computer program that (given enough time and memory) prints the elements of $A$, one by one, possibly with repetitions, possibly not in increasing order. On the other hand, for $A$ to be recursive, means that there is a program that, for any $n$, tells us whether $n\in A$ or not.

For example: The set of axioms of Peano Arithmetic is recursive. There are infinitely many (as there are infinitely many instances of induction), but given a formula, it is very easy to see whether it is one of these axioms or not.

The theorems of Peano Arithmetic form an r.e. set: We can list it simply by enumerating all proofs.

On the other hand, assuming that these axioms are not contradictory, there is no algorithm that tells whether a given statement is a theorem or not (this is the famous Goedel incompleteness theorem). (Too bad? Things would be much simpler for us if we could have a machine verifying our conjectures for us.)

The halting problem was the first manifestation in computability theory of this difference between being recursive and being r.e. The linked Wikipedia page contains a sketch of the diagonal argument showing that the set $K$ is not recursive, where $K$ consists of all pairs $(a,b)$ such that $a$ codes a computer program, $b$ codes an input, and $a$ eventually halts with input $b$. On the other hand, it is obvious that $K$ is r.e.: List all triples $(a,b,c)$, $c$ a number, and print $(a,b)$ if and only if $a$ stops on input $b$ in precisely $c$ steps.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.