Obliczalny izomorfizm

W teorii obliczalności dwa zbiory ${\ Displaystyle A; B \ subseteq \ mathbb {N}}$ liczb naturalnych jest obliczalnie izomorficzne lub rekurencyjnie izomorficzne , jeśli istnieje całkowita obliczalna funkcja bijektywna ${\ Displaystyle f \ okrężnica \ mathbb {N} \ do \ mathbb {N}}$ z ${\ Displaystyle f (A) = B}$ . Z twierdzenia o izomorfizmie Myhilla wynika , że relacja izomorfizmu obliczalnego pokrywa się z relacją wzajemnej redukowalności jeden-jeden .

Dwie numeracje i ${\ displaystyle$$displaystyle \ nu = \ mu \$$mu}$ nazywane są obliczalnie izomorficznymi , jeśli istnieje obliczalna bijekcja tak, że $\$

Obliczalnie izomorficzne numeracje wywołują to samo pojęcie obliczalności na zbiorze.

•    Rogers, Hartley, Jr. (1987), Teoria funkcji rekurencyjnych i efektywnej obliczalności (wyd. 2), Cambridge, MA: MIT Press, ISBN 0-262-68052-1 , MR 0886890 .