patternModerate
Given computable function, what are conditions for computability of inverse function?
Viewed 0 times
inversecomputablewhatarefunctioncomputabilityforconditionsgiven
Problem
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 $\mat
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 $\mat
Solution
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$.
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$.
Context
StackExchange Computer Science Q#50114, answer score: 10
Revisions (0)
No revisions yet.