Computable isomorphism explained

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 \colon \N \to \N such that the image of f restricted to A\subseteq \N equals B\subseteq \N , i.e. f(A) = B .

Further, two numberings

\nu and \mu are called computably isomorphic if there exists a computable bijection f so that \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 computable isomorphism coincides with the relation of mutual one-one reducibility.^[1]

References

• .

Notes and References

1. Theorem 7.VI, Hartley Rogers, Jr., Theory of recursive functions and effective computability