L'indovinello più difficile del mondo

L'indovinello più difficile del mondo (The Hardest Logic Puzzle Ever) è un indovinello di logica proposto da George Boolos e ispirato da una versione precedente e più semplice di Raymond Smullyan.

Gli oracoli Verace, Mendace e Imprevedibile. In realtà Odino, Thor e Freyja da un arazzo medievale.

Formulazione

«Tre oracoli divini A, B, e C sono chiamati, in un qualche ordine, Verace, Mendace e Imprevedibile. Verace dice sempre il vero, Mendace dice sempre il falso, mentre Imprevedibile decide se essere sincero o meno in modo completamente casuale. L'obiettivo del gioco è determinare le identità di A, B, e C ponendo loro tre domande a cui è possibile rispondere con un "sì" o con un "no". Ogni domanda deve essere posta a uno solo degli oracoli, che, pur comprendendo l'italiano, risponderà sempre nella propria lingua con le parole "da" o "ja". Non si sa quale di questi termini corrisponda a "sì" e quale a "no".»

Analisi del problema

Le risposte degli oracoli prevedono solo due valori (vero/falso, sì/no). Con tre risposte significative si possono identificare (al massimo) 2³ = 8 alternative. Nel caso presente bisogna individuare la combinazione giusta tra sei disposizioni possibili dei tre oracoli:

1. Verace-Mendace-Imprevedibile
2. Verace-Imprevedibile-Mendace
3. Mendace-Verace-Imprevedibile
4. Mendace-Imprevedibile-Verace
5. Imprevedibile-Verace-Mendace
6. Imprevedibile-Mendace-Verace

Se si volesse individuare anche se da/ja significano si/no o viceversa, avremmo un totale di dodici alternative possibili e sarebbe necessario ottenere una quarta risposta.

Bisogna quindi rinunciare a priori a conoscere il significato esatto di da e di ja, e formulare delle domande tali che alla risposta da (o ja) possiamo attribuire con certezza, di volta in volta, il significato di vero o falso.

Le domande dovranno inoltre essere tali che la risposta da (o ja) abbia lo stesso valore di vero o falso, sia che venga dall'oracolo Mendace che dall'oracolo Verace. Bisogna anche trovare il modo di neutralizzare l'incertezza derivante dal comportamento dell'oracolo Imprevedibile.

Rimane fondamentale l'osservazione che la prima mossa è quella di trovare un oracolo che si possa essere certi non sia Imprevedibile, non ha importanza se sia Vero o Falso.

Soluzioni

Una strategia è quella di usare connessioni logiche complicate nelle domande, come la sequenza di "Se e solo se" o costruzioni equivalenti. Per esempio la domanda:

«'da' significa 'sì' se e solo se tu sei Verace e se e solo se B è Imprevedibile?»

è equivalente a:

«È vero un numero dispari delle affermazioni: tu sei Mendace, 'ja' significa 'sì', B è Imprevedibile?»

Ma ci sono anche altre proposte di soluzione.

Soluzione originale di Boolos

Nel testo inglese Boolos chiama i tre oracoli "dio Vero" (True), "dio Falso" (False) e "dio Casuale" (Random) ma l'uso di questi sinonimi non cambia in niente l'impostazione del discorso.

La prima domanda, da porre per esempio all'oracolo A, è:

«da significa sì se e solo se tu sei Vero, se e solo se l'oracolo B è Casuale?»

Se la risposta è da si può essere certi che l'oracolo C non è Casuale e, se la risposta è ja, si può essere certi che l'oracolo B non è Casuale. Infatti, se A è Vero o Falso, la risposta è significativa e permette di fare la scelta giusta mentre, se A è Casuale, certamente né B né C possono essere Casuale!

La seconda e terza domanda, da porre all'oracolo non Casuale così individuato, potranno essere:

"da significa sì, se e solo se Roma si trova in Italia?"

La risposta da significa che l'oracolo interpellato è Vero, la risposta ja significa che l'oracolo è Falso.

"da significa sì, se e solo se l'oracolo A è Casuale?"

La risposta da significa che l'oracolo A è Casuale, la risposta ja significa che non lo è.

Dalle risposte a queste domande si deduce facilmente se l'oracolo che si sta interpellando è Vero o Falso e se A è o no Casuale. Di conseguenza è determinato anche il terzo oracolo, quello non interpellato.

Spiegazione

Si sfrutta la proprietà della co-implicazione logica materiale tra due proposizioni, unite dalla condizione "se e solo se". Cioè, date due proposizioni P e Q, alla domanda: [è vero che] "P se e solo se Q?" la risposta è no (=falso) solo se una delle due proposizioni è vera e l'altra falsa. Altrimenti la risposta è sì (=vero), sia che P e Q siano entrambe vere, sia che siano entrambe false.

Si può allora facilmente verificare che se si chiede a un dio oracolo che dica la verità:

[è vero che] "da significa sì, se e solo se Q?"

la risposta sarà da se Q è vera e sarà ja se Q è falsa, indipendentemente dal significato reale di da (ovviamente un oracolo che dica il falso darebbe risposte opposte).

Si può facilmente verificare anche che, se si chiede a un dio oracolo che risponda in italiano:

[è vero che] "tu dici la verità, se e solo se Q?"

la risposta sarà sì se Q è vera, mentre sarà no se Q è falsa, indipendentemente dal fatto che l'oracolo dica sempre la verità o sempre il falso.

Combinando queste due osservazioni e tornando agli oracoli dell'indovinello, se si chiede al primo di loro:

[è vero che] "da significa sì, se e solo se tu dici la verità, se e solo se Q?"

la risposta sarà da, se Q è vera, e sarà ja, se Q è falsa, indipendentemente dal significato reale di da e indipendentemente dal fatto che l'oracolo sia Vero o Falso.

Per sgombrare il campo dal comportamento di Casuale, bisogna scoprire, fin dalla prima risposta, un dio oracolo che non sia Casuale. Ciò si ottiene per esempio mettendo, nella domanda che si pone all'oracolo A, al posto di Q, la proposizione "l'oracolo B è Casuale". La domanda diventa:

[è vero che] "da significa sì, se e solo se tu sei Vero, se e solo se l'oracolo B è Casuale?"

Altre soluzioni

Roberts nel 2001 e Rabern and Rabern nel 2008 hanno osservato che la soluzione dell'enigma può essere semplificata usando certi condizionali ipotetici.
L'ipotesi di Boolos risulta tuttavia fallace. La chiave di questa soluzione è che, data una qualunque domanda Q del tipo sì/no, se si pone la domanda P:

• Se ti chiedessi Q mi diresti 'ja'?

il risultato è:

'ja': se l'effettiva risposta a Q è 'sì';

'da': se l'effettiva risposta a Q è 'no'.

indipendentemente dal fatto che l'oracolo interpellato sia Vero o Falso (ma non Casuale).
Allora si può procedere come segue.

• Si chieda al dio A, "Se ti chiedessi 'B è Casuale?', diresti 'ja'?"
  • Se A risponde 'ja', allora o A è Casuale (e sta rispondendo casualmente), oppure A non è Casuale e la risposta indica che B è effettivamente Casuale. In ogni caso, C non è Casuale.
  • Se A risponde 'da' allora, di nuovo, o A è Casuale (e sta rispondendo casualmente), oppure A non è Casuale e la risposta indica che B non è Casuale. In ogni caso B non è Casuale.
• Si vada dal dio che si è stabilito non essere Casuale grazie alla risposta precedente (quindi B oppure C), e gli si chieda: "Se ti chiedessi 'Sei Vero?' diresti 'ja'?" Siccome non è Casuale la risposta 'ja' indica che è Vero e la risposta 'da' indica che è Falso.
• Si ponga allo stesso dio la domanda: "Se ti chiedessi 'A è Casuale?' diresti 'ja'?" Se la risposta è 'ja' allora A è Casuale, se la risposta è 'da' allora il dio non ancora interpellato è Casuale. Il dio rimasto si può identificare per esclusione.

Spiegazione

Si può verificare che ciò funziona esaminando tutti gli otto casi possibili (l'oracolo può essere Vero/Falso, la risposta può essere da/ja, 'ja' può significare si/no).

• Si supponga che 'ja' significhi 'sì' e 'da' significhi 'no'.

(I) Si pone la domanda P a Vero e si ottiene come risposta 'ja'. Dal momento che egli dice la verità, la reale risposta a Q è 'ja', che significa 'sì'.
(II) Si pone la domanda P a Vero e si ottiene come risposta 'da'. Dato che dice la verità, la reale risposta a Q è 'da', che significa 'no'.
(III) Si pone la domanda P a Falso e si riceve come risposta 'ja'. Egli mente, ciò significa che se gli venisse posta la domanda Q risponderebbe 'da', mentendo; perciò la risposta effettiva alla domanda Q è 'ja', che significa 'sì'.
(IV) Si pone la domanda P a Falso e si riceve come risposta 'da'. Egli mente, ne consegue che se gli fosse posta la domanda Q risponderebbe 'ja', mentendo; quindi la risposta effettiva alla domanda Q è 'da', che significa 'no'.

• Si supponga che 'ja' significhi 'no' e 'da' significhi 'sì'.

(V) Si chiede P a Vero e risponde 'ja'. Dato che dice la verità, la risposta reale a Q è 'da', che significa 'sì'.
(VI) Si chiede P a Vero ed egli risponde 'da'. Siccome dice la verità, la risposta corretta a Q è 'ja', che significa no.
(VII) Si chiede P a Falso e la risposta è 'ja'. Dal momento che mente, se gli fosse posta Q risponderebbe 'ja', mentendo; quindi la risposta corretta a Q è 'da', che significa 'sì'.
(VIII) Si chiede P a Falso e risponde 'da'. Siccome sta mentendo, se gli venisse posta Q risponderebbe 'da', mentendo; quindi la risposta corretta a Q è 'ja', che significa 'no'.

In sintesi la domanda P contiene la domanda Q, quindi è a due strati: pone la domanda Q e contemporaneamente chiede la conferma che la risposta a Q sia "sì" (o "no").
L'oracolo Vero risponderà "sì" (o "no") -- cioè con la stessa risposta contenuta nella domanda P -- se la risposta a Q è "sì"; dovrà rispondere "no" (o "sì") -- cioè invertendo la risposta contenuta nella domanda P -- se la risposta a Q è "no".

L'oracolo Falso negherà che avrebbe dato una risposta falsa e, in definitiva, darà anch'egli una risposta uguale a quella dell'oracolo Vero.

Altra possibile soluzione: il comportamento di Casuale

La maggior parte dei lettori dell'indovinello suppone che il casuale fornirà completamente a caso le risposte a qualunque domanda; ma l'indovinello non lo dice. Infatti una affermazione chiarificante di Boolos ribadisce fortemente questo:

• Se Casuale dica o no la verità è come se dipendesse dal lancio di una moneta nascosta nel suo cervello: se esce testa dice la verità; se esce croce mente.

Questo significa che Casuale casualmente agisce come bugiardo o verace, e non che risponde casualmente.

Inseriamo un cambiamento nella prima domanda, in modo da ottenere sempre una risposta significativa, anche da Casuale:

Se ti chiedessi Q nel tuo attuale stato mentale, risponderesti 'ja'?

Abbiamo così separato le due personalità di Casuale, quella verace e quella bugiarda, e abbiamo costretto il dio a essere una sola di queste. Questo banalizza completamente l'indovinello, in quanto ora possiamo avere la risposta vera a ogni domanda.

• 1. Si chieda al dio A "Se ti chiedessi 'Sei Casuale?' nel tuo corrente stato mentale, diresti 'ja'?"

Se A risponde 'ja', allora A è Casuale: un caso fortunato, in cui basta una sola altra domanda per risolvere l'indovinello.

• 2a. Si chieda al dio B "Se ti chiedessi 'Sei Vero?', diresti 'ja'?"

Se B risponde 'ja' allora B è Vero e C è Falso.
Se B risponde 'da' allora B è Falso e C è Vero. In entrambi i casi l'indovinello è risolto.

Se A risponde 'da' allora A non è Casuale: con altre due domande allo stesso A risolviamo l'indovinello.

• 2b. Si chieda al dio A "Se ti chiedessi 'Sei Vero?', diresti 'ja'?"

Se A risponde 'ja', allora A è Vero.
Se A risponde 'da' allora A è Falso.

• 3. Si chieda al dio A "Se ti chiedessi 'B è il casuale?' diresti 'ja'?"

Se A risponde 'ja' allora B è Casuale e C è il contrario di A.
Se A risponde 'da' allora C è Casuale è B è il contrario di A.

Se si modifica l'enunciato dell'indovinello in modo tale che la risposta di Casuale sia effettivamente casuale:

Se Casuale dica 'ja' o 'da' è come se dipendesse dal lancio di una moneta nascosta nel suo cervello: se esce testa, dice 'ja'; se esce croce, 'da'.

la soluzione dell'indovinello richiede la più attenta interrogazione data nella sezione precedente.

Domande a cui non si può rispondere e teste di dei che esplodono

In A Simple Solution to the Hardest Logic Puzzle Ever, l'indovinello è svolto facendo notare che non è il caso in cui 'ja' e 'da' sono le uniche risposte che un dio può dare. È anche possibile che un dio non sia capace di rispondere. Per esempio, se la domanda "Risponderai a questa domanda con la parola che significa "no" nella tua lingua?" viene posta a Vero, egli non può rispondere sinceramente. (Il giornale lo rappresenta mostrando la sua testa che esplode, "...sono dèi infallibili! Hanno solo una possibilità a cui ricorrere –le loro teste esplodono") Permettere il caso delle teste che esplodono dà un'altra soluzione all'indovinello modificato (modificato in modo che Casuale sia effettivamente casuale) e introduce la possibilità di risolvere l'indovinello originale (non modificato) con sole due domande invece che con tre. Supportando una soluzione di due sole domande, gli autori risolvono un simile indovinello più semplice utilizzando soltanto due domande.

• Tre dèi A, B e C sono chiamati, in un certo ordine, Zefiro, Euro ed Eolo. Gli dèi dicono sempre la verità. Il tuo compito è determinare l'identità di A, B e C ponendo tre domande del tipo sì/no; ogni domanda essere posta esattamente a un dio. Gli dei capiscono l'inglese e risponderanno in inglese.

Si noti che questo indovinello si risolve con tre domande. Per risolverlo con due si prova il seguente lemma.

Lemma del bugiardo temperato. Se si chiede ad A "È questo il caso in cui {[(risponderai 'no' a questa domanda) E (B è Zefiro)] O (B è Euro) }?", la risposta 'sì' indica che B è Euro, la risposta 'no' indica che B è Eolo, e una testa che esplode indica che B è Zefiro. Da qui si può determinare l'identità di B con una sola domanda.

Usando questo lemma è semplice risolvere l'indovinello in due domande. Un trucco simile (paradosso del bugiardo) si può utilizzare per risolvere l'indovinello originale con due domande.

Bibliografia

• T. S. Roberts, Some Thoughts About The Hardest Logic Puzzle Ever (Journal of Philosophical Logic 30:609–612(4), December 2001).
• Brian Rabern and Landon Rabern, A Simple Solution to the Hardest Logic Puzzle Ever (Analysis, 68.2, April 2008).
• Raymond Smullyan, What is the Name of This Book? (Prentice Hall, Englewood Cliffs, NJ, 1978).
• Raymond Smullyan, The Riddle of Sheherazade (A. A. Knopf, Inc., New York, 1997).

Voci correlate

• Cavalieri e furfanti
• Indovinello logico

Collegamenti esterni

• George Boolos. The hardest logic puzzle ever. The Harvard Review of Philosophy, 6:62–65, 1996. (PDF), su hcs.harvard.edu. URL consultato il 18 febbraio 2008 (archiviato dall'url originale il 22 giugno 2012).
• Roberts T.S. Some thoughts about the hardest logic puzzle ever. Journal of Philosophical Logic, 30:609–612(4), December 2001. , su springerlink.com.
• An illustration of the puzzle, su philosophy.hku.hk.