# How to show that language is Turing-recognizable and Turing-decidable?

How do I being to show that if $$L_{1}$$ is Turing-recognizable language over $$\Sigma=\{0,1\}$$, then $$L_{2} = \{ww^R | w ∈ L_{1} \}$$ is a Turing recognizable language too.

There is another similar problem, but instead of the language being recognizable, it's decidable. If anyone has any ideas on how to approach both of these problems, I'd be very thankful.

I'm very new to this topic and didn't find any similar problems online, so I'm looking for any kind of tips to solve these problems :)

The following is a description of an acceptor/decider for $$L_2$$. If the length $$|x|$$ of the input $$x$$ is odd, then reject. Otherwise consider the subword $$x_1$$ (resp $$x_2$$) consisting of the first (resp. last) $$|x|/2$$ symbols of $$x$$. Check whether $$x_1 = x_2^R$$. If that is not the case, then reject. Otherwise, simulate an acceptor/decider for $$L_1$$ on input $$x_1$$.

• Does this also help to show that language is also Turing-recognizable? Commented May 1, 2022 at 12:58
• Yes. This shows that if $L_1$ is recognizable, then $L_2$ is recognizable. Moreover, if $L_2$ is decidable, then $L_2$ is decidable. Commented May 1, 2022 at 15:00

Here is what a $$TM$$ for $$L_2$$ would do

We first check that input $$x$$ is not of odd length, if so we reject

Next we cut $$x$$ into two halves and check that the second half is the reversal of the first, hence the string is of the form $$ww^R$$

Next, we run the recogniser/decider of $$L_1$$ on $$w$$ (the first half of the input $$x$$), and output whatever it outputs

So we basically do whatever the recogniser/decider for $$L_1$$ does on $$w$$, but only after checking that the string $$x$$ is in the form $$ww^R$$ (which can be done in few steps)

Hopefully its clear that we would yield a recogniser/decider for $$L_2$$ form a recogniser/decider for $$L_1$$