Dada la función computable, ¿cuáles son las condiciones para la computabilidad de la función inversa?

Si es computable y tiene un inverso, ¿bajo qué condiciones es también computable? No pude encontrar eso en un libro de texto, y googlear tiene algunas sugerencias vagas sobre bijective, pero no pude encontrar un teorema claramente establecido a tal efecto. De antemano, el bijective parece suficiente pero no necesario, por ejemplo, no es sobreyectivo pero es computablemente invertible (para una función total inversa, use el dominio elevado y números impares de nuevo a ). Además de una respuesta, una referencia a un teorema / prueba sería genial, o simplemente el nombre de un teorema relevante para que pueda googlearlo con éxito.$f:\mathbb{N}\rightarrow\mathbb{N}$$f^{-1}$$f(n)=2n$$\mathbb{N}_\perp$$\perp$

Esta pregunta me vino a la mente con respecto al siguiente pensamiento (que tampoco pude encontrar en un libro de texto o en Google). La distinción entre $f$ computable y $f^{-1}$ no, versus ambos computable, parece análoga a una distinción re versus recursiva. ¿Se puede expresar rigurosamente?

Por ejemplo, considere , con el dominio espacio funcional (Scott-o Lawson-continua) de un dominio . Supongamos que son los elementos compactos de , , por lo que , todo de la manera habitual. Entonces es computable si una enumeración de es re De manera similar, es computable si una enumeración de es re Así que si ambos son computables, lo que significa que ambas enumeraciones son re, entonces parece (al menos para mí) algo análogo a recursivo.$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}$

Por supuesto, no es lo mismo que recursivo, ya que si es una enumeración de , y de manera similar para , luego (al menos no lo creo). Pero parece haber algún tipo de idea análoga tratando de expresarse. Entonces, ¿cómo podría formular ese tipo de cosas rigurosamente? Entre los primeros pasos, creo que querrías expresar en términos de , pero no veo cómo configurarlo eso (alguna sugerencia de cómo hacer eso?).$\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$

Entonces, ¿esta idea también es conocida y discutida? Un libro de texto o una referencia de Google (o un término de búsqueda compatible con Google) sería genial. Gracias.

Digamos que una función computable es invertible si hay otra función computable que en la entrada encuentra tal que o devuelve cuando no tiene preimagen.$f$$g$$y$$x$$f(x) = y$$\bot$$y$

Para esta definición, se puede mostrar que una función computable es invertible si y solo si su rango es decidible, es decir, podemos decidir si una entrada dada tiene una preimagen bajo .$f$$f$