title: Let T = {<M> | M is a TM that accepts $w^R$ whenever it accepts w}. Show that T is undecidable
body: <blockquote>
    <p>Let T = {&lt;M> | M is a TM that accepts w<sup>r</sup> whenever it accepts w}.<br>
    Show that T is undecidable.</p>
  </blockquote>
  
  <p>I have two answers to this question - <a href="http://cseweb.ucsd.edu/classes/sp06/cse105/homework8.pdf" rel="noreferrer">San Diego</a>:</p>
  
  <blockquote>
    <p><strong>5.9</strong><br>
    Let T = { &lt;M> | M is a TM that accepts w<sup>r</sup>  whenever it accepts w }.</p>
    
    <p>Assume T is decidable and let decider R decide T.
    Reduce from A<sub>TM</sub> by constructing a TM S as follows:</p>
    
    <ul>
    <li>S: on input &lt;M,w>  
    
    <ol>
    <li>create a TM Q as follows:<br>
      On input x:            
    
    <ol>
    <li>if x does not have the form 01 or 10 reject. </li>
    <li>if x has the form 01, then accept. </li>
    <li>else (x has the form 10), Run M on w and accept if M accepts w. </li>
    </ol></li>
    <li>Run R on  </li>
    <li>Accept if R accepts, reject if R rejects.</li>
    </ol></li>
    </ul>
    
    <p>Because S decides A<sub>TM</sub>, which is known to be undecidable, we then know that T is not decidable</p>
  </blockquote>
  
  <p>Undisclosed source:</p>
  
  <blockquote>
    <ul>
    <li><p><strong>5.12</strong>  We show that <em>A</em><sub>TM</sub> ≤<sub>m</sub> <em>S</em> by mapping ‹<em>M</em>, <em>w</em>› to ‹<em>M'</em>› where <em>M'</em> is the following TM:</p>
    
    <ul>
    <li><em>M'</em> = “On input <em>x</em>:  
    
    <ol>
    <li>If <em>x</em> = 01 then <em>accept</em>.  </li>
    <li>If <em>x</em> ≠ 10 then <em>reject</em>. </li>
    <li>If <em>x</em> = 10 simulate <em>M</em> on <em>w</em>.<br>
    If <em>M</em> accepts <em>w</em> then <em>accept</em>; if <em>M</em> halts and rejects then <em>reject</em>.”  </li>
    </ol></li>
    </ul>
    
    <p>If ‹<em>M</em>, <em>w</em>› ∈ <em>A</em><sub>TM</sub> then <em>M</em> accepts <em>w</em> and <em>L</em>(<em>M'</em>) = {01,10}, so ‹<em>M'</em>› ∈ <em>S</em>.<br>
    Conversely, if ‹<em>M</em>, <em>w</em>› ∉ <em>A</em><sub>TM</sub> then <em>L</em>(<em>M'</em>) = {01}, so ‹<em>M'</em>› ∉ <em>S</em>. Therefore,<br>
    ‹<em>M</em>, <em>w</em>› ∈ <em>A</em><sub>TM</sub> ⇔ ‹<em>M'</em>› ∈ <em>S</em>.</p></li>
    </ul>
  </blockquote>
  
  <p>But I do not understand the following:</p>
  
  <p>1- what is the relation between x and w?</p>
  
  <p>2- why we consider the 2 cases ‹<em>M</em>, <em>w</em>› ∈ <em>A</em><sub>TM</sub> and ‹<em>M</em>, <em>w</em>› ∉ <em>A</em><sub>TM</sub>?</p>
  
  <p>3- why if A is mapping reducible to S this makes S undecidable?</p>
  
  <p>could anyone clarify these points for me?</p>