Reducing the halting problem for a language with strings that include at least one 1
Original Question: 

$L_1 = \{w \in \{0|1\}^* | \text{ w is a sequence of one or more 1's } \}$

$L_2 = \{\langle M \rangle | \text{ Turing machine } M \text{ decides } L \}$

prove that $L_2$ is undecidable.



Answer:

For first part you are correct.
First language $L_1$ is indeed decidable. Actually it is regular as represented by regular expression $1^+$.

Now coming to second one $L_2$. This language is as you said undecidable. And you can prove it by reducing halting problem which is known to be undecidable to this problem.

For doing this you have to create an instance of problem in question such that solving it gives us solution of halting problem.

Now formally we can define turing machine $\tau\langle M, w\rangle =M'$. Where $M'$ is a turing machine which started on input $x$ checks if $x$ is of form $1^+$. If no then it rejct it immediately. Otherwise it erases $x$ from it's tape then copies $M$ and $w$ on its tape and simulates $M$ on $w$. If $M$ stops then it accepts $x$(which it have erased).

Proof of validity of reduction:

$M$ halts on $w$ $\implies$ $M'$ accepts  all and only strings of form $1^+$.

$M$ does not halt on $w$ $\implies$ $M'$ accepts empty set. In particular it does not accept strings of form $1^+$.

So now if there would be any turing machine that decides $L_2$ then we can use it to find whether $M'\in L_2$ or not? If it outputs yes then we infer that original $M$ halts on $w$. Otherwise we infer that $M$ does not halt on $w$.

And because we know that halting problem is undecidable we conclude that no such turing machine exists which can decide $L_2$ and consequently $L_2$ is undecidable.

Hence proved.