Computable isomorphism

From Wikipedia, the free encyclopedia
Jump to: navigation, search

In computability theory two sets A;B \subseteq \N of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function f \colon \N \to \N with f(A) = B.

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.

References[edit]