The wikipedia article for semi-recursive sets (formally titled "recursively enumerable sets") claims:

A set S of natural numbers is called recursively enumerable if there is a partial recursive function whose domain is exactly S, meaning that the function is defined if and only if its input is a member of S.

The set S is the range of a total recursive function or empty. If S is infinite, the function can be chosen to be injective.

Why in the infinite case can we demand injectivity for the function?


Supposed $F$ is a total recursive function that takes infintely many different values. Then let $G(n)$ be defined by

  1. Read $n$.
  2. Let $S$ be the empty set.
  3. Repeat the following for $k=0,1,2,3\ldots$:
    1. Compute $x=F(k)$.
    2. If $x\in S$ already, then continue with the next $k$.
    3. Add $x$ to $S$.
    4. If $|S|=n+1$, then output $x$ and stop.
    5. Otherwise continue with the next $k$.

Then $G$ has the same range as $F$, and is injective.

Informally $F:\mathbb N\to\mathbb N$ can be viewed as a sequence of natural numbers. The above algorithm corresponds to removing the second and later occurrences of any output in the sequence. As long as there are infinitely many different numbers in the sequence, this still results in an infinite sequence, which will be computable.

| cite | improve this answer | |
  • $\begingroup$ However, $F$ is partial, not necessarily total. $\endgroup$ – BrianO Apr 7 '16 at 9:53
  • $\begingroup$ @BrianO: No -- it's easy to overlook, but the context of the claim was "The set $S$ is the range of a total recursive function or empty." The function that can be chosen to be injective (for an infinite set) is the one whose range is $S$, not the partial one in the previous paragraph whose domain was $S$. $\endgroup$ – hmakholm left over Monica Apr 7 '16 at 9:56
  • $\begingroup$ Ya know, ... I did overlook it, and it was easy ;) I used just the given definition of r.e. in the first paragraph — needlessly, I now think, as OP seems OK with the first claim in the second paragraph (that context you mention). $\endgroup$ – BrianO Apr 7 '16 at 10:01
  • $\begingroup$ @HenningMakholm In step 6, when you say "add $x$ to $S$, do you mean include the element $x$ in the set $S$? Thanks! $\endgroup$ – faux Apr 7 '16 at 13:33
  • $\begingroup$ @faux: Yes, $S := S \cup \{x\} $. $\endgroup$ – hmakholm left over Monica Apr 7 '16 at 13:45

When $f$ is a partial recursive function with an infinite range (hence an infinite domain), we can define $g$ by $$ g(n) = f(\,\mu_x(x\in dom(f) \land x\notin range(g\!\restriction\! n))\,) $$ or, less tersely, $$ g(n) = f(x), \text{where $x$ is least s.t. $x\in dom(f)$ and $x\notin range(g\!\restriction\! n))$}. $$ An iterative algorithm for $g$ goes something like this:

def g(n):
    x = 0
    halted = set()    # empty set
    while True:
        # Assertions:
        #     halted = set of pairs (k, f(k))
        #              where k < x and f halts on k in < x steps
        #     |halted| < n
        for each k <= x:
            # Here, dom(halted)   = {1st_coord_of(pair) | pair in halted}
            #       range(halted) = {2nd_coord_of(pair) | pair in halted}
            if k not in dom(halted) and (f halts on k in x steps with value y):
                if y not in range(halted):
                    add (k, y) to halted
                    if |halted| == n:
                        return y
        x = x + 1

This is a bit inefficient (it could save computations that haven't yet halted, and each time through the loop just do one more step for those) but here we're not concerned about complexity.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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