Computable isomorphism

From Wikipedia, the free encyclopedia

In computability theory two sets A and B are computably isomorphic or recursively isomorphic if there exists a bijective computable function f with f(A) = B.

Two numberings ν and μ are called computably isomorphic if there exists a bijective computable function f so that

\nu = \mu \circ f.\,

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

Comp Sci logo This computer science-related article is a stub. You can help Wikipedia by expanding it.