[Math] Is a semirecursive (recursively semidecidable) set enumerable

computabilitylogic

According to Computability and Logic (5th ed.), semi-recursive = recursively semidecidable, and according to this Wikipedia's article "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?

Best Answer

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.

Related Question