computability theory Computability theory, also known as recursion theory, is a branch of mathematical logic, computer science, and the theory of computation that originated in the 1930s with the study of computable functions and Turing degrees. The field has since ex ...

two sets

A, B

natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...

s are computably isomorphic or recursively isomorphic if there exists a total computable and

bijective In mathematics, a bijection, bijective function, or one-to-one correspondence is a function between two sets such that each element of the second set (the codomain) is the image of exactly one element of the first set (the domain). Equival ...

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

*. Reduction (complexity) {{mathlogic-stub