Vypočitatelný izomorfismus - Computable isomorphism

v teorie vypočítatelnosti dvě sady ${ displaystyle A; B subseteq mathbb {N}}$ z přirozená čísla jsou vypočítatelně izomorfní nebo rekurzivně izomorfní pokud existuje celkový bijektivní vypočítatelná funkce ${ displaystyle f colon mathbb {N} do mathbb {N}}$ s ${ displaystyle f (A) = B}$. Podle Věta o izomorfismu Myhill,^[1] vztah vypočítatelného izomorfismu se shoduje se vztahem redukce jedna ku jedné.

Dva číslování ${ displaystyle nu}$ a ${ displaystyle mu}$ jsou nazývány vypočítatelně izomorfní pokud existuje vypočítatelná bijekce ${ displaystyle f}$ aby ${ displaystyle nu = mu circ f}$

Vypočitatelně izomorfní číslování indukuje stejnou představu o vypočítatelnosti na množině.

Reference

• Rogers, Hartley, Jr. (1987), Teorie rekurzivních funkcí a efektivní vypočítatelnost (2. vyd.), Cambridge, MA: MIT Press, ISBN  0-262-68052-1, PAN  0886890.

Tento matematická logika související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.