PABLO NOGUEIRA
Alan Turing demostró en su famoso teorema de
indecibilidad que no es posible escribir un programa de ordenador que nos diga
si otro programa cualquiera se queda o no se queda colgado. Este es el famoso
«problema de la parada» para el que no hay programa posible.
Este teorema tiene consecuencias importantes para la programación de ordenadores. En esta entrada voy a intentar explicar el teorema sin usar matemáticas. Además, para no aburrir a los que ya se lo saben, voy a explicar que el mismo resultado se aplica a las personas, y que ese famoso debate acerca de que la indecibilidad es lo que distingue a los programas de las personas no tiene fundamento (más abajo hablo un poco más de esto y doy algunas referencias).
El problema que Turing deseaba estudiar era el de si dada una función matemática sobre números se puede escribir un programa que la calcule. Para ello Turing tuvo que definir qué es un programa y así inventó sus famosas «máquinas». Nosotros asumiremos sin más que los programas son esos prodigios que instalamos y utilizamos.
Empecemos explicando qué es una función matemática sobre números. Aquí va un ejemplo:
«Dame un número, y te devuelvo el doble de ese número»
Una función será para nosotros una frase que nos pide que calculemos un número a partir de otro. La tarea del programador será escribir un programa que realiza, es decir, calcula, esa función.
Un programa calcula esa función cuando al darle un número al programa éste nos devuelve el doble como resultado. El programa puede, por ejemplo, sumar el número consigo mismo, o multiplicarlo por dos, o multiplicarlo por seis y dividir el resultado por tres, o todo lo complicado que queramos hacerlo siempre y cuando el resultado sea correcto.
Las funciones pueden ser todo lo complicadas que queramos:
«Dame un número, y te devuelvo la raíz cuadrada de ese número»
«Dame un número, y te devuelvo el coseno de la integral, entre ese número y su cuadrado, del seno de ese número multiplicado por tres»
Las funciones también pueden ser muy tontas, como esta:
«Dame un número, y me quedo colgado»
No parece tener mucha utilidad, pero todos sabemos que existe un programa para esta función. Lo usan mucho las empresas que desarrollan sistemas operativos para ordenadores personales.
He aquí una variación sobre el mismo tema:
«Dame un número y si el número es par entonces me quedo colgado, pero si el número es impar entonces no me quedo colgado, te devuelvo el número 7»
Es sencillo construir un programa para esta función. Basta con ver si el resto de dividir el número entre dos es cero. De ser así entonces el número es par y lo que hay que hacer es ejecutar el programa de quedarse colgado. Pero si el resto no es cero, entonces el número es impar y lo que hay que hacer es devolver el número 7.
Un ingrediente fundamental del que depende todo
el argumento es que los programas se pueden enumerar. Es decir, a un programa
le corresponde un número. Al truco matemático se le suele denominar
«Gödelización» en honor al mítico Kurt Gödel, que también lo usó en su famoso
(y muy parecido) teorema de incompletitud de los sistemas formales. Aquí
explicaremos la Gödelización de forma sencilla: los programadores escriben los
programas en un editor de texto, así que basta con que hagan click en guardar y
usen un número diferente como nombre de fichero para cada programa. Listo.
Ya estamos en situación de hacer la pregunta del millón:
¿Tienen todas las funciones programas que las calculan?
I'm afraid not — dijo Alan.
¿Cómo?
Pues aquí tenéis una función para la que no hay programa posible:
Dame un número, y si el programa con ese número no se queda colgado entonces devuelvo el número 1, pero si el programa con ese número sí se queda colgado entonces devuelvo el número 0.
Esta es la función de decidir si otro programa se queda o no se queda colgado, en el que 1 significa «no se queda colgado» y en el que 0 significa «sí se queda colgado».
Puede parecer increíble, pero NO podemos escribir un programa que calcule esta función. Si suponemos que podemos escribirlo, vamos a tener un papelón. Veamos los detalles.
Supongamos que podemos escribir el programa. Entonces también podemos escribir este otro programa:
«Dame un número y si el programa con ese número sí se queda colgado entonces no me quedo colgado (te devuelvo el número 7), pero si el programa con ese número no se queda colgado entonces sí me quedo colgado»
Esta es la función de llevar la contraria, una función con poca utilidad aparente. Algunos marquesitos de cuatro años que conozco intentan calcularla siempre que pueden.
Si hubiera un programa para la función de llevar la contraria, dicho programa tendría un número, el que fuera. Para concretar, supongamos que es el 42, aunque cualquier otro número nos vale para el argumento.
¿Qué pasa si le damos el número 42 a ese programa número 42? Intentadlo primero antes de leer el siguiente párrafo.
Pues que el programa 42 sí se queda colgado cuando el programa 42 no se queda colgado, y que el programa 42 no se queda colgado cuando el programa 42 sí se queda colgado.
Un sinsentido, imposible.
¿Por qué hemos llegado a un sinsentido? Porque hemos asumido que se puede escribir el programa que determina si otro programa se queda o no se queda colgado. Si descartamos que existe, adiós al sinsentido.
Ahora vamos a hacerlo más interesante. En todas las funciones que hemos dado, reemplacemos «quedarse colgado» por «quedarse en silencio». Y reemplacemos «programa» por «persona». Como bien saben en la administración pública, una persona es un número, digamos, un NIF/NIE. Leemos de nuevo el argumento y tenemos el Problema de la Parada de las Personas: no hay una persona que pueda realizar la función de determinar si otra persona arbitraria se queda en silencio. Menudo papelón tiene el Señor 42. Se queda en silencio pero no se queda en silencio. No existe un Señor 42 capaz de realizar esa función.
¿Dónde está la chicha?
En la autoreferencia, de la cual se pueden obtener muchos sinsentidos o «paradojas», algunas de las cuales han dado para mucho.
De hecho, el argumento es bastante malvado: de existir el programa 42, se tendría un sinsentido, por tanto el programa 42 no existe, y por tanto hay funciones que no tienen programas. O de otra manera, el Señor 42 no puede estar y no estar en silencio, por tanto no hay Señor 42, y por tanto hay señores que no pueden decir si otros se quedan en silencio. ¡Pero sólo porque habría uno que se contradiría a sí mismo!
El Problema de la Parada de los Programas complica mucho las cosas a los pobres programas. No se puede tener un programa que nos diga si otro programa cualquiera se queda colgado o no. Por tanto, tampoco hay un programa que nos diga si dos programas calculan la misma función, pues ¿qué nos podría decir el programa comparador si los dos programas se cuelgan? Algo similar les pasaría a las personas.
Más que de matemáticas complejas, es un asunto de paradojas lógicas. Otra paradoja famosa es la paradoja del mentiroso, la de aquel cretense que dijo «todos los cretenses son mentirosos». ¿Puede el lector decidir si dice la verdad o si miente? Otra también muy famosa es la paradoja de Bertrand Russell, que cayó en la cuenta de que el club formado por aquellos clubes con menos de dos miembros es un club con más de dos miembros, y por tanto no es miembro de sí mismo. Pero curiosamente hay clubes que son miembros de sí mismos, como el el club formado por aquellos clubes con más de dos miembros. Rizando el rizo, Bertrand se preguntó si el club formado por todos los clubes que no son miembros de sí mismos puede ser miembro de sí mismo … y entonces se quedó en silencio. Esta paradoja y su resolución tuvo consecuencias importantísimas en los fundamentos de la matemática, la lógica y los lenguajes de programación. Otra de consecuencias similares es la versión de la paradoja del mentiroso de Kurt Gödel, manifestada en su sentencia «esta sentencia no es demostrable por un sistema formal». Un sistema formal que demuestra esa sentencia está demostrando falsedades. Un sistema sistema formal que no la demuestra no es capaz de demostrar todas las verdades, pues no es capaz de demostrar esa sentencia, haciéndola verdadera.
El Problema de la Parada de los Programas ha sido
usado como argumento para intentar diferenciar las capacidades de las personas
de las de los programas. Cito algunos nombres ilustres en el debate, por si se
quiere buscar más información: John R. Lucas, Roger Penrose, C. H. Whiteley,
Douglas Hofstadter, Solomon Feferman, Jack Copeland, Ron Chrisley, etc. El
título de «Problema de la Parada de las Personas» lo escuché por primera vez de
boca de
Ron Chrisley, que amablemente me concedió que se trata de una variación
de la respuesta que C. H. Whiteley le dio a John Lucas. Este último fue pionero
en utilizar el Problema de la Parada para establecer distinciones. La respuesta
de Whiteley es a mi juicio la más corta, directa y efectiva. La leí por primera
vez en el famoso libro de Douglas Hofstadter. Más referencias se pueden encontrar aquí.
Para terminar, menciono el Teorema de Henry Gordon Rice, que establece que hay más funciones huérfanas de programas de las que podemos contar. En concreto, hay tantas como números reales. Eso son muchas funciones.
Pablo Nogueira es profesor ayudante doctor de la Universidad Politécnica de Madrid
Hay 12 Comentarios
el cretense mentía, porque no todos los cretenses son mentirosos pero él sí.
Publicado por: fran | 25/12/2013 14:14:47
Qué artículo tan mal redactado.
Publicado por: pepe | 24/12/2013 19:47:27
El Problema de la Parada se puede generalizar al Problema de Hacer X, sea X parar, quedarse en silencio, hablar, pensar, tomarse una tarta de queso, etc.
Teorema: Sea X cualquier cosa que asumimos que puede hacer una persona. No hay ninguna persona capaz de realizar esta función "Dame un número, y decido si la persona con ese número hace X". La función de llevar la contraria sería "Dame un número, y si la persona con ese número hace X entonces yo no hago X, pero si la persona con ese número no hace X entonces yo hago X". No puede haber un Sr 42 capaz de hacer y no hacer X al mismo tiempo, ¿verdad?
Publicado por: Pablo Nogueira | 05/07/2013 15:46:18
@joan: Muy buena apreciación. Aunque la palabra "paradoja" y "contradicción" se suelen utilizan indistintamente. Técnicamente, una contradicción es una fórmula insatisfacible, lo opuesto a una tautología. Una paradoja es una sentencia autocontradictoria. Naturalmente, estas definiciones son incompletas porque depende del contexto (lógica formal, lógica completa, filosofía, etc.) En el artículo las uso de forma intuitiva.
Aquí van algunos enlaces (que por supuesto no son la fuente definitiva)
http://en.wikipedia.org/wiki/Satisfiable
http://en.wikipedia.org/wiki/Paradox
http://en.wikipedia.org/wiki/Tautology_%28logic%29
http://en.wikipedia.org/wiki/Contradiction#Contradiction_in_formal_logic
Publicado por: Pablo Nogueira | 02/07/2013 12:24:56
La proferencia del cretense que afirma que todos los cretenses son mentirosos no es una paradoja, sino más bien una contradicción: tan solo es cierto que no puede ser verdadera. Existen situaciones posibles en las que la proferencia es falsa. De hecho, es falsa si hay al menos un cretense que diga la verdad, distinto de quien realiza la proferencia en cuestión.
Sin embargo, ese mismo enunciado no puede ser proferido con verdad por ningún cretense: si una tal proferencia de un cretense fuese verdadera, debería ser también falsa (al ser proferida por un cretense, quien, de acuerdo con lo que la propia proferencia afirma supuestamente con verdad, es mentiroso).
Propiamente, una proferencia es paradójica si no puede ser ni verdadera ni falsa pues de su verdad puede inferirse su falsedad, y viceversa. Una proferencia es una contradicción si no puede ser verdadera.
Publicado por: joan | 02/07/2013 11:08:11
Gracias Hernán por tu comentario (y por tu correo electrónico). Me he equivocado con el teorema de Rice en la contribución al blog. Tal y como dices, el teorema de Rice versa sobre la distinción de funciones computables en clases, no va de cardinalidad (de si el conjunto de funciones no computables tiene la misma cardinalidad que los reales). Sospecho que mi confusión viene de mezclar el argumento diagonal de Turing con el de Cantor, que demostró que hay más números reales que naturales usando el argumento diagonal. Como el conjunto de funciones computables es numerable, he afirmado que el conjunto de funciones no computables tiene la misma cardinalidad que los reales... un lío.
El teorema de Rice tiene todo el sentido a la luz del problema de la parada. No se puede decidir si un programa termina, de esto se sigue que no se puede decidir si dos programas son iguales, y de esto se sigue que no es posible determinar si un programa pertenece a una clase de programas que no sea "trivial".
Publicado por: Pablo Nogueira | 02/07/2013 10:14:50
Agrego un comentario sobre el teorema de Rice.
Si damos la descripción de una función, habrá muchos programas que la cumplen; por ejemplo, "La clase de programas que reproducen mp3 y nada más" es una descripción posible, y el teorema de Rice plantea que esas funciones que sí cumplen con la descripción no podrían diferenciarse en general de otras que no la cumplieran! (al menos no podrían diferenciarse mediante un algoritmo), no podemos hacer un Test que las distinga de cualquier otra clase complementaria (por ejemplo "la clase de programas que no reproducen mp3 y son un virus que borran el disco!"). Esto tiene consecuencias, por ejemplo que en teoría hacer un software antivirus infalible, es imposible...
De nuevo, inspirador artículo, Saludos!
Publicado por: Hernan Echegoyemberry | 01/07/2013 16:36:17
@Hernan: La respuesta que Whiteley le dio a Lucas fue en relación al teorema de incompletitud de Gödel. Al final de la contribución están mezclados los dos debates, el de los que usan el resultado de Turing y los que usan el resultado de Gödel para establecer distinciones entre máquinas y personas.
La respuesta que Whiteley le dio a Lucas puede leerse en detalle en su artículo (ver la cuarta entrada de la bibliografía listada en la URL que doy al final del artículo.)
Resumiendo, Whiteley le dijo a Lucas que es la autoreferencia lo que causa el problema, que la paradoja es intrínseca a la frase y no a quién la intenta realizar. En concreto le dijo a Lucas que la frase "Lucas no puede afirmar de forma consistente si esta frase es cierta" no puede ser afirmada de forma consistente por Lucas.
Publicado por: Pablo Nogueira | 28/06/2013 17:24:49
La parte
"Puede parecer increíble, pero NO podemos escribir un programa que calcule esta función."
En realidad no podemos escribir "en general" un programa que calcule esta función. Hay que aclarar eso, sino un programa que sea
Si programaEntrada == "quedarse colgado", entonces avisar con 1, sino 0.
Ese programa puede detectar al menos 1 programa que se queda colgado (bastante obvio por cierto). Pero por ser precisos hay que aclararlo.
Por otro lado "La respuesta de Whiteley es a mi juicio la más corta, directa y efectiva", ¿Cuál es esa respuesta?
Gracias por publicar sobre este tema, buen artículo!
Publicado por: Hernan Eche | 28/06/2013 14:25:46
Uno de los aspectos que intenta explicar el artículo es que paradojas como las del mentiroso afectan a máquinas de cualquier tipo o a personas. Las personas no podemos decir si la frase "Esta frase es falsa" es falsa o verdadera, pues si decimos que es falsa eso significa que es verdadera, pues la frase dice que es falsa como hemos dicho que es. Por otro lado, si decimos que es verdadera eso signfica que es cierto que la frase es falsa, pero entonces es que es falsa.
Es un problema de autoreferencia y da igual que se lo preguntemos a una persona, a una máquina, o a lo que sea. La indecibilidad de la frase es intrínseca a la frase, no a quien la intente decidir.
La diferencia entre las máquinas y las personas no está en saber decidir esa frase. Por ahí no debe ir el argumento.
Publicado por: Pablo Nogueira | 28/06/2013 13:33:10
Muy bueno el artículo y la explicación sin necesidad de acudir a expresiones matemáticas abstractas. Me ha sorprendido gratamente encontrar algo así en un medio como este. Enhorabuena!
Yo creo que uno de los problemas con la famosa polémica sobre si la indecibilidad es lo que distingue a los programas de las personas es precisamente que se identifica a los programas con "máquinas de Turing", concretamente con lo que el propio Turing llamaba "máquinas automáticas", es decir, máquinas que simplemente, dada una entrada (un número) se limitan a generar una salida (el resultado) tras un proceso de computo.
Pero los ordenadores a los que estamos acostumbrados hoy en día no son sólo eso: como nosotros, tienen la capacidad de interaccionar con el mundo mientras ejecutan sus programas... son más bien lo que el propio Turing llamó ya en su día "máquinas oráculo", que no eran más que una versión "mejorada" de lo que hoy conocemos simplemente como "máquinas de Turing". Quizá una de estas "máquinas-o" si podría dar una respuesta satisfactoria a la paradoja del mentiroso, tal y como nosotros, los humanos, hacemos...
Publicado por: ignacio.lp | 28/06/2013 0:54:26
Parece bastante interesante. Sin embargo, aún conociendo y entendiendo el teorema de Gödel, los principios del atomismo lógico y las tteorías de Penrose, entre otros que se mencionan y que conozco, no me queda tan claro el artículo, debe ser por la falta de meticulosidad o de un ejemplo más claro y accesible a la descripción del prefijo griego meta, es decir, a la parte de la explicación de que un sistema cerrado no puede dar la explicación sobre sí mismo. Hay problemas de proposición en las nociones de identidad, específicamente, cuando se le asigna el número 42 no queda claro si es parte de la misma función de calculo o no, es decir, un calculo sobre un calculo. Pero puede ser también mi corto entendimiento. En cualquier caso, las personas no son sistemas cerrados, por lo tanto, apicarlo a las personas es una falacia.
Publicado por: Daniel | 27/06/2013 23:01:38