Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I'm getting confused. According to Computability and Logic fifth edition, semirecursive = recursively semidecidable, and according to wikipedia , "recursively enumerable sets, also called semidecidable sets".

So I think maybe semidecidable = semirecursive

A set is called semidecidable if there is an algorithm that correctly decides when a number is in the set. But given this condition, is the set enumerable? On the other side, if a set is enumerable, is it semidecidable?

share|cite|improve this question
If I'm correctly interpreting your question, suppose we have a semidecidable set S along with the corresponding algorithm A. We can apply A in parallel to every possible number: spend one tick checking 1, then a tick checking 2, then another tick checking 1, then 2,3;1,2,3,4;1,2,3,4,5; etc, so A runs for an infinite time on every number. When A halts on a particular number X, we add it to the list, so everything in the semidecidable set will eventually be enumerated. (I'm not adding this as an answer because I don't know whether I'm interpreting the question correctly or not.) – Lopsy Dec 26 '11 at 4:55
I think definitions used by various authors are different. But one definition of semidecidable is this: A set $A$ is semi-decidable if there is an algorithm that, given an input $x$, eventually halts if $x\in A$ and runs forever if $x\not\in A$. That is equivalent to saying $A$ is infinite and there's an algorithm that lists all the elements of $A$. – Michael Hardy Dec 26 '11 at 6:00
up vote 4 down vote accepted

A set $A \subseteq \mathbb{N}$ is recursively enumerable just in case its characteristic function $f$ is computed by a Turing machine which halts for all and only those $n \in \mathbb{N}$ where $f(n) = 1$, that is to say, $n \in A$. An equivalent definition is that a recursively enumerable set is one whose members can be enumerated by an algorithm—although of course that algorithm may run forever, producing 'new' elements of $A$ in an endless stream.

So yes, semidecidable, semirecursive and recursively enumerable are just different terms for the same thing, although they emphasise different ways of looking at the phenomenon.

A recursively enumerable set is by definition enumerable (by an algorithm, a Turing machine etc.), but whether an arbitrary set $B$ is enumerable rather depends on what notion of enumerability is in play. For example, a countable set could be enumerable by $\omega$, but not recursively so. Similarly, it might be enumerable by some ordinal $\beta > \omega$ (and with the Axiom of Choice, any set will be so enumerable).

However, if we restrict our attention to recursively enumerable sets, the answer to your second question is yes: if a set is recursively enumerable, then it is semidecidable.

share|cite|improve this answer

Your Answer


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.