Un Obsesivo máquina de Turing problema

Question

Puede usted por favor me ayuden a entender si es o no el siguiente, el problema es recursivo, es recursivamente enumerable, o co-recursivamente enumerable?

Una máquina de Turing $M$ se dice que el trastorno obsesivo si en cada entrada $w$ $M$ pasa a través de todos sus estados (excepto, eventualmente, el rechazar y aceptar a los estados).

Entrada: (codificación) de una máquina de Turing determinista $M$.

Pregunta: Es $M$ obsesivo?

Gracias.

Answer 1

La primera de convencerse de que es un obsesivo máquina universal que existe.

A continuación, el siguiente diagonalización argumento muestra que el conjunto de no-obsesivo máquinas no pueden ser recursivamente enumerable. Supongamos que la máquina de $N$ detiene exactamente cuando la entrada es un no-obsesivo máquina de Turing; luego construir la siguiente máquina de $D$ utilizando el estándar de quine/diagonalización técnicas:

machine D is:
   ignore any input;
   construct Y as a description of D itself;
   simulate N on input Y;
   go to a distinguished penultimate state;
   stop.

La construcción de la $Y$ es siempre la misma, por lo que pueden ser fácilmente organizados a suceder de manera obsesiva, simplemente dejando fuera a los estados que no son necesarios. Además, la simulación de $N$ se puede hacer utilizando un trastorno obsesivo universal sub-máquina. Así, la obsesión de $D$ depende únicamente de si el distinguido penúltimo estado es alcanzado. Pero si $N$ es correcta, esto va a pasar exactamente al $D$ es no obsesivo, por lo que es el trastorno obsesivo si y sólo si es no-trastorno obsesivo-una contradicción. Por lo $N$ no puede existir.

El conjunto de trastorno obsesivo máquinas no pueden ser recursivamente enumerable. El uso de la obsesiva universal de la máquina, es fácil de traducir cualquier máquina $P$ en uno que es el trastorno obsesivo si y sólo si $P$ se detiene en todas las entradas. Por lo tanto la enumeración de la obsesiva máquinas llevaría a una enumeración de todas las máquinas de Turing que calcular el total de funciones recursivas, que es bien conocido por ser imposible.