Mapeamento de reduções para complementação de A

Tenho uma pergunta geral sobre o mapeamento de reduções. Eu já vi vários exemplos de redução de funções para$A_{TM}$

onde $A_{TM} = \{\langle M, w \rangle : \text{ For } M \text{ is a turing machine which accepts string } w\}$

o que é ótimo para provar indecidibilidade. Mas digamos que eu queira provar a irreconhecibilidade. Ou seja, eu quero usar o corolário que, dado $A \le_{m} B$ , se $A$ é irreconhecível, então $B$ é irreconhecível.

Portanto, para qualquer linguagem arbitrária e irreconhecível que possa ser reduzida para (qualquer idioma de exemplo seria suficiente por exemplo), como posso reduzir ?$C$$\overline{A_{TM}}$$\overline{A_{TM}} \le_{m} C$

Para simplificar, basta considerar apenas a MT em .$\overline{A_{TM}}$

EDITAR

Para esclarecimento,$\overline{A_{TM}} = \{ \langle M, w \rangle : M \text{ is a turing machine which does not accept string } w \}$

Vamos usar , ou seja, todas as máquinas que não aceitam palavra (ou seja, cujo idioma está vazio).$L_{\emptyset}=\{ \langle M \rangle \mid L(M) = \emptyset \}$

Agora, mostramos a redução . A redução é feita usando uma entrada de e convertendo-a em uma entrada para modo que$\overline{A_{TM}} \le L_\emptyset$$(\langle M \rangle,w)$$\overline{A_{TM}}$${\langle \tilde M \rangle}$$L_\emptyset$

Dado , podemos construir da seguinte maneira. na entrada y faz o seguinte:$(\langle M \rangle,w)$$\tilde M$$\tilde M$

1. exclui a fita
2. escreve na fita$w$
3. executa em e executa o mesmo (se aceitar, aceita).$M$$w$$M$$\tilde M$

Convença-se de que é possível construir a codificação de partir da codificação de e de . Agora vamos verificar se essa redução é válida:$\tilde M$$M$$w$

• Se , rejeita ou não para. Nesse caso, também não aceita , para qualquer entrada . Isso significa assim .$(\langle M \rangle,w) \in \overline{A_{TM}}$$M$$\tilde M$$y$$y$$L(\tilde M) = \emptyset$$\langle \tilde M \rangle \in L_{\emptyset}$
• Se então aceitará , assim aceitará (para cada ). Segue que que implica que .$(\langle M \rangle,w) \notin \overline{A_{TM}}$$M$$w$$\tilde M$$y$$y$$L(\tilde M)=\Sigma^*$$\langle \tilde M \rangle \notin L_{\emptyset}$

A condição "iff" é válida e mapeamos com êxito uma entrada de em uma entrada de . Nesse caso, dizemos que reduzimos para . Ou seja, se pudermos resolver , também podemos resolver primeiro convertendo a entrada e depois executando o algoritmo que resolve na entrada convertida.$\overline{A_{TM}}$$L_\emptyset$$\overline{A_{TM}}$$L_\emptyset$$L_\emptyset$$\overline{A_{TM}}$$L_\emptyset$

Você não pode mostrar, para um idioma irreconhecível arbitrário $C$, aquele $\overline{A_{TM}} \leq_m C$. E se$\overline{A_{TM}} \leq_m C$ então, em particular, o grau de Turing $C$ é maior ou igual ao grau de Turing de $\overline{A_{TM}}$, porque a redutibilidade de muitos um implica redutibilidade de Turing. O grau de Turing de$\overline{A_{TM}}$ é $0'$, o mesmo que o grau de Turing $A_{TM}$. Existem muitas línguas irreconhecíveis cujo grau de Turing é incomparável com$0'$ (nem maior nem menor que $0'$)

O exemplo que Ran G. deu obras porque $L_\emptyset$ em particular é $m$-equivalente a $\overline{A_{TM}}$. Há um fenômeno geral de que a maioria dos problemas "naturais" tendem a ser comparáveis ​​entre si em$m$-grau. Mas se você olhar para problemas arbitrários, isso não é mais verdade.