Esta es esencialmente la respuesta de Rafael ampliada, y teniendo en cuenta lo que yo estaba (probablemente sin éxito) tratando de comunicar en los comentarios. Según recuerdo, la razón por la que la Máquina Universal es importante es que es a través de la UTM que podemos explicar realmente cómo se produce la "construcción" de las máquinas modificadas; pero podría haber metido la pata y si es así me disculpo.
Añadido: Supongo que la cuestión es que técnicamente tienes razón en que la prueba que presentas, que pasa por alto algunos detalles importantes, es incorrecta. La máquina $Q$ no se puede preguntar sobre el comportamiento de $Q$ con $Q$ como entrada, dada la forma en que describe $Q$ . Técnicamente la razón es que si intentas formalizarlo según las líneas que doy a continuación, acabas siendo incapaz de formalizar la entrada que debes poner en $Q$ . El argumento es "moralmente" correcto en el sentido de que unos pocos trucos técnicos (aunque estándar) resolverán esa cuestión utilizando una ligera modificación de $Q$ en lugar de $Q$ directamente. Por otra parte, está claro que la prueba no trata de ser técnicamente exacta, sino sólo "moralmente" exacta, por lo que se pueden perdonar ligeros desenfoques. Es similar a lo que ocurre en la descripción habitual de la segunda prueba de Cantor sobre la incontabilidad de los reales, donde se pasa por alto la cuestión de las distintas representaciones de los reales y puede llevar a un argumento técnicamente incorrecto.
Las máquinas de Turing tienen cada una un código $C$ y tomar números como entrada. (Podemos utilizar, por ejemplo, la numeración de Goedel para traducir a números determinadas frases o problemas). Escribamos $C(m)$ para significar la entrega de la máquina con el bacalao $C$ la entrada $m$ Podemos tomar un par $(C,m)$ donde ambos $C$ y $m$ son números, y obtener un número $N$ que se "corresponde" (de forma precisa y bien definida) con un par $(C,m)$ . Escribamos esto como $N\sim (C,m)$ .
Suponga que tiene una máquina $H$ que resuelve el problema de detención; podemos modificarlo para que acepte cualquier entrada y, cuando se le dé una entrada $N$ hará lo siguiente: \begin{equation*} H(N) = \left\{\begin{array}{ll} 1 & \mbox{if $N\sim (C,m)$, and $C$ halts when $m$ is its input;}\\ 0 & \mbox{if $N\sim (C,m)$ and $C$ does not halt when $m$ is its input;}\\ 0 & \mbox{if $N\not\sim(C,m)$ for any $C$ and $m$.} \end{array} \derecha. \Fin.
Si $H$ existe, entonces podemos "construir" (es decir, también existe) una máquina de Turing $Q$ tal que: \begin{equation*} Q(N) = \left\{\begin{array}{ll} 1 & \mbox{if $H(M)=0$, where $M\sim(N,N)$;}\\ \mbox{does not halt} & \mbox{if $H(M)=1$, where $M\sim(N,N)$.} \end{array} \derecha. \Fin ecuación Nótese que $M$ está bien definida, ya que no es más que el código del par $(N,N)$ .
La clave es que $Q$ no toma como entrada un par de la forma $(C,k)$ ; toma un solo número $k$ y luego se da cuenta de lo que $H(k,k)$ habría sido. Es una máquina mucho más restrictiva que una que "hace lo contrario" de lo que $H$ lo hace.
Ahora, $Q$ siendo una máquina de Turing tiene un código específico $C$ . Así que la pregunta es, ¿qué es $Q(C)$ ? Por definición, $Q(C) = 1$ si y sólo si $H(M)=0$ , donde $M\sim(C,C)$ Pero $H(M)=0$ significa que $M$ no es el código de un par válido, o bien que $C$ no se detiene cuando se le da el número $C$ como entrada. Sin embargo, $M$ *es* el código de un par, porque así lo hemos definido. Así que eso significa que $Q(C)=1$ si y sólo si la máquina con código $C$ no se detiene cuando se le da $C$ como entrada. Pero la máquina con código $C$ *es* $Q$ Así que $Q(C)=1$ si y sólo si el resultado de hacer $Q(C)$ es no terminante. Por lo tanto, no podemos tener $Q(C)=1$ .
¿Cuándo es $Q(C)\neq 1$ ? $Q(C)\neq 1$ si y sólo si $Q(C)$ no se detiene; y $Q(C)$ no se detiene si y sólo si $H(M)=1$ , donde $M\sim(C,C)$ . Pero $H(M)=1$ en este caso si y sólo si la máquina con código $C$ se detiene cuando se le da la entrada $C$ . Pero la máquina con código $C$ *es* $Q$ Así que $Q(C)$ no se detiene si y sólo si $Q(C)$ se detiene, una contradicción.
Creo que la clave aquí es doble: en primer lugar, que las entradas de las máquinas de Turing son sólo números, en lugar de pares o conjuntos reales. Estamos identificando lo que en el metalenguaje corresponde a un par con un solo número para hacer la entrada, por lo que no podemos encontrarnos con problemas de fundamentación (las entradas no son pares de pares de pares... etc, son sólo números ). La cuestión podría surgen si no pudiéramos definir el número porque requiere un proceso recursivo que "se prolonga indefinidamente" y conduce a un "número infinito". Y segundo : no construyes $Q$ para que se detenga si $H$ dice 'no se detiene' con esa misma entrada, o se detendrá si $H$ dice "es hace halt" con la misma entrada. En su lugar, $Q$ transforma su entrada de forma precisa y bien definida (en este caso, tomando $N$ al código de $(N,N)$ ) y sólo entonces preguntando si $H$ se detendrá con que nueva entrada o no. Es decir, $Q$ no tiene por qué ser tan general como lo haces ver en tu post, por lo que podemos utilizar $Q$ para preguntar sobre sí mismo.
