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:

enter image description here

enter image description here

Let me define:

  1. $L_u=\{<M,w> | \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 $<M,w>$) to input to $L_{pal}$(which is $M$ in above definition 2 and $M'$ in diagram). This is done above in blue boxes.


  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?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.