Let f_{1}, f_{2}, ... be an enumeration of the partial
recursive functions. We say f_{i}≠f_{j} if there
is some input x such that either

- f
_{i}(x) halts and f_{j}(x) does not halt, or - f
_{j}(x) halts and f_{i}(x) does not halt or - both f
_{i}(x) and f_{j}(x) halt and f_{i}(x)≠f_{j}(x).

_{i}≠f

_{j}. How hard is the set MIN?

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 f_{i}≠^{*}f_{j} 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,
f_{i}≠^{*}f_{j}.

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^{*}.

## No comments:

## Post a Comment