Computable isomorphism

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

Further, two numberings ν and μ (of the same set of objects) are called computably isomorphic if there exists a computable bijection f so that ν=μ∘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.