Question: Let $\mathit{T}\mathbf{=}\mathbf{\left\{}<M>\mathbf{\right|}\mathit{M}\mathbf{}\mathit{i}\mathit{s}\mathbf{}\mathit{a}\mathbf{}\mathit{T}\mathit{M}\mathbf{}\mathit{t}\mathit{h}\mathit{a}\mathit{t}\mathbf{}\mathit{a}\mathit{c}\mathit{c}\mathit{e}\mathit{p}\mathit{t}\mathit{s}\mathbf{}{\mathit{w}}^{\mathbf{R}}\mathit{w}\mathit{h}\mathit{e}\mathit{n}\mathit{e}\mathit{v}\mathit{e}\mathit{r}\mathbf{}\mathit{i}\mathit{t}\mathbf{}\mathit{a}\mathit{c}\mathit{c}\mathit{e}\mathit{p}\mathit{t}\mathit{s}\mathbf{}\mathit{w}\mathbf{\}}$. Show that T is undecidable.

A problem is undecidable if no Turing Machine exist which will halt in finite amount of time.

It’s known that $L=\left\{\left(w,M\right):w \text{is} \text{accepted} \text{by} M\right\}$ is undecidable. Here, 'w' are all the strings in L accepted by Turing Machine.

Let’s assume that T is decidable, there must be a Turing Machine TM (say A) that can decide T.

For any input $\left(w,M\right)$, construct M' as:

If we have $w=w^R$, which run M on w and set of alphabets of M be ‘$\sum _{}^{}$’ and $a,b\notin \sum$.

Let $\sum \cup \left\{a,b\right\}$ be the set of alphabets of M'. M' will reject all the possible string except ‘ab’ for input ‘ab’ that runs M on w,

• If M accepts w then M' is rejected.
• If M rejects then M'is accepted.

Now we going to show that Aaccepts M' if and only if M accepts w.

• If A accepts M' thenM ' rejects 'ab' and this implies M accepts w since M' rejects all the other strings including ba.
• If M accept w, then $M_0$ reject ab, because M' rejects all the other strings, thus M' is accepted by A.

Since we have Turing Machine for L, then on input $\left(w,M\right)$. So we can construct M' and run A on that Turing Machine, is accepted if and only if A accepts it.

But this is against our assumption made earlier at starting, that L is undecidable.

Hence we conclude that T is undecidable.