Estoy tratando de encontrar de dónde viene el lenguaje $\{\langle M,q,x\rangle$| $M$ es un Turingmachine y $q$ es un estado de la M y la ejecución de $M$ $w$ pasa $q\}$ pertenecen? si es $R,RE$ o ninguna de las anteriores.
Al principio, pensé que se decidable, ya que si se detiene puedo ir a través de los estados que visitó, y si es no parar me puede decir a partir de la detección de una configuración específica del doble que en el bucle, pero es correcto Lineal acotado automatizar y no para un infinito de bandas de la máquina (¿Estoy en lo cierto?).
Entonces yo quería demostrar que no es en $R$.Quiero hacer una reducción de la aceptación del problema: puedo hacer lo siguiente? dado $(\langle M\rangle,x)$ me da el mismo $(\langle M\rangle,x)$ $q$ que sería la aceptación de un estado de $M$. si no tiene ninguna, sería un nuevo estado aislado, así que tengo que si M acepta x visitas $q$, de lo contrario no lo es.
La recursividad: $f(\langle M \rangle, x)= (\langle M' \rangle, x',q')$
dado $(\langle M\rangle,x)$ I la construcción de la nueva $M'$ como el siguiente:
Si $M$ acepta $x$, $M'$ sería una copia de $M$, $x'=x$ y $q'=q_a$ donde $q_a$ es la aceptación de un estado de original $M$, si es que no puedo copiar $M=M'$ , $x=x'$ y $q'$ sería un nuevo estado aislado donde no alcanza. básicamente ignore a la entrada de la nueva $M'$ y se utiliza sólo con $x$.
Estoy en lo cierto?
