2. (12.5 points) LR = { M',s> : s ? L(M') and sR ?? L(M') }. For example, if L(M1) = {aab, baa, abb}, then M1,aab> ?? LR because aab and aabR are both strings in L(M1); M1,abb> ? LR because abb ? L(M1) and abbR ?? L(M1); and M1,bbab> ?? LR because bbab ?? L(M1).

Prove that LR ?? D using a mapping reduction from H to LR: M,w> ? H iff M#,ab> ? LR. Your mapping reduction function R must define the TM M# appropriately, and return M#,ab>.

Argue that if there was a TM called Oracle that could decide if M#,ab> ? LR , then that Oracle could also decide if M,w> ? H. But since H ?? D ...