Problema de parado

Ya había hablado antes de los problemas de decisión. Ahora voy a hablar de un "caso particular" de estos: el de decidir si una palabra pertenece a un lenguaje específico. Puse entrecomillado lo de caso particular porque en realidad cualquier problema de decisión se puede escribir de esta forma, pero eso es cosa aparte.
Veamos, una palabra es eso, una secuencia de símbolos de un alfabeto dado; un lenguaje es un conjunto de palabras. Por ejemplo la palabra palabra pertenece al lenguaje palabras en español, pero aerdssmensfeas no pertenece a ese lenguaje. Sin embargo, aerdssmensfeas pertenece al lenguaje palabras que comienzan en 'a', pero palabra no.
Entonces, si me yo tengo un lenguaje, y me dan una palabra, ¿cómo decido si pertenece a ese lenguaje? Una forma es usar una máquina de Turing. No se dejen asustar; una máquina de Turing es simplemente un mecanismo que tiene 4 cosas: una memoria física (cinta), una memoria virtual (estado), un apuntador en la cinta, y una lista de instrucciones.
La máquina únicamente ve el símbolo que está escrito en la celda de la cinta que marca el apuntador, y el estado que contiene, y sigue la instrucción adecuada. Una instrucción dice básicamente "si el símbolo es 'a' y el estado es 'q', escribe 'b' y muévete hacia adelante/atrás". Entonces, si el apuntador señala al símbolo 'a' y la memoria contiene el estado 'q', la máquina va a borrar esa 'a' y escribir 'b' en su lugar, y luego mover el apuntador a la siguiente o anterior celda de memoria, dependiendo de lo que diga la instrucción.
Ahora, para decidir si una palabra pertenece o no al lenguaje, se incluyen también dos estados particulares: acepta y rechaza. Si la máquina encuentra alguno de estos estados, entonces se detiene y hace lo que el estado le indica. Existe otro caso adicional, que es cuando la máquina jamás encuentra uno de esos estados; en ese caso, la máquina debe rechazar la palabra.
Aqui nos topamos con un problema, porque si queremos implementar la máquina, nos gustaría saber si esta se va a detener cuando le demos la palabra, para poder rechazarla sin tener que dejar la máquina corriendo por siempre. ¿Es posible hacer esto?, es decir, ¿podemos saber de antemano si una máquina se va a detener?
Primero veamos que, utilizando únicamente máquinas de Turing, esto no es posible. Para esto vamos a usar una variación de la paradoja de Russell (¡qué maravillosas son las paradojas!).
Supongamos que existe una máquina de Turing, llamémosla T (de Todopoderosa), que puede decir en tiempo finito, dada otra máquina y una palabra, si esa otra máquina se va a detener o no cuando se ejecute con la palabra dada. Entonces, dada la máquina y la palabra, podemos saber si esta se acepta o no: primero ejecutamos la T, sabemos que se va a detener, y nos va a decir si la otra máquina se detendrá o no. Si dice que no, entonces simplemente decimos que la máquina rechaza la palabra; si dice que sí, entonces la ejecutamos y damos el resultado que da la máquina.
Ahora podemos crear la máquina D (de Demoniaca) que acepta a todas las máquinas de no se aceptan a sí mismas, es decir, que si se da una codificación de la máquina y ella misma, esta va a rechazar.
La pregunta ahora es ¿D se acepta a sí misma?. Ahí tenemos una contradicción por donde lo veamos, pues si se acepta, entonces se tiene que rechazar, y viceversa.