Conjunto recursivamente enumerable? ¿Alguna pista?

Question

No pretendo sacarte respuestas, pero estoy atascado. Cualquier consejo sobre la dirección correcta sería apreciado. Tengo el siguiente conjunto $X$ ={$n$ donde $n$ es un número de una máquina de Turing $M$ que no se detiene cuando se le da $n$ como entrada}

Mi instinto me dice que no lo es. Y eso es porque la pregunta trata sobre el conjunto de todos los x's que no son parcialmente decidibles. Los lenguajes recursivamente enumerables SON parcialmente decidibles, por lo que no puede ser REL.

¿Es esto correcto? ¿Y es este razonamiento suficiente?

Gracias.

Answer 1

Si $X$ es recursivamente enumerable, entonces existe una máquina de Turing $T$ tal que $T$ se detiene en la entrada $n$ si y solo si $T_n$ no se detiene en la entrada $n$. Supongamos que $T=T_m$. Entonces $T_m$ se detiene en la entrada $m$ si y solo si $T_m$ no se detiene en la entrada $m$. Por lo tanto, $X$ no puede ser recursivamente enumerable.

Answer 2

El conjunto $Y$ de todos los números naturales $n$ tales que $n$ es el número de una máquina de Turing que se detiene con entrada $n$ es r.e..

El conjunto $K$ de todos los números naturales $n$ tales que $n$ no es el número de una máquina de Turing es recursivo.

Se sigue que el conjunto $Y\cup K$ de números naturales $n$ tales que $n$ es el número de una máquina de Turing que se detiene con entrada $n` o $n$ no es el número de una máquina de Turing es r.e..

Pero $Y\cup K$ es el complemento de $X$. Entonces, si $X$ es r.e., entonces ya que su complemento es r.e., $X$ es recursivo. Pero ese no es el caso, ya que si $X$ es recursivo, entonces $X\cup K$ es recursivo, y por lo tanto $Y$ es recursivo. Es bien sabido que $Y$ no es recursivo.

Answer 3

Un resultado útil conocido es que un conjunto $A \subset \omega$ es computable (recursivo, decidible) si y solo si $A$ y $\omega - A$ son enumerable computablemente.

Sea $X$ tu conjunto anterior. Entonces $\omega - X$ es el conjunto de $n$ tal que la $n^\text{th}$ máquina de Turing se detiene en $n$. Este conjunto es equivalente al conjunto del Problema de Detención. Es bien sabido que el conjunto del Problema de Detención es enumerable computablemente pero no computable. Por lo tanto, si $X$ es computablemente enumerable, entonces tienes que tanto $X$ como $\omega - X$ son ambos computablemente enumerables. Según el resultado del primer párrafo, tendrías que $\omega - X$, el conjunto del Problema de Detención, es computable. ¡Contradicción!