# Is this a correct application of Rice-Shapiro theorem?

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?

• You misread the last condition. It does not say what you wrote. – Andrej Bauer Jan 14 at 19:54
• the set of all finite languages of $\mathcal{L}$ should be acceptable. Is that correct? – sprajagopal Jan 14 at 20:10
• 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 – sprajagopal Jan 14 at 20:12
• @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). – Bader Abu Radi Jan 15 at 12:31

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\}$$.
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.
• 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... – sprajagopal Jan 15 at 15:05
• 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$}\}$) – Bader Abu Radi Jan 15 at 17:39