Both $\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ are not turing-recognizable?

Question

if we define $A_{TM}$ and $\overline{ A_{TM}}$ as follows: $$ \begin{align} A_{TM}&= \{ \langle M,w \rangle |M \text{ is a turing machine and $M$ accepts $w$} \}\\ \overline {A_{TM}}&= \{ \langle M,w \rangle |M \text{ is a turing machine and $M$ do not accepts $w$} \}\end{align} $$ $\overline{A_{TM}}$ and $\Sigma^*\backslash A_{TM}$ both are not turing-recognizeable. right?(a bit confused by the way $\overline{ A_{TM}}$ is defined. noramly $\overline A = \Sigma^*\backslash A$).

My reasons :

1.$\overline{A_{TM}}$ is not reconizable because: if it was then we could run two recognizer for $\overline{A_{TM}}$ and $A_{TM}$ in parallel and decides $A_{TM}$.
2. $\Sigma^*\backslash A_{TM}$ is not recongnizeable by fallowing lemma :
lemma: $L$ and $\overline L$ recognizeable iff $L$ is decideable.

in fact both reasones are quite the same but in second one we are considring inputs ($\langle M,w \rangle$) which are not properly formated.

Answer 1

Usually the second language is denoted by $A_{\overline{TM}}$, exactly to avoid the confusion with the complement.

This is actually a common question, and it has to do with the encoding of TMs and words. When we write $\langle M,w\rangle$, we mean that we give some agreed-upon encoding of a Turing machine and a word over its alphabet. We usually don't go to much into it, but it is agreed that the encoding is simple enough so that another Turing machine can easily parse it (where easily usually means either in logarithmic space, or polynomial time, or something of the sort).

Now, intuitively, in an agreed encoding, some words represent $M,w$ such that $M$ accepts $w$, some represent $M,w$ such that $M$ does not accept $w$, and some are meaningless gibberish. When the encoding is easy to parse, we can kind of ignore this gibberish. However, it does pose a small problem when we start complementing languages.

Indeed, $\Sigma^*\setminus A_{TM}$ should, formally, also contain all strings that are not legal encodings. However, since determining whether an encoding is legal is easy, then it doesn't effect the recognizability or decidability of the language. You can always start by checking the legality of the encoding, and accept if the encoding is illegal.

There is another way around it, which I like: you can define the encoding such that every string is a legal encoding. You do that by using some encoding of your liking, and adding to it the statement that any string that is not a legal encoding is now interpreted as some fixed TM $T$ and the empty word. Then, you actually get that $A_{\overline{TM}}=\overline{A_{TM}}$, and the problem goes away.

Answer 2

$A_{TM}\in RE$ (aka, turing recognizable), but $\overline{A_{TM}}\notin RE$.

The proof is quite simple, assuming you know that $A_{TM}$ is not decidable:

Look at the turing machine $M$ that given $\langle M', w\rangle$ simulates $M'$ on $w$, and accepts if and only if $M'$ accepted. for any $\langle M', w\rangle\in A_{TM}$, $M'$ accepts $w$ and thus $M$ accepts $\langle M', w\rangle$. Therefore, $M$ recognizes $A_{TM}$ (notice that anything which is not in $A_{TM}$ will never get accepted in $M$), and thus $A_{TM}\in RE$.

Since $L\in R \iff L\in RE\cup co-RE$, and we know that $A_{TM}\notin R$ but $A_{TM}\in RE$, then $A_{TM}\notin co-RE$ and thus $\overline{A_{TM}}\notin RE$.