2
$\begingroup$

Let $\langle M\rangle$ be the encoding of a Turing machine as a string over $\Sigma=\{0,1\}$, and consider the language $L=\{\langle M\rangle| \text{ $M$ is a Turing machine that accepts a string of length 2014} \}$

I want to use The Rice-McNaughton-Myhill-Shapiro Theorem (page 14 in this) to prove that $L$ is acceptable:

Say $\mathcal{L}$ is the set of all acceptable languages that contain strings of length 2014.

  • This set is monotone: every superset of a $L \in \mathcal{L}$ also contains strings of length 2014 so belongs to $\mathcal{L}$

  • This set is compact: for every language in $\mathcal{L}$ I can choose the finite subset with strings of length 2014.

  • This set is finitely acceptable: this is the part I'm confused about. Given every finite language of $\mathcal{L}$ is there a TM that can accept this set of finite languages?

$\endgroup$
4
  • 1
    $\begingroup$ You misread the last condition. It does not say what you wrote. $\endgroup$ – Andrej Bauer Jan 14 at 19:54
  • $\begingroup$ the set of all finite languages of $\mathcal{L}$ should be acceptable. Is that correct? $\endgroup$ – sprajagopal Jan 14 at 20:10
  • $\begingroup$ I guess the $\langle L \rangle$ is an encoding of the whole language itself. If each finite language of $\mathcal{L}$ is encoded like this, then set of encodings as a language should be acceptable $\endgroup$ – sprajagopal Jan 14 at 20:12
  • $\begingroup$ @sprajagopal You're right. Also, if I'm not mistaken, I think the problem is with the first condition. I've added an answer. In general, I think the theorem is more appealing for proving undecidability results (or showing that a language is not acceptable). $\endgroup$ – Bader Abu Radi Jan 15 at 12:31
2
$\begingroup$

The application of the theorem is not correct. Note that $\mathcal{L}$ is a set of acceptable languages, and consider your first point. If you take an acceptable language $L$ that contains a string of length 2014, then it is not necessarily that every superset of $L$ is acceptable.

Regarding the last point, the answer is yes. Given an encoding $\langle L\rangle$ of a finite language $L \in \mathcal{L}$, it is easy to check whether $L$ contains a string of length $2014$. Indeed, we're assuming that the encoding encodes all the words of $L$ in some order, so you can simply traverse the encoding to look for a word of length 2014. Specifically, quoting from the link you attached:

If $L$ is a finite language over $\Sigma$, then you can assume that $\langle L\rangle$ is the unique string over the alphabet $\Sigma \cup \{ \{,•,\}, \epsilon\}$ that contains the strings in $L$ in lexicographic order, separated by dots • and surrounded by braces {}, with $\epsilon$ representing the empty string. For example, if $\Sigma = \{ 0, 1\}$, and $L = \{\epsilon, 0,01,0110,01101001\}$, then $\langle L\rangle = \{ \epsilon•0•01•0110•01101001\}$.

So given such an encoding as input, you can go over it and check whether there is an infix of legnth 2014 between two consecutive dots •.

Finally, you can simply show that $L$ is acceptable directly by defining a TM that accepts it. Indeed, you can simply simulate the run of $M$ on all strings of length 2014 in parallel, and accepts iff $M$ accepts at least one of them.

$\endgroup$
2
  • $\begingroup$ That last paragraph makes the original problem clear. Still wondering why every superset of $L$ is not in $\mathcal{L}$. Every superset of $L$, say $S$, will contain the strings of 2014 length. I thought: since $S$ contains length 2014 strings, it must be in $\mathcal{L}$ but I think by definition $\mathcal{L}$ only contains acceptable strings so I cannot assume $S$ is acceptable. But is there a concrete way to prove that $S$ is not acceptable? Only then can we conclude this $\mathcal{L}$ is not monotone. The whole thing seems circular and going round and round... $\endgroup$ – sprajagopal Jan 15 at 15:05
  • $\begingroup$ You're right, in order to conclude that $S\in \mathcal{L}$, we need also to prove that $S$ is acceptable, for every suprset $S$. Unfortunately, this is far from being true. Consider for example the language $L = \{ 1^{2014}\}$, and the superset $L\cup A$, where $A$ is some non-acceptable problem (e.g., $A = \overline{Halt_{TM}} = \{ \langle M, w\rangle: \text{$M$ does not halt on $w$}\}$) $\endgroup$ – Bader Abu Radi Jan 15 at 17:39

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.