Самая сложная логическая головоломка на свете

«Самая сложная логическая головоломка на свете» — это логическая головоломка , названная американским философом и логиком Джорджем Булосом и опубликованная в «Гарвардском обзоре философии» в 1996 году. Статья Булоса предлагает несколько способов решения проблемы. Перевод на итальянский язык был опубликован ранее в газете La Repubblica под названием L'indovinello più difficile del mondo .

Об этом говорится следующим образом:

Три бога A, B и C называются (в произвольном порядке): Истинный, Ложный и Случайный. Правда всегда говорит правду, Ложь всегда говорит ложь, но говорит ли Случайный правду или ложь — это совершенно случайный вопрос. Ваша задача — определить личности A, B и C, задав три вопроса типа «да-нет» ; каждый вопрос должен быть задан ровно одному богу. Боги понимают английский, но ответят на все вопросы на своем языке, на котором слова « да» и «нет» — да и джа . в каком-то порядке. Вы не знаете, какое слово что означает.

Булос дает следующие разъяснения: одному богу можно задать более одного вопроса, вопросы могут зависеть от ответов на предыдущие вопросы, а характер ответа Рэндома следует рассматривать как зависящий от подбрасывания честной монеты, спрятанной в его мозгу: если монета опускает головы, он говорит правду; если решка, то ложно.

История

логик Рэймонд Смаллян Булос считает, что автором головоломки был , а Джон Маккарти добавил, что сложность незнания того, что означают да и джа , усугубляется . Соответствующие загадки можно найти во всех произведениях Смалляна. Например, в «Как называется эта книга?» , он описывает гаитянский остров, половина жителей которого — зомби (которые всегда лгут), а половина — люди (которые всегда говорят правду). Он объясняет, что «ситуация чрезвычайно осложняется тем фактом, что, хотя все туземцы прекрасно понимают английский язык, древнее табу острова запрещает им когда-либо использовать в своей речи неродные слова. Поэтому всякий раз, когда вы задаете им вопрос «да-нет», — отвечают они «Бал» или «Джа», — один из них означает «да» , а другой — « нет » . Проблема в том, что мы не знаем, что из «Бал» или «Да» означает «да» , а что — « нет». есть и другие похожие головоломки В «Загадке Шахерезады» .

Головоломка основана на головоломках о рыцарях и валетах . Одним из мест действия этой головоломки является вымышленный остров, населенный только рыцарями и мошенниками, где рыцари всегда говорят правду, а мошенники всегда лгут. Посетитель острова должен задать ряд вопросов типа «да/нет», чтобы узнать то, что ему нужно знать (особенности которых различаются в разных версиях головоломки). Одна из версий этих головоломок была популяризирована сценой из фантастического фильма 1986 года «Лабиринт» . Есть две двери, в каждой по одному охраннику. Один охранник всегда лжет, а другой всегда отвечает правду. Одна дверь ведет в замок, а другая — к «верной смерти». Загадка состоит в том, чтобы узнать, какая дверь ведет в замок, задав одному из охранников один вопрос. В фильме главный герой делает это, спрашивая: «Скажет ли он [другой охранник] мне, что эта дверь ведет в замок?»

Решение

Булос предложил свое решение в той же статье, в которой представил загадку. Булос утверждает, что «первый шаг — найти бога, который, как вы можете быть уверены, не является случайным и, следовательно, является либо истинным, либо ложным». Есть много разных вопросов, которые позволят добиться такого результата. Одна из стратегий — использовать в вопросах сложные логические связки (либо двуусловные , либо эквивалентные конструкции).

Вопрос Булоса заключался в том, чтобы спросить А:

Означает ли « да» тогда и только тогда, когда вы истинны, тогда и только тогда, когда B является случайным?

Эквивалентно:

Верны ли нечетное количество следующих утверждений: da означает «да» , вы правы, B — случайное?

Робертс (2001) и независимо Раберн и Раберн (2008) заметили, что решение головоломки можно упростить, используя определенные контрфакты . Ключом к этому решению является то, что для любого вопроса Q, дающего/нет, задается вопрос «Верно» или «Неверно».

Если бы я спросил тебя: «Вопрос», ты бы ответил: «Да» ?

приводит к ответу ja, если правдивый ответ на Q — да , и ответу da, если правдивый ответ на Q — нет (Раберн и Раберн (2008) называют этот результат леммой встроенного вопроса). Причину, по которой это работает, можно увидеть, изучив логическую форму ожидаемого ответа на вопрос. Эта логическая форма ( логическое выражение ) развивается ниже (« Q» истинно, если ответ на Q «да», « Бог» истинно, если бог, которому задается вопрос, действует как говорящий правду и «Ja верно , если значение Ja — «да»):

1. То, как бог решит ответить на вопрос Q, определяется отрицанием исключительного разделения между Q и Богом (если ответ на вопрос Q и природа бога противоположны, ответ, данный богом, обязательно будет «нет», а если они одинаковы, то обязательно будет «да»)):
   • ¬ ( Q ⊕ Бог)
2. Будет ли ответ, данный богом, Джа или нет, снова определяется отрицанием исключительного дизъюнкции между предыдущим результатом и Джа.
   • ¬ ( ( ¬ ( Q ⊕ Хорошо)) ⊕ Да )
3. Результат второго шага дает правдивый ответ на вопрос: «Если я задам вам вопрос, вы ответите да?» Какой ответ даст Бог, можно выяснить, используя рассуждения, аналогичные тем, которые использовались в шаге 1.
   • ¬ ( ( ¬ ( ( ¬ ( Q ⊕ Хорошо)) ⊕ Да )) ⊕ Хорошо )
4. Наконец, чтобы узнать, будет ли этот ответ Ja или Da (еще одно) отрицание исключительной дизъюнкции Ja , потребуется с результатом шага 3.
   • ¬ ( ( ¬ ( ( ¬ ( ( ¬ ( Q ⊕ Хорошо)) ⊕ Да ) ) ⊕ Хорошо )) ⊕ Да )

Это последнее выражение имеет значение true, если ответ — Ja , и false в противном случае. Ниже рассмотрены восемь случаев (1 соответствует истине, а 0 ложь):

вопрос Верно, если ответить на Вопрос — «да»	Бог Правда, если бог ведет себя как говорящий правду	И Верно, если значение Джа это "да"	Шаг 1 (Ответ Бога на вопрос)	Шаг 2 (Это Джа ?)	Шаг 3 (Божий ответ на контрфактическое)	Шаг 4 (Это Джа ?)
0	0	0	1	0	1	0
0	0	1	1	1	0	0
0	1	0	0	1	1	0
0	1	1	0	0	0	0
1	0	0	0	1	0	1
1	0	1	0	0	1	1
1	1	0	1	0	0	1
1	1	1	1	1	1	1

Сравнивая первый и последний столбцы, становится ясно, что ответ « Да» только в том случае, если ответ на вопрос «да». Те же результаты применимы, если бы вместо этого был задан вопрос: «Если бы я спросил вас «Q», вы бы ответили «Да»? потому что оценка контрфактического не зависит поверхностно от значений Джа и Да. Каждый из восьми случаев эквивалентно поясняется ниже словами:

• Предположим, что ja означает «да» , а da — «нет» .

1. True спрашивается и отвечает ja . Поскольку он говорит правду, правдивый ответ на вопрос — ja , что означает «да» .
2. True спрашивается и отвечает da . Поскольку он говорит правду, правдивый ответ на вопрос Q — да , что означает «нет» .
3. False задается и отвечает ja . Поскольку он лжет, из этого следует, что если бы вы спросили его Q, он вместо этого ответил бы da . Он бы солгал, поэтому правдивый ответ на вопрос — ja , что означает «да» .
4. False задается и отвечает da . Поскольку он лжет, отсюда следует, что если бы вы спросили его Q, он на самом деле ответил бы ja . Он бы солгал, поэтому правдивый ответ на вопрос — да , что означает «нет» .

• Предположим, что ja означает «нет» , а da означает «да» .

1. True спрашивается и отвечает ja . Поскольку он говорит правду, правдивый ответ на вопрос Q — да , что означает «да» .
2. True спрашивается и отвечает da . Поскольку он говорит правду, правдивый ответ на вопрос — ja , что означает «нет» .
3. False задается и отвечает ja . Поскольку он лжет, из этого следует, что если бы вы спросили его Q, он на самом деле ответил бы ja . Он бы солгал, поэтому правдивый ответ на вопрос — да , что означает да .
4. False задается и отвечает da . Поскольку он лжет, из этого следует, что если бы вы спросили его Q, он вместо этого ответил бы da . Он бы солгал, поэтому правдивый ответ на вопрос — ja , что означает «нет».

Независимо от того, лжет ли спрошенный бог или нет, и независимо от того, какое слово означает «да» , а какое « нет» , вы можете определить, будет ли правдивый ответ на вопрос « да» или «нет» .

Приведенное ниже решение строит три вопроса с использованием леммы, описанной выше.

Вопрос 1: Спросите бога Б: «Если бы я спросил вас: «Случайно ли это?», вы бы ответили «да ?». Если B отвечает ja , либо B является случайным (и отвечает случайным образом), либо B не является случайным, и ответ указывает, что A действительно случайный. В любом случае, C не является случайным. Если B отвечает da , либо B является случайным (и отвечает случайным образом), либо B не является случайным, и ответ указывает, что A не является случайным. В любом случае, вы знаете личность бога, который не является Рэндомом.

Вопрос 2: Подойдите к богу, который был идентифицирован как не случайный по предыдущему вопросу (либо A, либо C), и спросите его: «Если бы я спросил тебя: «Ты лжец?», ты бы ответил « да ?». Поскольку он не является случайным, ответ da указывает, что он истинен, а ответ ja указывает, что он ложен.

Вопрос 3: Задайте тому же богу вопрос: «Если бы я спросил вас: «Случайно ли B?», вы бы ответили « да ?». Если ответ ja , B является случайным; если ответ да , то бог, с которым вы еще не разговаривали, является Случайным. Оставшегося бога можно определить методом исключения.

Случай		1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16
А		Истинный	Истинный		ЛОЖЬ	Случайный	ЛОЖЬ		Случайный	Истинный	Истинный		ЛОЖЬ	Случайный	ЛОЖЬ		Случайный
Б		ЛОЖЬ	Случайный		Истинный	Истинный	Случайный		ЛОЖЬ	ЛОЖЬ	Случайный		Истинный	Истинный	Случайный		ЛОЖЬ
С		Случайный	ЛОЖЬ		Случайный	ЛОЖЬ	Истинный		Истинный	Случайный	ЛОЖЬ		Случайный	ЛОЖЬ	Истинный		Истинный
И		Да	Да		Да	Да	Да		Да	Нет	Нет		Нет	Нет	Нет		Нет
И		Нет	Нет		Нет	Нет	Нет		Нет	Да	Да		Да	Да	Да		Да
Действительно ли A случайно?		Нет	Нет		Нет	Да	Нет		Да	Нет	Нет		Нет	Да	Нет		Да
Как бы Б ответил на вопрос «Случайно ли?»	Английский	Да	Или		Нет	Да	Или		Нет	Да	Или		Нет	Да	Или		Нет
	Их язык	И	Или		И	И	Или		И	И	Или		И	И	Или		И
Ответ Б на вопрос 1: «Если бы я спросил вас: «Это случайное явление», вы бы ответили «да ?»	Английский	Да	Или		Да	Нет	Или		Нет	Нет	Или		Нет	Да	Или		Да
	Их язык	И	Или		И	И	Или		И	И	Или		И	И	Или		И
			И	И			И	И			И	И			И	И
Таким образом, __ (далее X) не является случайным.		А	А	С	А	С	А	С	С	А	А	С	А	С	А	С	С
Действительно ли X ложно?		Нет	Нет	Да	Да	Да	Да	Нет	Нет	Нет	Нет	Да	Да	Да	Да	Нет	Нет
Как бы X ответил на вопрос: «Вы неправы?»	Английский	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет	Нет
	Их язык	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И
Ответ X на вопрос 2: «Если бы я спросил вас: «Вы неправы?», вы бы ответили «да ?»	Английский	Да	Да	Нет	Нет	Нет	Нет	Да	Да	Нет	Нет	Да	Да	Да	Да	Нет	Нет
	Их язык	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И
Таким образом, X — это __.		Истинный	Истинный	ЛОЖЬ	ЛОЖЬ	ЛОЖЬ	ЛОЖЬ	Истинный	Истинный	Истинный	Истинный	ЛОЖЬ	ЛОЖЬ	ЛОЖЬ	ЛОЖЬ	Истинный	Истинный
Действительно ли B является случайным?		Нет	Да		Нет	Нет	Да		Нет	Нет	Да		Нет	Нет	Да		Нет
Как бы X ответил на вопрос «Случайно ли B?»	Английский	Нет	Да	Нет	Да	Да	Нет	Да	Нет	Нет	Да	Нет	Да	Да	Нет	Да	Нет
	Их язык	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И
Ответ X на вопрос 3: «Если бы я спросил вас: «Случайно ли B?», вы бы ответили «да ?»	Английский	Да	Нет	Нет	Да	Да	Нет	Нет	Да	Нет	Да	Да	Нет	Нет	Да	Да	Нет
	Их язык	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И	И
Таким образом, __ является случайным.		С	Б	Б	С	А	Б	Б	А	С	Б	Б	С	А	Б	Б	А
Таким образом, методом исключения (Буква) становится (Имя).	Письмо	Б	С	А	Б	Б	С	А	Б	Б	С	А	Б	Б	С	А	Б
	Имя	ЛОЖЬ	ЛОЖЬ	Истинный	Истинный	Истинный	Истинный	ЛОЖЬ	ЛОЖЬ	ЛОЖЬ	ЛОЖЬ	Истинный	Истинный	Истинный	Истинный	ЛОЖЬ	ЛОЖЬ

Поведение Рэндома

Третье поясняющее замечание Булоса объясняет поведение Рэндома следующим образом:

Говорит ли Рэндом правду или нет, следует думать, что это зависит от подбрасывания монеты, спрятанной в его мозгу: если монета выпадает орлом, он говорит правду; если решка, то ложно.

Здесь не указывается, производится ли подбрасывание монеты для каждого вопроса или для каждого «сеанса», то есть для всей серии вопросов. Если интерпретировать это как одиночный случайный выбор, который длится на протяжении всего сеанса, Раберн и Раберн показывают, что полезные ответы можно извлечь даже из случайного выбора; это потому, что контрфактическое утверждение было разработано таким образом, что независимо от того, был ли ответчик (в данном случае Рэндом) говорящим правду или лжецом, правдивый ответ на вопрос Q был бы ясен.

Другая возможная интерпретация поведения Рэндома, когда он сталкивается с контрфактом, заключается в том, что он отвечает на вопрос полностью после подбрасывания монеты в своей голове, но находит ответ на Q в своем предыдущем состоянии ума, пока вопрос задается. Опять же, это делает бесполезным спрашивать Рэндома об обратном. Если это так, небольшое изменение в вопросе выше дает вопрос, который всегда будет вызывать содержательный ответ от Рэндома. Изменение заключается в следующем:

Если бы я задал вам вопрос в вашем нынешнем психическом состоянии , вы бы ответили «да» ?

Это эффективно выделяет из Рэндома личностей, говорящих правду, и лжецов, и заставляет его быть только одним из них. При этом загадка становится совершенно тривиальной, то есть можно легко получить правдивые ответы. Однако предполагается, что Рэндом решил солгать или сказать правду, прежде чем определить правильный ответ на вопрос – что-то, что не указано в загадке или уточняющем замечании.

Спросите бога А: «Если бы я спросил тебя: «Вы случайно?» в твоем нынешнем психическом состоянии ты бы сказал да ?"

1. Если А отвечает «да» , А — это случайно: спросите бога Б: «Если бы я спросил тебя: «Ты правда?», ты бы ответил «да ?»
   • Если B отвечает ja , B — правда, а C — ложь.
   • Если B отвечает da , B — ложь, а C — истина. В обоих случаях головоломка решена.
2. Если А отвечает да , А не является случайным: спросите бога А: «Если бы я спросил тебя: «Ты правда?», ты бы ответил да ?»
   • Если A отвечает ja , A истинно.
   • Если A отвечает da , A ложно.
3. Спросите бога А: «Если бы я спросил тебя: «Случайно ли В?», ты бы ответил « да ?»
   • Если A отвечает ja , B является случайным, а C является противоположностью A.
   • Если A отвечает da , C является случайным, а B — противоположностью A.

Можно элегантно получить правдивые ответы в ходе решения исходной задачи, как это пояснил Булос («если монета выпадает орлом, он говорит правду; если решка — ложно»), не полагаясь на какие-либо якобы невысказанные предположения, внеся дальнейшее изменение на вопрос:

Если бы я задал вам вопрос, и если бы вы ответили так же правдиво, как и на этот вопрос , вы бы сказали «да» ?

Здесь единственным предположением является то, что Рэндом, отвечая на вопрос , либо отвечает правдиво («говорит правдиво»), ИЛИ отвечает ложно («говорит ложно»), что явно является частью разъяснений Булоса. Таким образом, исходную немодифицированную задачу (с пояснениями Булоса) можно рассматривать как «Самую сложную логическую головоломку на свете» с самым элегантным и несложным на вид решением.

Раберн и Раберн (2008) предлагают внести поправку в исходную головоломку Булоса, чтобы случайность на самом деле была случайной. Изменение состоит в том, чтобы заменить третье поясняющее замечание Булоса следующим:

Вопрос о том, скажет ли Рэндом «джа» или «да», следует рассматривать как зависящий от подбрасывания монеты, спрятанной в его мозгу: если монета выпадает орлом, он говорит «да» ; если решка, он говорит да .

С этой модификацией решение головоломки требует более тщательного допроса бога, приведенного в верхней части раздела «Решение» .

Вопросы без ответа и взрывающиеся божества

В «Простом решении самой сложной логической головоломки » Б. Раберн и Л. Раберн предлагают вариант загадки: бог, столкнувшись с парадоксом, не скажет ни «джа» , ни «да» , а вместо этого вообще не ответит. Например, если на вопрос «Собираетесь ли вы ответить на этот вопрос словом, которое на вашем языке означает нет ?» установлено значение «Истина», он не может ответить правдиво. (В статье это представлено как взрыв его головы : «... они непогрешимые боги! У них есть только один выход – их головы взрываются».) Допущение случая «взрывающейся головы» дает еще одно решение загадки и открывает возможность решить головоломку (модифицированную и оригинальную) всего за два вопроса, а не за три. В поддержку решения головоломки из двух вопросов авторы решают аналогичную, более простую головоломку, используя всего два вопроса.

Трех богов A, B и C в определенном порядке называют Зефиром , Эвром и Эолом . Боги всегда говорят правду. Ваша задача — определить личности A, B и C, задавая вопросы типа «да-нет»; каждый вопрос должен быть задан ровно одному богу. Боги понимают английский и ответят на английском.

Обратите внимание, что эта головоломка тривиально решается с помощью трех вопросов. Кроме того, для решения задачи в двух вопросах следующая лемма доказывается .

Лемма о закаленном лжеце. Если мы спросим A: «Действительно ли {[(вы ответите «нет» на этот вопрос) И (B — Зефир)] ИЛИ (B — Эврус)}?», ответ «да» означает, что B — Эврус, ответ «нет» указывает на то, что B — Эол, а взрывающаяся голова указывает на то, что B — Зефир. Следовательно, мы можем определить личность B за один вопрос.

Используя эту лемму, несложно решить головоломку в двух вопросах. Раберн и Раберн (2008) используют аналогичный прием (смягчают парадокс лжеца), чтобы решить исходную головоломку всего за два вопроса. Узкиано (2010) использует эти методы, чтобы найти решение исправленной головоломки, состоящее из двух вопросов. В решении двух вопросов как для исходной, так и для измененной головоломки используется тот факт, что некоторые боги неспособны ответить на определенные вопросы. Ни Правда, ни Ложь не могут дать ответ на следующий вопрос.

Вы бы ответили так же, как Рэндом, на вопрос «Находится ли Душанбе в Киргизии ?»?

Поскольку измененный Рэндом отвечает действительно случайным образом, ни Правда, ни Ложь не могут предсказать, ответит ли Рэндом да или да на вопрос, находится ли Душанбе в Киргизии. Учитывая это невежество, они не смогут сказать правду или солгать – поэтому они будут хранить молчание. Однако у Рэндома, который несет случайную чепуху, не возникнет проблем с произнесением ни ja , ни da . Узкиано (2010) использует эту асимметрию, чтобы предложить решение модифицированной головоломки из двух вопросов. Тем не менее, можно предположить, что боги обладают «пророческой способностью предсказывать ответы Рэндома еще до того, как в мозгу Рэндома подбросится монета?» В этом случае решение из двух вопросов по-прежнему доступно с использованием самореферентных вопросов в стиле, использованном в Rabern and Rabern (2008).

Вы бы ответили ja на вопрос, ответили бы вы da на этот вопрос?

И здесь ни Правда, ни Ложь не могут ответить на этот вопрос, учитывая их приверженность говорить правду и лгать соответственно. Они вынуждены отвечать «да» на тот случай, если ответ, который они обязуются дать, будет «да» , а этого они не могут сделать. Как и раньше, их ждет взрыв головы. Напротив, Рэндом будет бездумно излагать свою чушь и случайно отвечать да или да . Узкиано (2010) также использует эту асимметрию, чтобы предложить решение модифицированной головоломки из двух вопросов. Однако собственная модификация головоломки Ускиано, которая устраняет эту асимметрию, позволяя Рэндому либо отвечать «джа», «да», либо хранить молчание, не может быть решена менее чем за три вопроса.

Внешние ссылки

• Ричард Уэбб. Три бога, три вопроса: самая сложная логическая головоломка. (New Scientist, том 216, выпуски 2896–2897, 22–29 декабря 2012 г., страницы 50–52.)
• Том Эллис. Даже сложнее, чем самая сложная логическая головоломка.
• Стефан Винтейн. Игра с Истиной.
• Уолтер Карниелли. Контрфакты, противоречия и самая сложная логическая головоломка в мире. Журнал Омния Люмина. (на португальском языке)
• Джейми Кондлифф. Самая сложная логическая головоломка (и как ее решить).
• Самая сложная логическая головоломка (страница Googlesites)