Photo of my problem that I don't understand
About question above in photo, I just can't understand its solution provided.
We know the complement of Atm = {<M,W> : M is TM and M does not accept W}
and Rtm as described in photo = {<M,W> : M is TM that rejects the input string W}
if we put M,epsilon into each of above,
the complement of Atm = M does not accept epsilon
Rtm = M rejects Epsilon
in either case, it makes sense to me, thus my perspective is
<M,epsilon> is in Rtm and also in complement of Atm.
But answer says <M,epsilon> is NOT in Rtm but in complement of Atm
Why is that?
Thank you very much!
Remember that there are three possible things a Turing machine can do (eventually) on a given input string:
Accept,
Reject,
Not halt (that is, run forever without giving an answer).
This means there are two ways a pair $\langle M, w\rangle$ can fail to be in $A_{TM}$:
$M(w)$ halts and says "REJECT," or
$M(w)$ never halts.
In the former case, we have $\langle M, w\rangle\in R_{TM}$. But in the latter case, $\langle M, w\rangle$ is in neither $R_{TM}$ or $A_{TM}$. What is true is that $\overline{A_{TM}}\supseteq R_{TM}$, but they are not equal.