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:\mathbb{\mathbb{N}}\to \mathbb{\mathbb{N}}$ such that the image of $f$ restricted to $A\subseteq \mathbb{\mathbb{N}}$ equals $B\subseteq \mathbb{\mathbb{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.

References

• .

Template:Comp-sci-theory-stub Template:Asbox