Computable isomorphism

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

Further, two numberings ν {\displaystyle \nu } and  μ {\displaystyle \mu } are called computably isomorphic if there exists a computable bijection  f {\displaystyle f} so that  ν = μ ∘ f {\displaystyle \nu =\mu \circ f} . Computably isomorphic numberings induce the same notion of computability on a set.

## Theorems

[edit]

By the Myhill isomorphism theorem, the relation of computable isomorphism coincides with the relation of mutual one-one reducibility.[1]

## References

[edit]

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

* Rogers, Hartley Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890.

P ≟ NP |

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

This mathematical logic-related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template