Numerous authors have considered the notion of computable reducibility (or FF-reducibility, or \(m\)-reducibility) on equivalence relations on the natural numbers. This holds of equivalence relations \(E\) and \(F\) (written \(E\leq_c^n F\)) if there exists a computable total function \(f\) on \(\omega\) such that \(x~E~y\) if and only if \(f(x)~F~f(y)\). Recent results include both the existence of such reductions and, for many pairs of equivalence relations, the impossibility of any such reduction.

Considering several of the proofs of non-reducibility, we have defined a weaker notion, finitary reducibility, to help analyze these negative results. We say that \(E\) is \(n\)-arily reducible to \(F\), written \(E \leq_c F\), if there are computable total functions \(f_1,\ldots,f_n:\omega^n\to\omega\) such that, for all \(j,k\leq n\) and all \(i_1,\ldots,i_n\in\omega\), \(i_j~E~i_k\) if and only if \(f_j(i_1,\ldots,i_n)~F~f_k(i_1,\ldots,i_n)\). If the indices of such functions can be found uniformly for every \(n\), then \(E\) is finitarily reducible to \(F\), written \(E\leq_c^{\omega}F\). In this talk we will give examples of how these new notions can be used.