isomorfismo computable

En la teoría de la computabilidad, dos conjuntos${\displaystyle A,B}$Los números naturales son computacionalmente isomorfos o recursivamente isomorfos si existe una función total computable y biyectiva.${\displaystyle f\colon \mathbb {N} \to \mathbb {N} }$de tal manera que la imagen de${\displaystyle f}$restringido a${\displaystyle A\subseteq \mathbb {N} }$igual${\displaystyle B\subseteq \mathbb {N} }$, es decir${\displaystyle f(A)=B}$.

Además, dos numeraciones${\displaystyle \nu }$y${\displaystyle \mu }$(del mismo conjunto de objetos) se denominan isomorfos computacionalmente si existe una biyección computable.${\displaystyle f}$de modo que${\displaystyle \nu =\mu \circ f}$Las numeraciones isomorfas computacionalmente inducen la misma noción de computabilidad en un conjunto.

Según el teorema de isomorfismo de Myhill , la relación de isomorfismo computacional coincide con la relación de reducibilidad mutua uno a uno . ^{[ 1 ]}

• Rogers, Hartley Jr. (1987), Teoría de las funciones recursivas y la computabilidad efectiva (2.ª  ed.), Cambridge, MA: MIT Press, ISBN 0-262-68052-1, SR 0886890 .