Mapeo de las reducciones a complemento de A $ _ {TM} $

Question

Tengo una pregunta general acerca de las reducciones de mapeo. He visto varios ejemplos de funciones de reducción de $ A_ {TM} $

donde $ A_ {TM} = \ {\ langle M, w \ rangle: \ text {A} M \ text {es una máquina de Turing que acepta cadena} w \} $

que es ideal para probar la indecidibilidad. Pero digo que quiero probar irreconocible en su lugar. Es decir, quiero usar el corolario de que da $ A \ le_ {m} B $, si $ A $ es irreconocible luego $ B $ es irreconocible.

Así que para cualquier idioma irreconocible arbitraria $ C $ que puede ser reducida a $ \ overline {A_ {TM}} $ (cualquier idioma ejemplo sería suficiente para poner un ejemplo), ¿cómo puedo reducir $ \ overline {A_ {TM }} \ le_ {m} $ C?

Para simplificar, basta con considerar meramente TM en $ \ overline {A_ {TM}} $.

Editar

Para mayor claridad, $ \ overline {A_ {TM}} = \ {\ langle M, w \ rangle: M \ text {es una máquina de Turing que no acepta la cadena} w \} $

Answer 1

Let's take $L_{\emptyset}=\{ \langle M \rangle \mid L(M) = \emptyset \}$, that is, all the machines that accept no word (i.e., whose language is empty).

Now we show the reduction $\overline{A_{TM}} \le L_\emptyset$. The reduction is done by taking an input $(\langle M \rangle,w)$ of $\overline{A_{TM}}$ and converting it into an input ${\langle \tilde M \rangle}$ for $L_\emptyset$ such that

$$(\langle M \rangle,w) \in \overline{A_{TM}} \quad\text{ iff }\quad \langle \tilde M \rangle \in L_{\emptyset}$$

Given $(\langle M \rangle,w)$ we can construct $\tilde M$ in th following way. $\tilde M$ on input y does the following:

1. deletes the tape
2. writes $w$ on the tape
3. runs $M$ on $w$, and performs the same (if $M$ accepts, $\tilde M$ accepts as well).

Convince yourself it is possible to construct the coding of $\tilde M$ from the coding of $M$ and from $w$. Now let's verify that this reduction is valid:

• If $(\langle M \rangle,w) \in \overline{A_{TM}}$ then $M$ either rejects or doesn't halt. If so, then also $\tilde M$ doesn't accept $y$, for any input $y$. This means $L(\tilde M) = \emptyset$ thus $\langle \tilde M \rangle \in L_{\emptyset}$.
• If $(\langle M \rangle,w) \notin \overline{A_{TM}}$ then $M$ accepts $w$, thus $\tilde M$ accepts $y$ (for every $y$). It follows that $L(\tilde M)=\Sigma^*$ which implies that $\langle \tilde M \rangle \notin L_{\emptyset}$.

The "iff" condition holds and we successfully mapped an input of $\overline{A_{TM}}$ into an input of $L_\emptyset$. In this case we say we reduced $\overline{A_{TM}}$ to $L_\emptyset$. That is, if we can solve $L_\emptyset$, we can also solve $\overline{A_{TM}}$ by first converting the input and then running the algorithm that solves $L_\emptyset$ on the converted input.

Answer 2

You cannot show, for an arbitrary unrecognizable language $C$, that $\overline{A_{TM}} \leq_m C$. If $\overline{A_{TM}} \leq_m C$ then in particular the Turing degree of $C$ is greater than or equal to the Turing degree of $\overline{A_{TM}}$, because many-one reducibility implies Turing reducibility. The Turing degree of $\overline{A_{TM}}$ is $0'$, the same as the Turing degree of $A_{TM}$. There are plenty of unrecognizable languages whose Turing degree is incomparable with $0'$ (neither greater nor less than $0'$).

The example that Ran G. gave works because $L_\emptyset$ in particular is $m$-equivalent to $\overline{A_{TM}}$. There is a general phenomenon that most "natural" problems tend to be comparable with each other in $m$-degree. But if you look at arbitrary problems this is no longer true.