I'm given the set $T = \{\langle M, w\rangle : M $ is a Turing Machine that accepts $w$ reversed whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the bracket notation to denote the encoding of the TM and input string)
Given that I know the set $A = \{\langle M,w\rangle : M \text{ accepts } w \}$ is undecidable but recognizable, I'm trying to show that $A$ reduces to $T$.
I start by assuming that $T$ is decided by a Turing Machine $R$ and then attempt to construct a new Turing Machine, $S$, that will decide $A$ by using $R$ as a subroutine.
To construct this new machine $S$, I will run $R$ on input $\langle M,w\rangle$. If $R$ accepts, then $\langle M,w\rangle$ is in $A$. However, $R$ rejecting doesn't necessarily mean that $\langle M,w\rangle$ isn't in $A$, since $M$ might reject $w$ reversed but accept $w$. So now I'm confused on how to actually construct the reduction. Any help would be great
Best Answer
Suppose T is decided by R. Construct the following machine H.
$H(<A>, x):$
1) Create the following machine $< M >:$
$\quad\quad M(w):$
$\quad\quad\quad A(x)$
$\quad\quad\quad accept$
2) if $R(<M, w>)$ accepts then
$\quad\quad accept$ (since A(x) halts)
$\;\;\;$else
$\quad\quad reject$ (since A(x) loops)
Note that $<M>$ is constructed to accept all w if and only if A(x) halts.
In that case, $<M>$ certainly accepts w and reverse(w).
So $<M, w>$ is in T if and only if A(x) halts.
If R is a decider, then H would be a decider for the Halting problem.
So, T must be undecidable.
Now, construct the recognizer for T:
$R(<M, w>):$
$\quad$ if M(w) accepts and M(reverse(w)) accepts then
$\quad\quad$ accept
$\quad$ else
$\quad\quad$ reject
Note that if either M(w) or M(reverse(w)) rejects or loops then R will reject or loop.
So, R is a recognizer for T.