1
$\begingroup$

Let's define a recursively enumerable set as the domain of some program $p$, i.e., $\{x:\phi_p(x)\downarrow\}$.

There is another definition of a recursively enumerable set: it is either the empty set or the range of a computable function $f: \mathbb N\to \mathbb N$.

I'm trying to understand their equivalence.

One direction: suppose the second definition holds. Then define the program $p$ by the following conditions. The program $p$ takes an input $x$ and checks if $x\in f(\mathbb N)$: since $f$ is computable (say via $e$), the program $p$ can use $e$ to see, for each $n=0,1,\dots$, whether $f(n)=x$. If $x\in f(\mathbb N)$, then such $n$ will be found, and in this case we force $p$ to halt. Otherwise the program will work forever. For this program $p$, the domain of $\phi_p$ is $f(\mathbb N)$, q.e.d. Is this proof correct?

The other direction: This seems to be more difficult. I found this answer (which is supposedly what I need), from which the proof appears to be relatively easy, but I don't understand that proof. For example, I don't understand what $\Phi_{e,s}$ is.

$\endgroup$
3
  • $\begingroup$ Regarding $\Phi_{e,s}$ in the linked answer, it probably means that you're now indexing your partial recursive functions by pairs of numbers instead of single numbers. This is not a problem, since there are computable bijections between $\mathbb{N}\times\mathbb{N}$ and $\mathbb{N}$. Also, the proof you offered above seems to be the direction which does not involve $\Phi_{e,s}$ in the linked answer. $\endgroup$
    – Reveillark
    Commented Dec 1, 2019 at 1:05
  • $\begingroup$ @Reveillark If we read $\Phi_{e,s}(n)$ as $\phi_{\pi(e,s)}(n)$ where $\pi$ is the Cantor pairing function, then it's not clear to me why $A$ is the range of $f$ from that answer. $\endgroup$
    – user557
    Commented Dec 1, 2019 at 1:17
  • $\begingroup$ @Reveillark Actually, $\Phi_{e, s}$ is typically used to refer to the function computed by $\Phi_e$ where any computation that takes more than $s$ steps is considered to diverge. I.e. $\Phi_{e, s}$ means "run the program coded by $e$ for $s$ steps" $\endgroup$
    – Patrick Lutz
    Commented Dec 15, 2019 at 17:50

1 Answer 1

Reset to default
1
$\begingroup$

Your proof seems correct.

Here is another proof of the remaining direction: assume that $A=\operatorname{dom}\phi_e $ for some $e$. If $A$ is finite, then it is obviously an image of some computable function.

Now assume that $A$ is infinite. We will construct an infinite list $\langle c_n\mid n<\omega\rangle$: start from an empty list. We will add natural numbers into the list by considering the following procedure: for each $n$, check $\phi_e(n)\downarrow$. By dovetailing, we can evaluate $\phi_e(n)$ simultaneously for multiple $n$. If we finish computing $\phi_e(n)$ for given $n$, put $n$ into the list.

Since $A$ is infinite, out list is infinite. Let $f$ be the canonical enumeration of the list (i.e. $f(n)=c_n$.) By our construction of the list, $f$ is computable. Moreover, the image of $f$ is exactly $A$: if $n\notin A$, then $n$ will not be appear in our list.

$\endgroup$
3
  • $\begingroup$ I'm not sure I understand why we can perform infinitely many checks $\phi_e(n)\downarrow$. It will take forever to know for which $n$ $\phi_e(n)\downarrow$, won't it? $\endgroup$
    – user557
    Commented Dec 3, 2019 at 0:27
  • $\begingroup$ @user700016 This is the reason why I mentioned dovetailing. $\endgroup$
    – Hanul Jeon
    Commented Dec 3, 2019 at 2:24
  • 1
    $\begingroup$ Another way to say this is to define $f(n)$ inductively as follows: if there is some $m < n$ such that $\phi_e(m)$ halts in at most $n$ steps and $m$ is not already in the range of $f$ then set $f(n)$ to be the least such $m$. Otherwise let $f(n)$ diverge. This also works fine when $A$ is finite. $\endgroup$
    – Patrick Lutz
    Commented Dec 15, 2019 at 17:55

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .