Was sind bei gegebener berechenbarer Funktion die Bedingungen für die Berechenbarkeit der inversen Funktion?

Wenn berechenbar ist und eine Umkehrung hat, unter welchen Bedingungen ist auch berechenbar? Ich konnte das in einem Lehrbuch nicht finden, und beim Googeln werden einige vage Vorschläge zum Bijektiv gemacht, aber ich konnte keinen klar formulierten Satz zu diesem Zweck finden. Nebenbei scheint das Bijektiv ausreichend, aber nicht notwendig zu sein, z. B. ist nicht surjektiv, sondern rechnerisch invertierbar (für eine inverse Gesamtfunktion verwenden Sie die angehobene Domäne und ordnen Sie ungerade Zahlen wieder ). Zusätzlich zu einer Antwort wäre ein Verweis auf einen Satz / Beweis großartig, oder nur der Name eines relevanten Satzes, damit ich ihn erfolgreich googeln kann.f - 1 f ( n ) = 2 n N ⊥$f:\mathbb{N}\rightarrow\mathbb{N}$$f^{-1}$$f(n)=2n$$\mathbb{N}_\perp$$\perp$

Diese Frage kam mir in Bezug auf den folgenden Gedanken in den Sinn (den ich auch in einem Lehrbuch oder bei Google nicht finden konnte). Die Unterscheidung zwischen berechenbar und nicht gegenüber beiden berechenbar scheint irgendwie analog zu einer Unterscheidung zwischen re und rekursiv zu sein. Kann das konsequent ausgedrückt werden?f - $f$$f^{-1}$

Betrachten Sie zum Beispiel , wobei die (Scott- oder Lawson-kontinuierliche) Funktionsraumdomäne einer Domäne . Lassen seine ‚s kompakte Elemente, , wobei , die alle in der üblichen Weise. Dann ist berechenbar, wenn eine Aufzählung von re ist. In ähnlicher Weise ist berechenbar, wenn eine Aufzählung von re ist. Wenn also beide berechenbar sind, was bedeutet, dass beide Aufzählungen re, dann das scheint (zumindest für mich) irgendwie analog zu rekursiv.f ∈ D = [ E → E ] E K D D ↓ f = { g ∈ K D ∣ g ⊑ f } f = ⊔ ↓ f f ↓ f f - 1 ↓ f - $f:E\rightarrow E$$f\in D=[E\rightarrow E]$$E$$K_D$$D$$\downarrow f=\lbrace g\in K_D\mid g\sqsubseteq f\rbrace$$f=\sqcup\downarrow f$$f$$\downarrow f$$f^{-1}$$\downarrow f^{-1}$

Natürlich ist es nicht ganz dasselbe wie rekursiv, denn wenn eine Aufzählung von , und ähnlich für , dann (zumindest nehme ich das nicht an). Aber es scheint eine analoge Idee zu geben, die versucht, sich auszudrücken. Wie könnten Sie so etwas konsequent formulieren? Unter den ersten Schritten würde ich denken, dass Sie in Form von , aber ich sehe nicht, wie ich soll das auf (irgendein Vorschlag, wie man das macht?).$\mathbb{N}_f\subseteq\mathbb{N}$$\downarrow f$$\mathbb{N}_{f^{-1}}$$\mathbb{N}_{f^{-1}}\neq\mathbb{N}\setminus\mathbb{N}_f$$\mathbb{N}_{f^{-1}}$$\mathbb{N}_f$

Ist diese Idee also auch bekannt und diskutiert? Ein Lehrbuch oder eine Google-Referenz (oder ein Google-fähiger Suchbegriff) wäre großartig. Vielen Dank.

Nehmen wir an, dass eine berechenbare Funktion invertierbar ist, wenn es eine andere berechenbare Funktion , die bei der Eingabe entweder so findet , dass oder zurückgibt, wenn kein Vorbild hat.$f$$g$$y$$x$$f(x) = y$$\bot$$y$

Für diese Definition kann man zeigen, dass eine berechenbare Funktion genau dann invertierbar ist, wenn ihr Bereich entscheidbar ist, dh wir können entscheiden, ob eine gegebene Eingabe ein Vorbild unter .$f$$f$