Prove that a language A is c.e. iff it is the range of a partially computable function

Question

I am having trouble in formally proving this statement. I looked online and most proofs just mention that it is the part of the definition of c.e (computably enumerable) language.

Answer 1

I'm going to assume that you're using as your definition of a set being computably enumerable that there is a computable procedure for listing the elements of the set. In this case, the direction $A$ is computably enumerable implies that $A$ is the range of a partial computable function is pretty easy: just define a function $f$ by $f(n)=$ the $n^{th}$ element in the listing of the elements of $A$. Then $f$ is in fact total computable, since to compute $f(n)$ for any $n$ you just run the computable procedure to list the elements of $A$ until $n$ elements have been listed and then just output the $n^{th}$ one.

In the other direction, if $A$ is the range of some partial computable function $f$, then you need to come up with a computable procedure for listing the values of $f(n)$ for all $n$ such that $f(n)$ halts. So e.g. your procedure could start by running the computation $f(0)$ for 1 step, then running $f(0)$ and $f(1)$ both for 2 steps, and so forth, and whenever any of the computations halt outputting the value you get. In this way, you'll eventually list all of the values in the range of $f$, hence all of the elements of $A$.