Computable isomorphism
In computability theory two sets of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function with .[further explanation needed] By the Myhill isomorphism theorem,[1] the relation of computable isomorphism coincides with the relation of mutual one-one reducibility.
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[]
- ^ 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.
Categories:
- Reduction (complexity)
- Theoretical computer science stubs
- Mathematical logic stubs