recursive set of numbers of computable partial functions

Question

Is the set of numbers of computable partial functions from $\mathbb N\to\mathbb N$, taking only a finite number of values, recursive?

I think yes, but I have some problems with explaining it.

Answer 1

No, this set is not recursive. One way to prove it is by Rice's theorem, but I'll assume you haven't seen that theorem and I'll give a more elementary proof. Fix some computably enumerable but not computable set $X\subseteq\mathbb N$ and fix an algorithm $A$ that enumerates $X$. For each natural number $n$, let $f(n)$ be the number of an algorithm $B_n$ that does the following on any input $k\in\mathbb N$: Perform the first $k$ steps in the algorithm $A$ that enumerates $X$. If $n$ has been enumerated in that part of the enumeration, then output $k$; otherwise output $0$. (There is a recursive function $f$ that does this.) Notice that algorithm $B_n$ outputs only the value $0$ if $n\notin X$, but if $n$ is in $X$ and is enumerated at step $s$ by algorithm $A$ then $B_n$ outputs all natural numbers above $s$ (as well as $0$). So $f(n)$ is in the set you asked about if and only if $n\notin X$. By our choice of $X$, this is not computable.