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 \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.Theorem 7.VI, Hartley Rogers, Jr., Theory of recursive functions and effective computability

References

{{citation

| last = Rogers | first = Hartley Jr. | author-link = Hartley Rogers, Jr.

| edition = 2nd

| isbn = 0-262-68052-1

| location = Cambridge, MA

| mr = 886890

| publisher = MIT Press

| title = Theory of recursive functions and effective computability

| year = 1987}}.

Category:Reduction (complexity)