Computable isomorphism

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

In computability theory two sets of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function with . By the theorem of Myhill,[1] the relation of computable isomorphism coincides with the relation of one-one reduction.

Two numberings and are called computably isomorphic if there exists a computable bijection so that

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

References[edit]

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