Obviously, B would be recursive if for every TCF f, there was an inverse fuction that would return all possible values, as we could just take these and then check if any of them is in A. However I cannot find a proof (or counter-proof) that you can invert TCFs this way. AFAIK, all injective functions are invertible, but can we also invert a non-injective function and compute all the possible inputs that would result in the desired output?


In general, no, we can't conclude that $B$ is recursive. We can choose $f$ so that $B$ is the halting problem, for instance.

To do that, choose any TM $M_0$ which halts on the empty input.

We define $f(x)$ as follows. Let $M,n$ be such that $\langle M, k \rangle = x$ where $\langle -, - \rangle$ is any computable pairing function (bijection). Then, run $M$ on empty input for $k$ steps. If that halts, return $\langle M \rangle$, otherwise return $\langle M_0 \rangle$.

It is then easy to verify that, using such $f$, we have

$$ \begin{array}{ll} B &= \{ \langle M' \rangle \ |\ \exists M,k. f(\langle M,k \rangle)= \langle M' \rangle \} \\ &= \{ \langle M' \rangle \ |\ \exists k. M' \mbox{ halts in $k$ steps } \} \\ &= \{ \langle M' \rangle \ |\ M' \mbox{ halts} \} \end{array} $$

With some more effort, we can even make $f$ injective, yet obtain the same $B$ (halting problem).

Indeed, a well-known result states that any RE nonempty set $A$ is the image of some total computable function $g: \mathbb N \to \mathbb N$. For the halting problem $A$ is infinite and RE, so there is such a $g$. Exploiting $g$ we can define $f(x)$ as $g(y)$ where $y$ is the least number such that $\{g(0),g(1),\ldots,g(y)\}$ contains exactly $x+1$ (non-duplicate) elements.

Note that $y$ exists since the image of $g$ ($A$) is infinite.

In such way the image of $f$ is the same as the one of $g$, i.e. $A$, but $f$ is now injective by construction. ($f$ is not surjective, of course)


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.