# Undecidability

$REGULAR_{TM}$ = { <M> | M is a Turing Machine and L(M) is regular}.

Q. Prove that $REGULAR_{TM}$ is undecidable.

Solution. We will use the fact that $A_{TM}$ = { <M,w> | M is a Turing machine and M accepts w} is undecidable.

Assume, for the sake of contradiction, that $REGULAR_{TM}$ is decidable.

We will construct a Turing machine, $M'$ such that $L(M')$ is regular if and only if $M$ accepts $w$.

Let $M'$ operate as follows on input $x$:-

If $x$ is of the form $0^n1^n$, then “Accept”.

Else, simulate $M$ on $w$, and “Accept” if $M$ accepts $w$.

This ends the construction of $M'$.

We can see that :-

1. If $M$ accepts $w$, then $L(M')$ is the set of all strings, and hence, is regular.

2. If $M$ does not accept $w$, then $L(M')$ is not regular.

That is, $L(M')$ is regular iff $M$ accepts $w$. $\therefore$  If $REGULAR_{TM}$ is decidable, then $A_{TM}$ is decidable.