Computable isomorphism
From Wikipedia, the free encyclopedia
In computability theory two sets of natural numbers are computably isomorphic or recursively isomorphic if there exists a total computable and bijective function such that the image of restricted to equals , i.e. .
Further, two numberings and (of the same set of objects) are called computably isomorphic if there exists a computable bijection so that . Computably isomorphic numberings induce the same notion of computability on a set.
Theorems
By the Myhill isomorphism theorem, the relation of computably isomorphic coincides with the relation of mutual one-one reducibility.[1]