Categoría: Ciencia

Voy a intentar explicar lo más detalladamente posible la solución al problema lógico de George Boolos. Sugiero que cojáis un lápiz y un papel para que no os perdáis por el camino.

Existen numerosos acertijos en los que tenemos un conjunto que dice la verdad y otro que miente, como en el siguiente, que es muy popular:

Existen dos países: en uno, sus habitantes dicen la verdad, y en el otro, sus habitantes mienten. Estamos en uno de los países y nos encontramos con un individuo, el cual puede ser de ese mismo país o puede ser del otro y estar de visita. Por lo tanto, ese individuo puede que nos mienta o nos diga la verdad. Trataremos de averiguar en qué país nos encontramos con una pregunta de sí o no.

Este caso es trivial: basta con encontrar una pregunta cuya respuesta sea unívoca para cada país, sin importar cuál sea la procedencia del individuo; por ejemplo, ¿eres de aquí? Si responde sí, estamos en el país de la verdad, si responde no, estamos en el país de la mentira.

En el problema que nos atañe, la cosa no es tan sencilla. ¿Por qué? Porque existe un tercer elemento, un tercer dios que responde aleatoriamente; esto significa que una respuesta suya –en principio, pues veremos que no es cierto– no nos aporta ninguna información. Por lo tanto, para nuestra primera pregunta nuestros esfuerzos deben centrarse en hallar a un dios que no sea Azar, para después proceder como en el acertijo del ejemplo y realizar dos preguntas cuya respuesta sea unívoca (ahora estamos seguros, pues ese no es Azar).

La existencia de un dios Azar y el desconocimiento del significado de ‘ja’ y ‘da’ nos obliga a construir preguntas complejas como bicondicionales o estructuras similares. Veamos cómo.

En primer lugar, preguntaremos a B: ¿si te preguntase si A es Azar, me responderías ‘ja’? Ante esta pregunta, vamos a observar qué deduciríamos si B fuera Verdad o fuera Mentira en dos casos posibles:

1. Ja = Sí; Da = No.
   • Verdad diría Ja, luego A es Azar y C no es Azar.
   • Verdad diría Da, luego C es Azar y A no es Azar.
   • Mentira diría Ja, luego A es Azar y C no es Azar.
   • Mentira diría Da, luego C es Azar y A no es Azar.
2. Ja = No; Da = Sí.
   • Verdad diría Ja, luego A es Azar y C no es Azar.
   • Verdad diría Da, luego C es Azar y A no es Azar.
   • Mentira diría Ja, luego A es Azar y C no es Azar.
   • Mentira diría Da, luego C es Azar y A no es Azar.

¿Veis la belleza de la pregunta? Efectivamente: independientemente del significado de ‘ja’ o ‘da’ obtenemos la misma respuesta. Por lo tanto, si B es Verdad o Mentira, podemos deducir quién es Azar. Pero esto no nos importa; lo realmente importante es quién NO es Azar, puesto que en el caso de que B sea Azar, la conclusión extraída pensando que B es Verdad o Mentira es igualmente válida.

Así que ya tenemos el primer paso. Si la respuesta a la primera pregunta es ‘ja’, sabemos con certeza que C no es Azar (bien por el análisis anterior, o bien porque el análisis nos da igual puesto que B es Azar), y si la respuesta es ‘da’, sabemos con certeza que A no es Azar. Primer objetivo cumplido. Al dios que acabamos de descartar como Azar, lo llamaremos X, y será objetivo de las dos últimas preguntas.

La segunda pregunta irá dirigida a X: ¿si te preguntase si eres Verdad, me responderías ‘ja’? Como veremos, las posibilidades se reducen, puesto que X puede ser únicamente Verdad o Mentira. Los casos posibles son los siguientes:

1. Ja = Sí; Da = No.
   • Verdad sólo podría decir Ja, luego X es Verdad.
   • Mentira sólo podría decir Da, luego X es Mentira.
2. Ja = No; Da = Sí.
   • Verdad sólo podría decir Ja, luego X es Verdad.
   • Mentira sólo podría decir Da, luego X es Mentira.

Comprobamos cómo la pregunta realizada es (aunque más complicada en su formulación) muy parecida a la del acertijo del ejemplo. Hemos conseguido una respuesta unívoca, puesto que de nuevo no depende del significado de ‘ja’ o ‘da’.

Tras esta segunda pregunta, tenemos identificado al dios X totalmente (que será A o C, como ya hemos visto). Si la respuesta ha sido ‘ja’, X es Verdad; si la respuesta ha sido ‘da’, X es Mentira.

Entonces, la tercera y última pregunta será de nuevo para X: ¿si te preguntase si B es Azar, me responderías ‘ja’? Una pregunta análoga a la anterior que conlleva un análisis idéntico, así que me lo voy a ahorrar.

Lógicamente, si la respuesta es ‘ja’, B es Azar; si la respuesta es ‘da’, el otro dios restante (A o C, el que no sea X) será Azar; y todo ello independientemente del significado de ‘ja’ y ‘da’. Así pues, segundo dios identificado totalmente y, de rebote, el tercero, por descarte.

George Boolos, filósofo y estudioso de la lógica matemática que trabajó en el MIT, bautizó al siguiente problema como The Hardest Logic Puzzle Ever. Boolos atribuye su origen al lógico Raymond Smullyan, por estar inspirado en los acertijos de éste, y a John McCarthy, por añadir la dificultad del desconocimiento del significado de las palabras ‘da’ y ‘ja’:

Tres dioses A, B, y C son llamados, en algún orden, Verdad, Mentira, y Azar. Verdad siempre habla expresando la verdad, Mentira siempre habla expresando algo falso, pero la respuesta de Azar es completamente aleatoria pudiendo ser verdadera o falsa. Su tarea es determinar las identidades de A, B, y C formulando un máximo de tres preguntas cuya respuesta es sí o no; cada pregunta debe ir dirigida a un único dios y es posible hacer más de una pregunta a un mismo dios. Los dioses entienden español, pero contestarán a las preguntas en su propio idioma, en el cual las palabras para ‘sí’ y ‘no’ son ‘da’ y ‘ja’, en algún orden. Usted no sabe qué significado se asocia a cada palabra.

Mañana publico la solución. Mientras tanto, comeos un rato el coco: 100 gallifantes para el que lo resuelva sin mirar.

(Vía: cgredan blog)