In computability theory two sets A , B {\displaystyle A,B} of natural numbers are computably isomorphic or recursively isomorphic if there exists a total computable and bijective function f : N → N {\displaystyle f\colon \mathbb {N} \to \mathbb {N} } such that the image of f {\displaystyle f} restricted to A ⊆ N {\displaystyle A\subseteq \mathbb {N} } equals B ⊆ N {\displaystyle B\subseteq \mathbb {N} }, i.e. f ( A ) = B {\displaystyle f(A)=B}.

Further, two numberings ν {\displaystyle \nu } and μ {\displaystyle \mu } (of the same set of objects) are called computably isomorphic if there exists a computable bijection f {\displaystyle f} so that ν = μ ∘ f {\displaystyle \nu =\mu \circ f}. Computably isomorphic numberings induce the same notion of computability on a set.

Theorems

By the Myhill isomorphism theorem, the relation of computably isomorphic coincides with the relation of mutual one-one reducibility.

  • Rogers, Hartley Jr. (1987), Theory of recursive functions and effective computability (2nded.), Cambridge, MA: MIT Press, ISBN0-262-68052-1, MR.