# The language of TMs accepting some word starting with 101

I have a homework question about the properties (decidability, Turing-recognizability, etc.) of the language

$$L = \{ \langle M \rangle | \text{M is a TM and M accepts some string w which has 101 as a prefix} \}.$$

I have made an attempt at showing decidability of $L$:

On input $\langle M, w\rangle$ (where $M$ is a TM and $w \in \sigma^*$):

1. Simulate $M$ on $w$.
2. If $M$ rejects and halts, reject. If $M$ accepts and halts, accept.

However, I'm not sure about moving forward after this. I do not want a solution, but I want some ideas/techniques as to what else I can prove about $L$.

First, it should be intuitive that L is not decidable. Decidable means that you can can tell in finite amount of time if a word (in this case, coding of turing machine) is in L. In m opinion, this should be one of the first things that should come in mind while solving these kinds of questions.

Note that there are infinitely many string that have $101$ as prefix (for example $101, 1011, 10111$, or in general, $101^i$ for $i \geq 1$).

There are several problems with your solution. First, the input for a TM for $L$ is $\langle M\rangle$, and not $\langle M, w\rangle$. Second, what happens if $M$ doesn't halt on $w$? Your TM for $L$ also doesn't halt, and hence can't decide $L$.

You can show that $L \in RE\setminus R$.

Show that $L \in RE$ by describing a TM $M'$ that recognizes $L$ (meaning, on input $\langle M\rangle$, if $\langle M\rangle \in L$ then $M'$ accepts $\langle M\rangle$, otherwise $M'$ rejects or doesn't halt.

An easy way to show that $L\notin R$ is a reduction $f$ from the halting problem $HP$ to $L$, such that if $\langle M,w\rangle \in HP$ , then $f(\langle M,w\rangle) \in L$ (Hint: $f(\langle M,w\rangle)$ we accept any input if and only if $M$ stops on $w$).

• Please mention that $HP$ is the halting problem. It could also be useful to single out a specific variant of the halting problem. – Yuval Filmus Mar 31 '14 at 22:35

Hint: It is undecidable whether a given Turing machine accepts the empty string, or any other fixed string for that matter. Given a Turing machine, we can come up with a different Turing machine that rejects immediately if the input is not (say) $101$, and otherwise simulates the original Turing machine. What does that imply?

• I don't think I can immediately reject if the input is not 101, since M can accept other strings (but does not have to). All we know is that it does accept some string that starts with 101. – Bob Mar 31 '14 at 21:53
• Well, the hint is aimed at showing that $L$ is not decidable. – Yuval Filmus Mar 31 '14 at 22:07

According to $$Rice's$$ $$theorem$$,

$$\qquad$$ $$L$$ = { $$\langle M \rangle$$ | $$L (M) ∈ P$$ } is undecidable if $$P$$ is a non-trivial semantic property of $$\qquadL(M)$$.

$$\qquad$$ P is the set of all languages that satisfies a particular property

If the following two properties hold, it is proved as undecidable −

Property 1 (Semantic) − If $$M_1$$ and $$M_2$$ recognize the same language, then either $$\qquad\qquad\langle M_1 \rangle ,\langle M_2\rangle \in L$$ or $$\langle M_1 \rangle ,\langle M_2\rangle \notin L$$.

Property 2 (Non-trivial) − There exists $$M_1$$ and $$M_2$$ such that $$\langle M_1 \rangle \notin L$$ and $$\langle M_2 \rangle \notin L$$.

Now,

$$\quad$$ 1) For any two TMs, $$M_1$$ and $$M_2$$ with $$L(M_1) = L(M_2)$$ either both $$M_1$$ and $$M_2$$ both accept all strings starting with 101 or both don't accept.

$$\quad$$ 2) There exists TMs that accepts strings starting with 101 and not accepting strings that starts with 101.

Therefore, the property of the language of a TM to start with 101 is a semantic and non-trivial. Hence, according to Rice's theorem, the given language is undecidable.

$$L$$ is recognizable as TMs that accepts when given as input strings starting with 101 always accepts and halts. But complement of $$L$$ isn't recognizable as both $$L$$ and complement of $$L$$ being recognizable will mean that $$L$$ is decidable(why?).