2
$\begingroup$

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.

$\endgroup$

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ i think you have a blunder in line 9 and you meant $M$ does not accept $w$. i edited my question and added my reasoning to it. do you agree with what i said? $\endgroup$
    – mike
    Commented Apr 21, 2021 at 15:47
  • $\begingroup$ @mike - right, fixed. What you wrote is fairly correct. The point is that these two problems are not really different. They only differ by a decidable problem (namely, is the encoding legal), so we can get rid of this obstacle, and from that point on the problems are the same. $\endgroup$
    – Shaull
    Commented Apr 21, 2021 at 18:39
  • $\begingroup$ good point. if im not mistaken you are saying for $C = A \cup B$ that $A \cap B = \emptyset $ we can say : ($A \notin RE \; \land \; \text{knowing $B$ is decideable}) \implies C\notin RE$ and also ($A \in RE \; \land \; \text{knowing $B$ is decideable}) \implies C\in RE$ so we just can ignore $B$ $\endgroup$
    – mike
    Commented Apr 21, 2021 at 19:38
  • $\begingroup$ @mike - Yes, that's exactly right. This is closely related to the concept of Promise Probelms: en.wikipedia.org/wiki/Promise_problem $\endgroup$
    – Shaull
    Commented Apr 21, 2021 at 19:48
0
$\begingroup$

$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$.

$\endgroup$
1
  • $\begingroup$ The OP asked about $\overline{A_{TM}}$ vs $\Sigma^*\setminus{A_{TM}}$ (which are not the same in the OP's terms), so I think this does not really answer the question. $\endgroup$
    – Shaull
    Commented Apr 21, 2021 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.