Computable isomorphism

In computability theory two sets

of natural numbers are computably isomorphic or recursively isomorphic if there exists a total computable and bijective function

are called computably isomorphic if there exists a computable bijection

Computably isomorphic numberings induce the same notion of computability on a set.

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

This theoretical computer science–related article is a stub.

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

You can help Wikipedia by expanding it.