Examples (trivial and non-trivial) of computable functions whose inverse is not computable

Question

Can you give some examples (some trivial and some non-trivial) of computable functions whose inverse is not computable?

Answer 1

This is an expansion of the comment by Respawned Fluff. Suppose that $f$ is a partial computable function from $\mathbb{N}$ to $\mathbb{N}$ that is injective. We do not assume that the domain is computable.

Then the graph of $f$ is recursively enumerable - this is the set $G_f$ of all pairs $(x, f(x))$ for which $f(x)$ halts. (See below.)

So the set of pairs $H = (f(x),x)$ is also recursively enumerable - just enumerate $G_f$ but print the tuples in the opposite order. Note that $H$ is the graph of $f^{-1}$.

Now we can use $H$ to compute $f^{-1}$, as follows. Given $y$, enumerate $H$. If a pair $(y,z)$ is ever enumerated into $H$, halt and return $z$. This procedure will produce $f^{-1}(y)$ for every $y$ in the range of $f$, so it will compute $f^{-1}$.

---

It is a somewhat standard exercise to prove that if $f$ is a partial recursive function, then the graph of $f$ is r.e., and that if the graph of a function is r.e. then the function is partial recursive. This follows from the definition of a partial recursive function:

$f$ is a partial recursive function if and only if there is a Turing machine $M$ such that $f \simeq \phi_M$. That is, $f(x) = \phi_M(x)$ whenever $\phi_M(x)$ is defined, and $f$ is undefined whenever $\phi_M(x)$ is undefined.

So, given an partial recursive function $f$, we may simulate it on each input, and enumerate the pairs $(x,f(x))$ for which $f$ has a value. Similarly, given an enumeration of the graph and an input $y$, we can search the enumeration to see if $f(y)$ exists.

Answer 2

Disclaimer:

This is an incorrect example. I'm leaving it here because it might be beneficial to see why it breaks. The explanation is at the bottom.

Example:

Define the domain as

\begin{align} X &= \Big\{ \langle M, I, R\rangle\ \Big|\ R \text{ is the (finite) run of }M \text{ on input } I\Big\}\\ &\cup\; \Big\{ \langle M, I, \bot\rangle\ \Big|\ M \text{ does not stop on input } I\Big\} \end{align}

(the machines in $X$ are deterministic) and define $f$ as $$f\Big(\big\langle M,I,x \big\rangle\Big) = \big\langle M,I\big\rangle.$$

Given a deterministic Turing machine $M$, it has only one run $R$ on any input $I$, and either it stops or not, so $f$ is injective. On the other hand, the inverse function solves the halting problem, so it is not computable.

Why it is incorrect:

The issue is that according to the standard definition the domain of a partial computable function is tied to the function itself, namely, if the computation stops, then that point belongs to the domain. In other words one cannot constraint the domain arbitrarily and that poses problems if the domain we would like to use isn't computable itself.

To summarize, in the example above either:

• $f$ is computable, but not injective, because there are bad inputs like $\langle M,I,\bot\rangle$ for a machine $M$ that stops on input $I$ that would be mapped to $\langle M,I\rangle$;
• $f$ isn't computable, e.g. $f$ distinguishes bad inputs from good inputs, but then it is able to recognize $X$, which means it can solve the halting problem.

I hope this helps $\ddot\smile$

Answer 3

No, there is not. Let's $f$ a computable injective function and define the function $g$ such that

$$g(x)=y \Leftrightarrow f(y)=x$$

Then $g$ is effectively computable :

• On input $x$, simulate the computation of $f$ on all inputs until one of those computations (on input $y$) halts with result $x$. Then return the input $y$.

Note that even if $f$ is not injective or partial, we can still define such a $g$.