¿Puedes resolver el problema de parada para una única máquina de Turing no universal?

Question

Por lo tanto, estoy familiarizado con el problema de detención y su demostración. Sin embargo, también entiendo que la prueba es para cualquier máquina universal $U$ es decir, el conjunto $\{(x,y)\in\{0,1\}^{<\omega}\times\{0,1\}^{<\omega}: U(x,y)\downarrow\}$ no es computable. En concreto, he visto la prueba por contradicción de que el complemento del conjunto no es semicomputable.

Sin embargo, dada una máquina específica, no universal $M$ con el alfabeto, digamos, $\{0,1\}$ ¿podría definir una máquina $M^\prime$ tal que, digamos, $M^\prime(w)=M(w)$ si y sólo si $M(w)$ se detiene, y $M^\prime(w)=0$ si $M$ no se detiene en la entrada $w$ ? ¿O esto, de alguna manera, resolvería el problema de detención, por lo que tal máquina $M^\prime$ no puede existir?

Perdón, de antemano, si esto parece una pregunta demasiado básica o si ya se ha preguntado antes. La verdad es que no se me ocurre cómo formular la pregunta simplemente para buscar si se ha contestado antes o no. Gracias.

Answer 1

Primero, una observación. Tal y como yo entiendo el concepto, la "máquina de Turing universal" describe la funcionalidad de una máquina de forma bastante rígida: la máquina tiene que recibir entradas en un formato determinado, y luego comportarse de una forma muy específica. No es un concepto robusto para el tipo de pregunta que estás planteando; podrías simplemente tomar una máquina universal y modificarla de alguna manera trivial para que sea esencialmente la misma, pero no es técnicamente una "máquina universal".

Dicho esto, diré un poco lo que creo que hay realmente detrás de tu pregunta. Estás preguntando cuándo es posible hacer un algoritmo para resolver el problema de detención para máquinas particulares. Puedes preguntar esto de forma más general: dado un conjunto particular de números naturales, ¿existe un algoritmo para decidir qué números están en el conjunto y cuáles no? En su caso, el conjunto es el conjunto de entradas para las que la máquina se detiene. Sólo algunos conjuntos surgen así; se llaman, por definición, los conjuntos "computablemente enumerables". Por otro lado, los conjuntos para los que es posible hacer un algoritmo que decida qué elementos están dentro y cuáles fuera son, por definición, "conjuntos computables". El argumento del problema de detención muestra que hay un conjunto computablemente enumerable que no es computable.

Lo que creo que has observado es que una máquina de Turing universal es bastante potente en el sentido de que puede hacer todo lo que cualquier otra máquina de Turing puede hacer. Es natural preguntarse si hay conjuntos "menos potentes" que sigan sin ser computables. Eso puede parecer un poco nebuloso, pero estamos de suerte: hay una buena manera de comparar la potencia de dos conjuntos, llamada Grado de Turing . La idea básica es que un conjunto A es "más fuerte" que otro conjunto B (tiene un grado más alto) si se puede construir una máquina para calcular B (es decir, decidir qué elementos están dentro y cuáles están fuera), si esa máquina puede consultar A como un "oráculo". Esto resulta ser un concepto rico y robusto.

De todos modos, la respuesta a mi versión de tu pregunta es sí. Hay una gran variedad de conjuntos que son computables (es decir, que son el conjunto de parada de alguna máquina), no computables, y que son estrictamente más débiles que el conjunto de parada de cualquier máquina universal (en términos de grado de Turing). No conozco ninguna construcción sencilla, pero espero haberte dado algunas ideas para intentar aprender.

Answer 2

Como se ha dicho, $M'$ es una función bien definida. A veces $M'$ es computable, como en casos sencillos como cuando $M$ es una máquina que siempre se detiene o que nunca se detiene. Es $M'$ ¿siempre computable? Resulta que no.

Consideremos el caso de un conjunto semidecidible $\Gamma$ . Sea $M$ sea una máquina de Turring que produzca $1$ para todos $\alpha\in\Gamma$ y salidas $0$ o bucles para $\alpha\notin\Gamma$ . En primer lugar, hay que tener en cuenta que $M$ no es una máquina universal de Turring. Prueba: Si $M$ es universal, entonces $M(\alpha)$ simula $\alpha(0)$ . Entonces tenemos $\alpha\in\Gamma$ si $\alpha(0)=1$ . Por lo tanto, todos los $\alpha\in\Gamma$ salida $1$ cuando se ejecuta en una cinta en blanco. $\Gamma$ era un conjunto semidecidible arbitrario, por lo que el resultado es válido también para todos los conjuntos semidecidibles. Sin embargo, el conjunto de todas las máquinas de Turing es decidible, y por tanto, semidecidible. Pero hay algunas máquinas de Turing que no producen $1$ cuando se ejecuta en una cinta en blanco. Por lo tanto, $M$ no es universal.

Desde $M$ no es universal, podemos definir $M'$ . Supongamos que $M'$ es computable (para demostrar una contradicción). Ahora $M'$ salidas $1$ para todos $\alpha\in\Gamma$ y salidas $0$ de lo contrario. Por lo tanto, $\Gamma$ es decidible. Esto significa que todos los conjuntos semidecidibles son decidibles. Una contradicción, y por lo tanto, $M'$ es incalculable.

Por último, su pregunta es si podemos definir un máquina (a diferencia de una función) $M'$ para todos los no universales $M$ . Como se ha mostrado anteriormente, no podemos definir una máquina de este tipo cuando $M$ es una máquina que enumera un conjunto semidecidible.

En general, para lo que $M$ podemos definir (la máquina) $M'$ ¿Y cuándo no podemos? Una máquina $M'$ existe si el conjunto $G$ de todos los valores para los que $M$ se detiene es decidible. Prueba: Supongamos que la máquina $M'$ existe. $M(\alpha)$ se detiene si $M'(\alpha)=1$ y $M(\alpha)$ no se detiene si $M'(\alpha)=0$ Así que $G$ es decidible. Supongamos que $G$ es decidible. Entonces hay una máquina que acepta $\alpha$ si $M(\alpha)$ se detiene, y rechaza $\alpha$ si $M(\alpha)$ no se detiene. Es decir, la máquina $M'$ .

Answer 3

La prueba estándar de que el problema de detención es irresoluble da una máquina $M$ de manera que no haya una máquina total $M'$ puede determinar correctamente el conjunto de $n$ para lo cual $M(n)$ se detiene.

Esta máquina $M$ no es universal en el sentido de la teoría de la computabilidad. Más bien $M(e)$ intenta calcular $\phi_e(e)$ ; si $U(e,e)$ se detiene y devuelve un número mayor que $0$ entonces $M(e)$ no se detiene, mientras que si $U(e,e)$ se detiene y regresa $0$ entonces $M(e)$ se detiene y regresa $1$ . Si $U(e,e)$ no se detiene entonces tampoco $M(e)$ . Se puede comprobar que esto da una buena definición de máquina $M$ y que ninguna máquina $M'$ puede resolver el problema de parada para $M$ en el sentido indicado en la pregunta.