5
$\begingroup$

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?

  • 1
    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.)2011-12-26
  • 1
    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$.2011-12-26

1 Answers 1

5

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.