30 dic 2016

Cómo resolver el enigma de lógica más difícil del mundo

Hay enigmas complicados que se enuncian de forma muy sencilla. Los de lógica son un buen ejemplo: manejan términos que todos entendemos (como mentir o decir la verdad), pero tenemos que ser muy ocurrentes para resolverlos. El conocido como "problema de lógica más difícil del mundo" está al alcance de todos si lo abordamos sistemáticamente, y durante su resolución descubriremos técnicas muy útiles para lidiar con problemas de otro tipo. Su autor, Smullyan, un pianista, mago, humorista y matemático es más interesante aún que el propio enigma.

El problema fue publicado por George Boolos en la Harvard Review of Philosophy en 1996, pero su creador es Raymond Smullyan, un hombre fascinante cuyo retrato esbozamos al final de la entrada.

Aquí os dejo una versión equivalente que ha sufrido algunas modificaciones narrativas por mi parte, pero cuya esencia lógica sigue siendo exactamente la misma:

Enunciado "literario":

Estás frente a tres ordenadores A, B y C (aparentemente iguales) que responden "0" y "1" a preguntas del tipo "sí" o "no", y no se sabe si 0 significa no y 1 significa sí o viceversa ("0"="sí", "1"="no"). 

Uno de ellos tiene un sistema operativo Linux y siempre dice la verdad, otro es la computadora Skynet y siempre miente y otro lleva Windows y responde aleatoriamente, como si tirara una moneda y contestara "0" si sale cara y "1" si sale cruz. 

Haciéndoles tres preguntas del tipo "sí" o "no" (tienes que elegir a qué ordenador le haces cada pregunta [no vale preguntar algo y que contesten los tres] y puedes hacerles preguntas a ordenadores distintos) a las que contestarán con "1" o "0", ¿podrías determinar qué sistema operativo (Linux, Windows, Skynet) lleva cada ordenador (A,B,C)? ¿Cuáles serían esas tres preguntas?


Enunciado más sencillo:

Con tres preguntas de o no (a las que responderán con 1 ó 0), tienes que adivinar qué sujeto miente siempre, cuál dice la verdad y cuál responde aleatoriamente. Todo esto sin saber el significado real de 1 y 0 (sólo sabes que uno de ellos significa y el otro no).


Si has resuelto antes problemas de lógica, probablemente detectes intuitivamente dos factores que hacen que el enigma se complique bastante. El primero es evidente: al no saber traducir 0/1 a sí/no, tendremos que idear preguntas que permitan sacar información a los ordenadores incluso aunque no conozcamos el significado real de la respuesta. El segundo es que el factor aleatorio es lo más tocapelotas que te puedes encontrar: una pregunta al aleatorio (Windows) será una pregunta perdida.

Este último factor nos permite hacer la primera deducción acerca de la solución del problema: tendremos que preguntar necesariamente a más de un ordenador, ya que si le hacemos las tres preguntas a uno sólo y resulta ser Windows, no habremos obtenido ninguna información del mismo. Es práctico dibujar diagramas de árbol, escribiendo en cada rama las identidades posibles de cada ordenador según la respuesta obtenida (podemos caracterizar cada estado posible con tres letras: escribiendo en orden la identidad de A, B y C. Por ejemplo, MVA indica que A es Mentiroso, B es Verdadero y C es Aleatorio).

Una buena estrategia para solucionar un problema complejo es reducirlo antes a un problema más simple. Así pues, vamos a intentar resolver primero el enigma suponiendo que los ordenadores responden o NO. Una vez entendamos la estructura de la solución de este problema derivado, nos será mucho más fácil abordar el enigma que nos ocupa.

Otra deducción más filosófica: cada pregunta que hagamos creará dos ramas en nuestro diagrama, y asociados a esa rama tendremos un número de estados posibles. Por ejemplo, aquí tenemos, con la notación descrita arriba, la disyunción de estados que provoca preguntarle a A si es el aleatorio (en el problema, se llama Windows... A partir de ahora, por simplicidad, usaremos la terminología "aleatorio, mentiroso, verdadero"):




Es fundamental observar dos cosas:

  1. Hagamos la pregunta que hagamos, las dos posibilidades que contemplen que el preguntado sea aleatorio (en este caso, los estados AMV y AVM), estarán siempre presentes en ambas respuestas (ya que el aleatorio no nos aporta ninguna información).
  2. Es bueno hacer preguntas que, como esta, asocien un número igual de estados posibles a cada respuesta. ¿Por qué? Pues porque tras la segunda pregunta, hemos de quedarnos con (un mínimo de) dos estados asociados a cada respuesta, ya que la tercera pregunta dividirá éstos en dos y así determinaremos de forma única cuál es la identidad de cada ordenador con 3 preguntas. Si hiciéramos una primera pregunta que asociara, por ejemplo, cinco estados al SÍ, nos sería imposible llegar al estado mencionado con dos preguntas más (ya que cinco divido a la mitad dos veces es 1,25 > 1), y por tanto no podríamos solucionar el problema.
Nuestra mejor perspectiva, por tanto, es quedarnos con cuatro estados posibles tras la primera pregunta (es decir, descartar dos de los 6 estados posibles originales).

Combinando los dos puntos anteriores, llegamos a una paradoja aparente:


Si, tras hacer la primera pregunta, tenemos cuatro estados posibles, nuestra única opción para llegar a la solución es preguntar algo que divida por dos el número de estados, dejando 2 asociados al SÍ y 2 al NO. Pero, si la posibilidad de que el preguntado sea aleatorio aparece en ambas respuestas, tendríamos 3 estados tras la segunda pregunta, lo que nos llevaría a la conclusión de que es imposible resolver el problema.



Pues bien, las premisas son ciertas pero la conclusión es errónea, porque... ¿Y si estuviéramos seguros de que no estamos preguntando al aleatorio?

Esta es la última deducción que tenemos que hacer para resolver la versión reducida del enigma. Una vez nos demos cuenta de esto, sólo tenemos que probar inteligentemente varias combinaciones de preguntas que nos devulevan un conjunto de estados en los que no quepa la opción de que un determinado ordenador (A,B o C) sea aleatorio tras la primera pregunta, utilizando operadores lógicos sencillos: lo que los programadores conocen como ==, and, or,... y que los profanos conocen como "¿Es la respuesta que me das al preguntarte X igual a la que me das al preguntarte Y?", "¿Son las dos respuestas SÍ?", "¿Es alguna de las respuestas SÍ?",...

Esta es mi solución, una de las muchas posibles (puedes ver una solución alternativa que usa un operador lógico distinto en el apartado de fuentes al final de la entrada) [antes de la pregunta indico a quién va dirigida]:



Et voilà!  Observa las letras recuadradas bajo la primera respuesta: en el SÍ, no cabe la opción de que B sea aleatorio, y lo mismo pasa con C en el NO. Por eso, a partir de ese momento, sólo les preguntamos a ellos.

La segunda pregunta es simplemente para determinar si el interrogado es mentiroso o verdadero. Podríamos decir cualquier cosa cuya respuesta sea evidente, como ¿Existes?, ¿Es el término "monarquía parlamentaria" un oxímoron? ¿No es no? (esto sólo es válido para ordenadores que no sean del PSOE). Una vez lo hemos determinado, es coser y cantar, le hacemos una simple pregunta sobre la identidad de otro personaje y ya hemos averiguado quién es quién.


Volvemos al problema original


La adaptación de la solución del problema simplificado al de partida pasa por dos etapas: encontrar preguntas fructíferas aun desconociendo si 0/1 es SÍ/NO o NO/SÍ y adaptar (complicar) la estructura lógica de la solución anterior a este tipo de preguntas.

Con un poco de intuición (que podemos adquirir resolviendo muchos problemas de lógica más sencillos), hallamos esa pregunta mágica: ¿1 es SÍ?

Su magia está en que, independientemente del significado de 1, siempre que se lo preguntemos al verdadero responderá 1 y siempre que se lo preguntemos al mentiroso responderá 0 (haz la prueba). Por tanto, es una herramienta magnífica para determinar identidades.

Para rematar el problema, sólo nos queda la última etapa: añadir esta pregunta a la estructura de la solución anterior. Veréis que ese es el único cambio entre una y otra:



Vale, sí, la primera pregunta es bastante farragosa, pero es que es un enigma muy complejo☺.

Merece la pena reflexionar sobre otra enseñanza del problema: en lógica, no importa tanto el significado que le asociemos a cada símbolo; lo verdaderamente relevante es el contraste entre dichos símbolos, que podemos exprimir mediante operadores lógicos (como el que hemos usado aquí), siendo posible sacar conclusiones de palabras cuyo significado real no conocemos, pero entre las que hay una relación (son antónimos). Esto choca con nuestra experiencia cotidiana, donde lo fundamental es el valor absoluto de nuestros "signos lógicos" (como SÍ o NO) y no el valor relativo de los mismos.

Smullyan y Epiménides 


Puede que pensando el problema hayas imaginado ciertas preguntas que los ordenadores serían incapaces de contestar. Seguramente, todas ellas sean autorreferenciales (algún día hablaremos de los muchos quebraderos de cabeza que dio la autorreferencialidad a grandes lógicos como Bertrand Russell). Este tipo de paradoja se conoce desde hace milenios y la primera mención de la que tenemos constancia la hizo Epiménides, un poeta cretense del siglo VI AEC que (supuestamente) durmió una siesta de 57 años de la que se despertó con el don de la clarividencia. Este misterioso individuo afirmó que todos los cretenses eran mentirosos, y siendo él cretense, esto equivale a decir Yo miento o Esta frase es falsa. 

Si le preguntamos a algún ser racional (sea mentiroso o sincero) ¿Es esta frase falsa? (o alguna variante) será incapaz de contestar algo coherente, por lo que este tipo de preguntas están prohibidas en el problema. Aunque sería interesantísimo incluirlas (y hacer que a los ordenadores les pueda explotar la CPU cuando se las hacemos): en las fuentes os dejo una variante del problema en la que se permiten preguntas irrespondibles, siendo posible resolverlo ¡con sólo dos de ellas!




El del vídeo no es nada más y nada menos que Raymond Smullyan: un genial pianista, mago, humorista, lógico, filósofo, taoísta, escritor, matemático y, sobre todo... inventor por excelencia de problemas de lógica. Él es el creador de este acertijo (aunque técnicamente, en el suyo los ordenadores respondían sí y no), en el que encontramos elementos característicos de su vasta obra, repleta de caballeros que siempre dicen la verdad acompañados de escuderos que siempre mienten y de humanos que dicen lo que les da la gana.

Una de sus mejores recopilaciones de enigmas, cuentos y anécdotas lógicas es ¿Cómo se llama este libro? donde trata temas tan variados como el teorema de incompletitud de Gödel o la caracterización de la lógica, y te ayuda a casarte con la deseable Porcia (personaje de la entretenida y antisemita obra de Shakespeare El mercader de Venecia) y a determinar si aún vive Drácula. Además, es fácilmente legible porque está dividido en pequeñas secciones de menos de una página. Por ponerle una pega, la traducción al español es mala (y tengo pruebas contundentes de ello), así que try to read it in English.

Otro librazo suyo es Alice in Puzzle-Land, cuyo prólogo está escrito por Martin Gardner (también un excelente y longevo divulgador, que nos dejó hace unos años) y que tengo el honor de poseer, firmado por Raymond Smullyan. 



Os dejo una reseña de su interesantísima vida al final de la entrada (era profesor de piano pero se retiró por una lesión, también fue mago profesional y dio clase de asignaturas que nunca había cursado pero que dominaba; la universidad en la que trabajaba, por tanto, se las "convalidó").

Hoy, Smullyan tiene 97 años y vive (esperemos que durante mucho tiempo más) en el barrio de Queens de Nueva York. Si os fijáis, él ya no puede leer su propio cuento carroliano, según el subtítulo del mismo.

La mejor forma posible de acabar la entrada es con una anécdota de Smullyan sobre la esencia de la lógica, acompañada de un buen bis:

Un amigo —ex-oficial de policía—, cuando se enteró de* que yo era lógico de profesión, me dijo: "Deja que te explique cómo veo yo la lógica. El otro día, estaba con mi mujer en casa de una señora que nos ofreció tarta. En la bandeja había sólo dos trozos, uno mayor que otro. Tras un momento de reflexión, cogí el mayor. Mi razonamiento fue el siguiente: Sé que a mi mujer le gusta la tarta y que ella sabe que a mí también me gusta. También sé que ella me quiere y desea lo mejor para mí, de manera que ella habría querido que yo cogiera el trozo más grande. Por eso lo cogí."
Raymond Smullyan en ¿Cómo se llama este libro?



*: Los nefastos traductores del libro prescindieron de ese de. Esta es sólo una de las muchas erratas y errores de concepto de la versión castellana: en la página anterior, encontramos clock traducido como chimenea. Que conste que no he elegido esa sección porque esté especialmente plagada de erratas, éstas se distribuyen homogéneamente a lo largo y ancho de la obra. He hecho bastantes cambios en el párrafo citado para evitar el estilo anticuado e ineficiente de esos expertos en deslucir a Raymond traductores.







Fuentes y lectura recomendada

¿Cómo se llama este libro? - Raymond Smullyan

Enunciado original (en inglés):
http://gizmodo.com/5971702/the-hardest-logic-puzzle-ever-and-how-to-solve-it

Solución alternativa (en inglés):
https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever#The_solution

Disquisiciones sobre el comportamiento del aleatorio (en inglés):
https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever#Random.27s_behavior

Preguntas irrespondibles (en inglés):
https://en.wikipedia.org/wiki/The_Hardest_Logic_Puzzle_Ever#Unanswerable_questions_and_exploding_god-heads

Epiménides: https://es.wikipedia.org/wiki/Epim%C3%A9nides
http://blog.nueva-acropolis.es/2009/y-epimenides-durmio/

Smullyan: http://www.pianosociety.com/cms/index.php?section=1056

Artículo original: http://www.hcs.harvard.edu/~hrp/issues/1996/Boolos.pdf

No hay comentarios:

Publicar un comentario