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 such that the image of restricted to equals , i.e. .

Further, 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.

Theorems

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

References

  1. Theorem 7.VI, Hartley Rogers, Jr., Theory of recursive functions and effective computability
  • Rogers, Hartley, Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890{{citation}}: CS1 maint: multiple names: authors list (link).


This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.