-1
$\begingroup$

The language given is: $$L = \{\langle M\rangle \mid M \text{ accepts all strings of length at most 5} \}$$

I have to find the class to which this language belongs.

Now according to my intuition, recursive enumerable languages are those which have verifiers i.e for any string $w \in L$, there is a way to prove that $w \in L$ and for recursive languages, along with the above condition, for any string $w \notin L$, there is a way to prove that $w \notin L$.

Now, there will be finitely many strings which are of length less than or equal to five. We can make a TM which accepts all of these finitely many strings, and hence, the given language is recursively enumerable.

However, it is not recursive because to prove a string $w \notin L$, the only way to do that would be to "run" the TM on the string to prove that none of the strings greater than length five are accepted and since there are infinitely many such strings, we will never finish checking.

Is this approach correct?

$\endgroup$
  • 1
    $\begingroup$ "We can make a TM which accepts all of these finitely many strings, and hence, the given language is recursively enumerable." No, that just shows that $L$ is non-empty. $\endgroup$ – David Richerby Sep 14 '18 at 16:58
  • $\begingroup$ @DavidRicherby So would it mean that in addition to showing that it accepts all strings of length less than five, I would also have to show that it doesn't accept any string whose length is greater than five and since there are infinitely many such strings, the language would not be RE? $\endgroup$ – Gokul Sep 14 '18 at 17:15
  • 1
    $\begingroup$ You are given a description of a Turing machine. Your job is to determine whether or not it accepts all strings of length at most 5. Demonstrating that there is some other TM that accepts all such strings doesn't do anything towards that. $\endgroup$ – David Richerby Sep 14 '18 at 18:38
2
$\begingroup$

Your approach is slightly incorrect in the sense you have to built a Turing machine that given an input $M$ has to check whether $M$ accepts those strings and not build a Turing machine that itself accepts all those string. Note the difference here. And L is recursively enumerable because you can clearly build a Turing machine $M_1$ that on input $<M>$, constructs the corresponding Turing machine $M$, runs $M$ on all strings y of length at most 5. If $<M> \in L$, $M$ would accept all those strings and hence $M_1$ would accept $<M>$, verifying the construction. You can show its undecidable by reducing the Membership problem of Turing machines to L, i.e, $MP \leq_m L$.

$\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.