Étant donné la fonction calculable, quelles sont les conditions de calcul de la fonction inverse?

Si $f:\mathbb{N}\rightarrow\mathbb{N}$ est calculable et a un inverse, dans quelles conditions est $f^{-1}$aussi calculable? Je ne pouvais pas trouver cela dans un manuel, et googler obtient de vagues suggestions sur le bijectif, mais je n'ai pas pu trouver un théorème clairement énoncé à cet effet. D'un côté, le bijectif semble suffisant mais pas nécessaire, par exemple,$f(n)=2n$ n'est pas surjectif mais est inversible de façon calculable (pour une fonction totale inverse, utilisez le domaine soulevé $\mathbb{N}_\perp$ et mapper les nombres impairs vers $\perp$). En plus d'une réponse, une référence à un théorème / preuve serait formidable, ou tout simplement le nom d'un théorème pertinent afin que je puisse le google avec succès.

Cette question m'est venue à l'esprit concernant la pensée suivante (que je n'ai pas non plus pu trouver dans un manuel ou sur quoi que ce soit sur Google). La distinction entre$f$ calculable et $f^{-1}$non, par opposition aux deux calculables, semble un peu analogue à une distinction re versus récursive. Peut-on l'exprimer avec rigueur?

Par exemple, considérez $f:E\rightarrow E$, avec $f\in D=[E\rightarrow E]$ le domaine d'espace de fonction (Scott ou Lawson continu) d'un domaine $E$. Laisser$K_D$ être $D$des éléments compacts, $\downarrow f=\lbrace g\in K_D\mid g\sqsubseteq f\rbrace$, par lequel $f=\sqcup\downarrow f$, le tout de la manière habituelle. alors$f$ est calculable si une énumération de $\downarrow f$ est de même, $f^{-1}$ est calculable si une énumération de $\downarrow f^{-1}$ is re Donc, si les deux sont calculables, ce qui signifie que les deux énumérations sont re, alors cela me semble (du moins) analogue à récursif.

Bien sûr, ce n'est pas tout à fait la même chose que récursive, car si $\mathbb{N}_f\subseteq\mathbb{N}$ est une énumération de $\downarrow f$, et de même pour $\mathbb{N}_{f^{-1}}$, puis $\mathbb{N}_{f^{-1}}\neq\mathbb{N}\setminus\mathbb{N}_f$(au moins je ne le suppose pas). Mais il semble y avoir une sorte d'idée analogue essayant de s'exprimer. Alors, comment pourriez-vous formuler ce genre de chose avec rigueur? Parmi les premières étapes, je pense que vous voudriez exprimer$\mathbb{N}_{f^{-1}}$ en terme de $\mathbb{N}_f$, mais je ne vois pas comment procéder pour le configurer (une suggestion sur la façon de procéder?).

Alors, cette idée est-elle également bien connue et discutée? Un manuel ou une référence Google (ou un terme de recherche compatible Google) serait parfait. Merci.

Disons qu'une fonction calculable $f$ est inversible s'il existe une autre fonction calculable $g$ celui en entrée $y$ trouve soit $x$ tel que $f(x) = y$ ou retourne $\bot$ quand $y$ n'a pas de préimage.

Pour cette définition, on peut montrer qu'une fonction calculable $f$ est inversible si et seulement si sa plage est décidable, c'est-à-dire que nous pouvons décider si une entrée donnée a une préimage sous $f$.