Beräknarbar isomorfism

I beräkningsbarhetsteori två uppsättningar $A;B\subseteq \mathbb {N}$ av naturliga tal är beräkningsbart isomorfa eller rekursivt isomorfa om det finns en total bijektiv beräkningsbar funktion $f\colon \mathbb {N} \to \mathbb {N}$ med $f(A)=B$ . Enligt Myhill isomorphism theorem , sammanfaller förhållandet mellan beräkningsbar isomorfism med förhållandet mellan ömsesidig en - en reducerbarhet .

Två numrering $\nu$ och $\mu$ kallas beräkningsbart isomorfa om det finns en beräkningsbar bijektion $f$ så att $\nu =\mu \circ f$

Beräknarbart isomorfa numrering inducerar samma uppfattning om beräkningsbarhet på en mängd.

•    Rogers, Hartley, Jr. (1987), Theory of rekursiva funktioner och effektiv beräkningsbarhet (2:a upplagan), Cambridge, MA: MIT Press, ISBN 0-262-68052-1 , MR 0886890 .