Prueba $L=\left\{ \left\langle M\right\rangle \mid L\left(M\right)=A_{TM}\right\} \in\overline{RE\cup coRE}$

Question

Me gustaría probar la siguiente afirmación: $$L=\left\{ \left\langle M\right\rangle \mid L\left(M\right)=A_{TM}\right\} \in\overline{RE\cup coRE}$$

Dónde $$A_{TM}=\left\{ \left\langle M,w\right\rangle \mid M\text{ is a TM that accepts }w\right\} $$

He llegado a la conclusión de que la forma de hacerlo es mostrar una reducción múltiple $$ALL_{TM}\leq_{m}L$$ donde $$ALL_{TM}=\left\{ \left\langle M\right\rangle \mid M\text{ is a TM with }L\left(M\right)=\Sigma^{*}\right\} $$ Como sé que $ALL_{TM}\in\overline{RE\cup coRE}$ . Pero el nivel de recursividad en este punto me está haciendo girar la cabeza. Así que mis preguntas son:

1) ¿Estoy en el camino correcto? ¿Es factible esta reducción?

2) Si es así, ¿quizás una pista sobre cómo construirlo?

Editar (Respuesta):

Terminé utilizando un enfoque diferente. Mostré las dos reducciones de muchos $A_{TM}\leq_{m}L$ y $\overline{A_{TM}}\leq_{m}L$ que dan el mismo resultado.

Answer 1

Hay un proceso que a menudo facilita los problemas de este tipo, y también da un cálculo más preciso del nivel de incomputabilidad de un conjunto.

El primer paso en cualquier problema de este tipo es utilizar el Procedimiento Tarski-Kuratowski para estimar lo incalculable que es el conjunto. Para ello, escribimos una definición del conjunto utilizando cuantificadores de los números naturales y predicados computables.

Dejemos que $H(M,w,s)$ sea el predicado computable que dice la máquina $M$ acepta $w$ después de exactamente $s$ pasos. A continuación, $$ A_{TM} = \{ \langle M,w\rangle | (\exists s)H(M,w,s) \} $$ y así tenemos $$ N \in L \leftrightarrow (\forall M,w)(\forall s)\left [ [H(N, \langle M,w\rangle, s) \to (\exists s') H(M,w,s')] \\ \land [ H(M,w,s) \to (\exists s'') H(N, \langle M,w\rangle, s'')]\right ] $$ A continuación, lo ponemos en forma de prenex: $$ N \in L \leftrightarrow (\forall M,w)(\forall s)(\exists s')(\exists s'')[ [H(N, \langle M,w\rangle, s) \to H(M,w,s')]\\ \land [ H(M,w,s) \to H(N, \langle M,w\rangle, s'')]] $$ La fórmula resultante comienza con un bloque de $\forall$ seguido de un bloque de $\exists$ , por lo que está en el nivel $\Pi^0_2$ de la jerarquía aritmética . Este es un límite superior para el nivel de incapacidad de cálculo del conjunto, pero un hecho sorprendente es que el nivel obtenido por este proceso suele ser el nivel exacto de incapacidad de cálculo del lenguaje.

Así que queremos demostrar que nuestra lengua es $\Pi^0_2$ completa. Dejemos que $R(a,b,c)$ sea cualquier relación computable, y mira $S = \{ c : (\forall a)(\exists b)R(a,b,c)\}$ . Queremos demostrar que $S$ es muchos -uno reducible a nuestra lengua original- porque $R$ es arbitraria, esto demuestra que nuestro lenguaje es $\Pi^0_2$ completa.

Para ello, comience con una máquina $M$ que está en $N$ . Ahora, dado un número $c$ , fabricamos una nueva máquina $M'(c)$ de la siguiente manera. Para cada entrada $v$ de longitud $n$ , $M'(c)$ primero busca cada $a < n$ para un $b$ tal que $R(a,b,c)$ . Si encuentra tal $b$ para cada $a < n$ entonces $M'(c)$ corre $M$ en $v$ y devuelve lo que $M$ devuelve. Por lo tanto, si $(\forall a)(\exists b)R(a,b,c)$ entonces $M'(c)$ tiene el mismo comportamiento que $M$ . Sin embargo, si hay un $c$ para que $\lnot (\forall a)(\exists b)R(n,b,c)$ entonces $M'(c)$ no tendrá el mismo lenguaje que $M$ porque $M'(c)$ entrará en un bucle infinito en lugar de aceptar algunas entradas que $M$ aceptaría.

En general, tenemos que $c \in S$ si y sólo si $M'(c) \in N$ Así que $N$ es un $\Pi^0_2$ conjunto completo. En particular, por Teorema de Post Esto significa que $N$ no es r.e. (los conjuntos r.e. son los $\Sigma^0_1$ conjuntos) o co-r.e. (los conjuntos co-r.e. son los $\Pi^0_1$ conjuntos).

Answer 2

EDIT: Este enfoque no funciona para este problema en particular, pero dejo esta respuesta aquí ya que tiene algún valor en diferentes escenarios.

No sé si la reducción que sugieres es fácil de construir. Aquí hay un enfoque alternativo:

1. Demostrar que $L$ es indecidible.
2. Demostrar que $L$ se reduce a $\overline L$ y viceversa. Por lo tanto, $L$ es $\mathsf{RE}$ si $L$ es $\mathsf{coRE}$ .
3. Recordemos que una lengua está en $\mathsf{RE} \cap \mathsf{coRE}$ precisamente si es decidible.