Let f1, f2, ... be an enumeration of the partial recursive functions. We say fi≠fj if there is some input x such that either
- fi(x) halts and fj(x) does not halt, or
- fj(x) halts and fi(x) does not halt or
- both fi(x) and fj(x) halt and fi(x)≠fj(x).
MIN is in Σ2 of the arithmetic hierarchy. For all j<i you need to check that for some input x, one of the three conditions above hold (which might require a ∀ to check that a machine does not halt). We have two unbounded quantifiers (the first "for all" is bounded) so MIN is in Σ2.
In fact this is tight for Turing reductions, every problem in Σ2 reduces to MIN.
For an interesting open question we turn to a variation called MIN*. We say fi≠*fj if one of the three conditions above hold for infinitely many x. MIN* contains the set of indices i such that for all j<i, fi≠*fj.
Without too much effort one can show MIN* is in Π3. Marcus Schaefer shows that every language in Π3 can be Turing reduces to an oracle that encodes both MIN* and K where K is the usual halting problem. We would like to remove K which is equivalent to the following open question
Read Schaefer's paper for details and many more interesting facts about MIN and MIN*.