Notes: $(50$ points$)$ Please prove that language Rrm is undecidable by showing that ATM $|$ TM T rejects all input strings $\}2\mathrm{.}3$ EQTM is undecidable Prove that language EQTM is undecidable by showing that ATM $<=$m EQTM EQTM $=\{($T$1,$ T$2)|$ T$1$ and T$2$ are TMs and L$($T$1)=$ L$($T$2)\}$ PROOF: For the purpose of contradiction, we assume that EQTM is decidable and there is a decider Y for EQTM. We design decider X for ATM that works as follows on input string z$.$ line $1$: function f reads input x $=($M$,$m$)$ and generates output y $=($T$1,$ T$2),$ where T$1$ is a TM working as follows on input string $1.$ Simulates M on m If M accepts m$,$ then T$1$ accepts t$1.$ If M rejects m$,$ then T$1$ does not accept $($rejects or loops$)$ t$1.$ If M loops on m$,$ T$1$ also loops. T$2$ is a TM working as follows on input string t$2.$ T$2$ accepts t$2.$ We can see that x $=($M$,$m$)$ ATM $$ M accepts m $$ L$($T$1)=$ L$($T$2)$ f$(($M$,$m$))=($T$1,$ T$2)$ EQTM line $2$: X runs Y on string y line $3$: if Y accepts string y line $4$: then X accepts z line $5$: else X rejects z However, we have already proved that ATM is undecidable. Contradiction! Therefore, the assumption is wrong. That is$,$ EQTM is undecidable. $$