91Ó°ÊÓ

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 ‘$\underset{}{\overset{}{∑}}$’ and $a,b∉∑$.

Let $∑∪\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.