# Prove by reduction that language of TMs accepting only words starting with 101 is undecidable

Before an exam in Computability I go through questions from last year's test. So the question is:

$$A= \{ \langle M\rangle x | M \text{ is a TM and accepts } x \}$$ $$L = \{ \langle M \rangle | M \text{ is a TM and halts only on words starting with 101 } \}$$ Prove by reduction that $$L$$ is undecidable. So this should be done without Rice's theorem.

I have troubles with constructing a reduction function, to show $$A\leq L$$.

Assume that $$L$$ is decidable. Then there is a Turing machine, $$T$$ that, on input $$M$$ decides whether $$M$$ halts only on words starting with $$101$$.
Using $$T$$, we will be able to decide $$A$$. Given $$\langle M\rangle x$$, we would like to decide if $$M$$ accepts $$x$$. In order to do that, imagine another Turing Machine $$M_x$$, that
1. Does not halt if input does not begin with $$101$$.
2. If input begins with $$101$$ ignores remaining input and simulates $$M$$ on $$x$$. If $$M$$ accepts $$x$$, $$M_x$$ halts else does not halt.
Now $$M$$ accepts $$x$$ if and only if $$M_x$$ belongs to $$L$$ (i.e. $$T$$ accepts $$\langle M_x\rangle$$).