# Reducing universal language to language of palindromes

I am trying to understand proof for proving language of all palindromes is undecidable from these slides. It tried to reduce universal language to language of all palindromes on alphabet.

The two slides are as follows:

Let me define:

1. $$L_u=\{ | \text{ M accepts w}\}$$
2. $$L_{pal}=\{M | L(M) = \text{palindromes} \}$$

If I am correct, we reducing $$L_u$$ to $$L_{pal}$$ means converting inputs to $$L_u$$ (which is $$$$) to input to $$L_{pal}$$(which is $$M$$ in above definition 2 and $$M'$$ in diagram). This is done above in blue boxes.

Doubts:

1. I dont get what is $$x$$ here, when it says Accept x and x is palindrome? If it says x is palindrome, then it must be some string. But it is not the input to any of $$L_u$$ or $$L_{pal}$$? Then why $$M'$$ has input $$x$$ and what exactly it is? Any random string?

2. Also how $$M_{pal}$$ saying

• YES means $$L(M')=\{palindromes\}$$ iff M accepts w
• NO means $$L(M')\neq\{palindromes\}$$ iff M doesnt accept w

I feel $$M'$$ accepts if both:

• $$M$$ accepts $$w$$
• $$x$$ is plalindrome

Making $$L(M') = \{w,x\}$$ Now saying YES: $$L(M')=\{palindromes\}$$, means both $$w$$ and $$x$$ are palindromes, not just $$M$$ accepts $$w$$, is it correct?

3. But if NO: $$L(M')\neq\{palindromes\}$$ means of either or both of one condition is false (but not necessarily both):

• $$M(w)$$ accepts
• $$x$$ is palindrome

So even if $$x$$ is not a palindrome, $$M$$ might accepts $$w$$. Then how we can deduce M doesnt accept $$w$$ if answer is NO?