Problem $6.[16$ points$]$

Consider the language REGULAR is a Turing machine and $L(M)$ is

regular Problem $6.[16$ points$]$

Consider the language REGULAR TM $=\{|$ M is a Turing machine and L$($M$)$ is

regular $\}$ and the complementary language NONREGULARTM $=\{|$ M is a Turing

machine and L$($M$)$ is not regular $\}.$ Both of these languages are undecidable; in fact, both

are not even recognizable.

$1.[6$ points$]$ Theorem $5\mathrm{.}3$ in Sipser$$s book shows that REGULARTM is undecidable. The

proof can be used to show that one of the above two languages is not recognizable.

Examine closely the proof in the book and determine which of the two languages,

REGULAR TM or NONREGULAR TM$,$ can be shown to be not recognizable using the

construction in this proof. Justify your answer.

$2.[10$ points$]$ Give another reduction that shows that the other one of these two languages

is also not recognizable.