CSC 341 (Fall 2021)

Lab: Diagonalization

Problem: It Hurts My Head

Prove that the following languages are undecidable by reduction from a known undecidable language.

  1. \(L_1 = \{\, M \mid \text{\( M \) is a TM that accepts \( w^{R} \) whenever it accepts \( w \)} \,\}\).

    (Recall that \(w^{R}\) is the reversal of \(w\).)

  2. \(L_2 = \{\, (M, w) \mid \text{\( M \) is a TM that, on input \( w \), writes a '\$' on the tape} \,\}\).