7
$\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.

$\endgroup$
6
$\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$.

$\endgroup$
  • 1
    $\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 Nov 30 '15 at 16:39
  • $\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 Nov 30 '15 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 Nov 30 '15 at 17:07
  • $\begingroup$ Try showing that if $f^{-1}$ is computable then $f$'s range is decidable. $\endgroup$ – Yuval Filmus Nov 30 '15 at 17:10
  • $\begingroup$ Thanks yet again. It seems so obvious --- now that you've said it:) $\endgroup$ – John Forkosh Nov 30 '15 at 17:20

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.