Computable isomorphism
In computability theory two sets [math]\displaystyle{ A;B \subseteq \N }[/math] of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function [math]\displaystyle{ f \colon \N \to \N }[/math] with [math]\displaystyle{ f(A) = B }[/math]. By the Myhill isomorphism theorem,[1] the relation of computable isomorphism coincides with the relation of one-one reduction. Two numberings [math]\displaystyle{ \nu }[/math] and [math]\displaystyle{ \mu }[/math] are called computably isomorphic if there exists a computable bijection [math]\displaystyle{ f }[/math] so that [math]\displaystyle{ \nu = \mu \circ f }[/math]
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
- Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, 1987, ISBN 0-262-68052-1.
 |
