Minimal Indices

Let's look at some interesting questions about the set of smallest programs. This post relates more to recursion theory than complexity theory. No time bounds today.

Let f₁, f₂, ... be an enumeration of the partial recursive functions. We say f_i≠f_j if there is some input x such that either

1. f_i(x) halts and f_j(x) does not halt, or
2. f_j(x) halts and f_i(x) does not halt or
3. both f_i(x) and f_j(x) halt and f_i(x)≠f_j(x).

Define the set MIN as the set of indices i such that for all j<i, f_i≠f_j. How hard is the set MIN?

MIN is in Σ₂ 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 Σ₂.

In fact this is tight for Turing reductions, every problem in Σ₂ 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 Π₃. Marcus Schaefer shows that every language in Π₃ 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

Does K Turing reduce to MIN^*?

Read Schaefer's paper for details and many more interesting facts about MIN and MIN^*.