0
$\begingroup$

A computably enumerable relation is a $R\subseteq \mathbb{N}^k$ such that there is some computable $S\subseteq \mathbb{N}^{k+1}$ and $R(\vec{x})\Leftrightarrow \exists y(S(\vec{x},y))$. A relation $S$ is computable if its characteristic function is, and a function is computable if it has an expression in terms of projection, constants, plus, times, the characteristic function of less-than, composition, and minimization.

I want to prove that $X\subseteq \mathbb{N}$ is computably enumerable iff there is a computable function $f:\mathbb{N}\rightarrow \mathbb{N}$ such that $X = \{f(x):x\in\mathbb{N}\}$. Besides the basic definition of a computable function I can also use induction, definition by cases, and the coding functions. We found a way of injectively mapping each tuple of natural numbers of arbitrary length to a single natural number, and the function $\ell(x)$ maps any natural number to the length of the tuple represented by $x$. The function $th(x,y)$ maps to the $x$th element of tuple $y$. A hint given for the $\Rightarrow$ direction (I haven't even though about the $\Leftarrow$ direction because supposedly it's easy) is to use projection on coordinates 0 and 1, and to define it by cases, using the assumption that $X\ne \emptyset$.

My instincts tell me that I want to define $f(0)$ in some way as to make this map to the least value of $R(x)$, and $f(1)$ to the next largest, and so on. I can't define $f(0) = \mu x R(x)$, the minimization of $x$ in $R$, since $R$ is not necessarily computable and therefore $f$ would not necessarily be computable (a c.e. function being not necessarily computable). My brain keeps thinking of something like

$$f(0) = \begin{cases} \mu x S(x,0) \text{ if } \exists x (S(x,0)) \\ ...otherwise \end{cases}$$

but then this looks like it's heading down the wrong tracks and I'm not sure how to basically "scan down the list" of all possible values.

$\endgroup$
0
$\begingroup$

At the start of the second paragraph, do you mean to say $f$ is a computable function like in the title? If it is, you can enumerate $X$ just by computing $f(0), f(1), f(2) \ldots $ For the other direction, if $X$ is computably enumerable just enumerate it and define $f(0)$ as the first element you get, $f(1)$ as the second, and so on. If $X$ is finite and you run out of values, you can just define $f$ of anything higher as the same as $f(0)$

$\endgroup$
  • $\begingroup$ The definition of "computably enumerable" though, doesn't permit one to just enumerate it. The enumeration has to somehow be constructed from $S$. $\endgroup$ – Addem Mar 23 '17 at 23:19
  • $\begingroup$ The definition I am familiar with says that computably enumerable means there is an algorithm that generates all the elements in your set, each one in finite time. Under that definition you just run the algorithm. Wikipedia says it is equivalent that there is an algorithm that recognizes the set. $\endgroup$ – Ross Millikan Mar 23 '17 at 23:39
  • $\begingroup$ The definition I provided above is different. $\endgroup$ – Addem Mar 23 '17 at 23:42
0
$\begingroup$

I think I've found an answer. I don't traverse $X$ from least to greatest, but instead leverage the existence of an enumeration of all pairs. With this I define inductively a function that enumerates all pairs that satisfy $S$ and with that I define a function that maps to the pair and projects on the first coordinate.

[Edit, realized this is wrong because functions defined inductively are not necessarily computable.]

$\endgroup$

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.