  A Borel equivalence relation on a Polish space is said to be countable if all
of its equivalence classes are countable. Standard examples of countable Borel
equivalence relations (on the space of subsets of the integers) that occur in
recursion theory are: recursive isomorphism, Turing equivalence, arithmetic
equivalence, etc. There is a canonical hierarchy of complexity of countable
Borel equivalence relations imposed by the notion of Borel reducibility. We
will survey results and conjectures concerning the problem of identifying the
place in this hierarchy of these equivalence relations from recursion theory
and also discuss some of their implications.
