The language of TMs accepting some word starting with 101

Question

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

Answer 1

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

Answer 2

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?

Answer 3

According to $Rice's$ $theorem$,

$\qquad$ $L$ = { $\langle M \rangle$ | $L (M) ∈ P$ } is undecidable if $P$ is a non-trivial semantic property of $\qquad$$L(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?).

Answer 4

By Rice's theorem, it is undecidable if $M$ accepts a language with a non-trivial property (there are languages that have the property and others that don't). "Includes a string starting 101" is a non-trivial property.