0
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 23 at 15:37
  • $\begingroup$ @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. $\endgroup$ – MercyDude May 23 at 15:42
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 23 at 15:54
  • $\begingroup$ 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). $\endgroup$ – Yuval Filmus May 23 at 15:56
  • $\begingroup$ Yet another thing to try is diagonalization. $\endgroup$ – Yuval Filmus May 23 at 16:02
0
$\begingroup$

Hint 1: What happens when $k=2$?

Hint 2: Use a reduction from $\text{ALL}_{\text{TM}}$.

| cite | improve this answer | |
$\endgroup$
0
$\begingroup$

IDK if this is the most elegant way . But consider the language L = { : M is TM and L(M) =! emptyset and L(M) =! sigma*} lets call the above language nontrivial now its quite easy to prove the nontrivial is not in both RE and coRE with reduction from ATM for example. no that we have nontrivial we can use the following reduction : F() = from the complimentary language of nontrivial to MinTm both directions almost immediate and based on the fact that if k = 3 than M must be either empty or sigma* (since the TM has only two states qrej and qacc)

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.