The Hierarchy of Equivalence Relations on the Natural Numbers Under Computable Reducibility
Samuel Coskey, Joel David Hamkins, Russell Miller · Computability · 2012
The notion of computable reducibility between equivalence relations on the natural numbers provides a natural computable analogue of Borel reducibility. We investigate the computable reducibility hierarchy, comparing and contrasting it with the Borel