11
$\begingroup$

If $f:\mathbb{N}\rightarrow\mathbb{N}$ is computable and has an inverse, under what conditions is $f^{-1}$ also computable? I couldn't find that in a textbook, and googling gets some vague suggestions about bijective, but I couldn't find a clearly stated theorem to that effect. Offhand, bijective seems sufficient but not necessary, e.g., $f(n)=2n$ isn't surjective but is computably invertible (for a total function inverse, use lifted domain $\mathbb{N}_\perp$ and map odd numbers back to $\perp$). In addition to an answer, a reference to a theorem/proof would be great, or just the name of a relevant theorem so I can successfully google it.

This question came to mind regarding the following thought (which I also wasn't able to find in a textbook or google anything about). The distinction between $f$ computable and $f^{-1}$ not, versus both computable, seems kind of analogous to an r.e. versus recursive distinction. Can that be expressed rigorously?

For example, consider $f:E\rightarrow E$, with $f\in D=[E\rightarrow E]$ the (Scott- or Lawson-continuous) function space domain of some domain $E$. Let $K_D$ be $D$'s compact elements, $\downarrow f=\lbrace g\in K_D\mid g\sqsubseteq f\rbrace$, whereby $f=\sqcup\downarrow f$, all in the usual way. Then $f$ is computable if an enumeration of $\downarrow f$ is r.e. Similarly, $f^{-1}$ is computable if an enumeration of $\downarrow f^{-1}$ is r.e. So if both are computable, meaning both enumerations r.e., then that seems (to me at least) kind of analogous to recursive.

Of course, it's not quite the same thing as recursive, since if $\mathbb{N}_f\subseteq\mathbb{N}$ is an enumeration of $\downarrow f$, and similarly for $\mathbb{N}_{f^{-1}}$, then $\mathbb{N}_{f^{-1}}\neq\mathbb{N}\setminus\mathbb{N}_f$ (at least I don't suppose so). But there seems to be some kind of analogous idea trying to express itself. So how could you formulate that kind of thing rigorously? Among the first steps, I'd think you'd want to express $\mathbb{N}_{f^{-1}}$ in terms of $\mathbb{N}_f$, but I'm not seeing how to go about setting that up (any suggestion how to do that?).

So, is this idea also well-known and discussed? A textbook or google reference (or google-able search term) would be great. Thanks.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
10
$\begingroup$

Let us say that a computable function $f$ is invertible if there is another computable function $g$ that on input $y$ either finds $x$ such that $f(x) = y$ or returns $\bot$ when $y$ has no preimage.

For this definition, one can show that a computable function $f$ is invertible if and only if its range is decidable, that is, we can decide whether a given input has a preimage under $f$.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ Thanks so much, @YuvalFilmus , that's exactly what I was looking for. Could you also give me the name of that theorem (or some way to find it in the index of a textbook, or google it)? I'd like to study that a bit deeper (but there's no need to "cut-and-paste" it here). (And I take it when $f$ is many-to-one, then $g$ just returns the first $x$-preimage it finds as it munges through the $y$'s in $f$'s decidable range.) $\endgroup$
    – John Forkosh
    Commented Nov 30, 2015 at 16:39
  • 1
    $\begingroup$ I just came up with this theorem, so if it has a name I am unaware of it. The proof is a simple exercise along the lines indicated in your comment. $\endgroup$
    – Yuval Filmus
    Commented Nov 30, 2015 at 16:45
  • $\begingroup$ Thanks again, Yuval. Okay, I get it. And my sense is your condition is indeed the necessary one, though I'm not offhand seeing how to prove $f$'s range undecidable $\Rightarrow$ $f^{-1}$ not computable. Also, I'm thinking all this stuff must be well-known and done to death. It seems like such an obvious question to ask, but I just can't google a concrete answer. $\endgroup$
    – John Forkosh
    Commented Nov 30, 2015 at 17:07
  • 1
    $\begingroup$ Try showing that if $f^{-1}$ is computable then $f$'s range is decidable. $\endgroup$
    – Yuval Filmus
    Commented Nov 30, 2015 at 17:10
  • 3
    $\begingroup$ So if we have a (total) bijective computable function, then its inverse is always computable? :O $\endgroup$
    – byk7
    Commented Oct 26, 2020 at 8:30
1
$\begingroup$

Also note that if the function is injective and not necessarily surjective, then the inverse will be partial computable

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.