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

Improve this question
$\endgroup$
7
  • $\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, 2020 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, 2020 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, 2020 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, 2020 at 15:56
  • $\begingroup$ Yet another thing to try is diagonalization. $\endgroup$
    – Yuval Filmus
    May 23, 2020 at 16:02

2 Answers 2

Reset to default
1
$\begingroup$

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

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Isn't the answer always true in this case? wolframscience.com/prizes/tm23/images/Shannon.pdf proves that 2 states are enough for a universal machine in its traditional form. $\endgroup$
    – Bernardo Subercaseaux
    May 23, 2020 at 23:22
  • $\begingroup$ I don't think I get you . I meant to use reduction based on the above fact . which means :f(x) = x,2 $\endgroup$
    – Doron Bruder
    May 24, 2020 at 9:11
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)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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