lo.logic - a proof that L_min is not in coRE?

This is a problem with a surprisingly unique history. See the survey

Marcus Schaefer: A guided tour of minimal indices and shortest descriptions. Arch. Math. Log. 37(8): 521-548 (1998)

for more discussion. A proof that the problem is not coRE can be extracted from page 6 of that survey. For convenience I will give a self-contained argument here. Unfortunately it is not as simple as the "not-RE" proof!

We will show a Turing reduction from $L_{ALL}$ = { $ M~|~L(M) = Sigma^{star} $} to $L_{min}$, which suffices since $L_{ALL}$ is complete for the second level of the arithmetic hierarchy (implying it is not coRE). Intuitively, this means that given an oracle for $L_{min}$ we could decide the halting problem for machines which have oracles to the halting problem. A coRE language cannot have this property.

Let $hat{M}$ be the lexicographically first machine that accepts no inputs, under some encoding of machines.

First, we observe that given an oracle for $L_{min}$, we can effectively determine whether $M(M)$ halts or not, for a given $M$. (Recall this is enough to determine whether $M(x)$ halts or not, for given $M$, $x$.)

Define a machine $N_M$ which on input $t$, simulates $M(M)$ for up to $t$ steps and halts iff the simulation halts. To determine if $M(M)$ halts, make a list ${cal L}$ of all machines $M' neq hat{M}$ with $M' leq N_M$ such that $M' in L_{min}$. This list can be computed using an oracle for $L_{min}$. Observe that all such machines accept at least one input, since we excluded $hat{M}$ and they are all minimal. Via dovetailing, we can effectively find integers $t'$ such that each $M'(M')$ halts in $t'$ steps. Let $t''$ be the largest such $t'$. Then $M(M)$ halts iff $M(M)$ halts in at most $t''$ steps.

Now that we can decide the halting problem, we turn to computing a function version of $L_{min}$: given an oracle for $L_{min}$, we can output the minimum equivalent machine $M'$ to the input $M$. If $M in L_{min}$ this is easy. Otherwise we make a list ${cal L}$ of all machines that are in $L_{min}$ and are smaller than $M$. Then we begin to compute, for increasing inputs $x$, bit tables indicating the accept/reject behavior of all machines in ${cal L}$, on the inputs seen so far. (We can do this because we can solve the halting problem with the oracle!) When we find that a machine $M''$ differs on an input from $M$, we remove it from ${cal L}$. If $M$ is not minimal, there will eventually be only one machine $M'$ left which has not yet differed from $M$, since all machines in ${cal L}$ are minimal. If $M$ is not minimal then this $M'$ must be the minimum machine.

Finally, we define a machine $N$ that recognizes $L_{ALL}$ with an oracle for $L_{min}$. Let $M_{ALL}$ be the minimum Turing machine that accepts everything. If the input $M$ is less than $M_{ALL}$, output NO. ($M$ must reject something.) Otherwise compute the minimum machine equivalent to $M$. If $M = M_{ALL}$ then output YES otherwise output NO. Note $L(N) = L_{ALL}$.