And even works for some non-recursive theories like the first-order theory of true arithmetic.

The basic idea is that you can determine whether a sentence X is in the theory or not by searching every natural number for counter-examples, and then using your halting oracle to check whether that search terminates or not.