Computable isomorphism

In computability theory two sets ${\displaystyle A;B\subseteq \mathbb {N} }$ of natural numbers are computably isomorphic or recursively isomorphic if there exists a total bijective computable function ${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$ with ${\displaystyle f(A)=B}$.^{[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 ${\displaystyle \nu }$ and ${\displaystyle \mu }$ are called computably isomorphic if there exists a computable bijection ${\displaystyle f}$ so that ${\displaystyle \nu =\mu \circ f}$

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

References[]

• Rogers, Hartley, Jr. (1987), Theory of recursive functions and effective computability (2nd ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, MR 0886890.

This mathematical logic-related article is a stub. You can help Wikipedia by .

• v
• t