# Is $MIN_{TM}$ not in $\overline{RE\cup coRE}$

Given the language:

$$MIN_{TM}$$= $$\{ \langle M,k\rangle: there\ exists\ a\ TM\ D\ s.t.\ L(M)=L(D)\ and\ D\ has\ less\ than\ k\ states \}$$

I need to prove if this language is in $$R$$ or $$RE-R$$ or $$coRE-R$$ or $$\overline{RE\cup coRE}$$.

I suspect this language is in $$\overline{RE\cup coRE}$$ but I can't prove it. (I Tried using reduction but no help).

• You can try very small values of $k$. The language TOT, of all total Turing machines, might come in handy – it is known to be $\Pi_2$-complete, and so neither r.e. nor co-r.e. – Yuval Filmus May 23 at 15:37
• @YuvalFilmus What do you mean by trying very small values of k, also what's the language TOT? I can't even manage to find it on the web. And I have no Idea what's $\Pi_2$-complete is so I assume I don't necessarily need it to prove this problem. – MercyDude May 23 at 15:42
• I told you what TOT is. It is also the second bullet here, where you can read all about $\Pi_2$-completeness, though as you mention, all you need to know is that a $\Pi_2$-complete language such as TOT is neither r.e. nor co-r.e. – Yuval Filmus May 23 at 15:54
• My suggestion (haven't checked whether it works – might depend on the exact Turing machine model) is to consider the special case of MIN_TM in which $k$ is some very small constant. Another suggestion is to try and relate MIN_TM to Kolmogorov complexity, which is known not to be computable (though this corresponds to the behavior of a Turing machine on a single input). – Yuval Filmus May 23 at 15:56
• Yet another thing to try is diagonalization. – Yuval Filmus May 23 at 16:02

Hint 1: What happens when $$k=2$$?
Hint 2: Use a reduction from $$\text{ALL}_{\text{TM}}$$.