?

Log in

No account? Create an account

Предыдущий пост Поделиться Следующий пост
Парадокс голубоглазых островитян (часть 2)
lex_kravetski


Первая часть

…в общем, это — прекрасное решение прекрасной задачи.

Жаль, что оно неверное.


Но как?!



Постойте, я же только что расписал это решение во всех деталях, да и на других сайтах описывается оно же. Что тут не так?

Да, относительно этого сложного процесса нас тоже немного гложут сомнения, но тут ведь как с квантовой механикой: «заткнись и считай». Рекурсия сложна для понимания, но работает!

Вы знаете, особое изящество этой задачи мне видится в том, что рекурсия тут действительно работает. Причём на первых итерациях она даже интуитивно понятна, а на более поздних рождает щекочущее нервы чувство чудесной научной мистики, поэтому прямо-таки хочется поверить, что тут всё верно, ты только что понял что-то очень нетривиальное, а те, кто продолжает с ним спорить, просто «не догоняют» всей этой логической крутизны.

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

Иными словами, изящество этого «парадокса» в том, как здорово в нём замаскированы несколько очень суровых натяжек — внутри весьма изощрённого и «технологичного» решения.

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


Спасительное противоречие



Дело в том, что в решении задачи игнорируется одно из её условий: у туземцев есть запрет на то, чтобы сообщать другим о цвете их глаз. Причём из контекста понятно, что имеется в виду не только «говорить», но и сообщать иным способом — рисовать на картинке, неожиданно показывать зеркальце или давать некий ребус, решение которого идеально логичным (это тоже есть в условии) туземцем привело бы к вычислению им собственного цвета глаз.

Так вот, в описанной ситуации туземцы совершенно точно дают друг другу такой ребус — ведь на этом построено всё решение со всей его рекурсией: их действия или бездействия приводят к тому, что в конечном счёте вообще все узнаю́т, какого цвета у них глаза.

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

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

Если же эти правила не отменены, то в описанном случае им невозможно следовать, ведь хотя бы одно из них будет нарушено.


Вариант с неопределённостью



Условия задачи не сообщают нам, какие именно приоритеты у туземцев. Вполне возможно, что каждый из них счёл бы, что лучше нарушить одно правило, чем два: не самоубиться, узнав цвет своих глаз, но зато и не сообщить другим о цвете их глаз. Ведь альтернатива тому — нарушить правило о знании цвета своих глаз, выполнить правило о самоубийстве, и тем самым нарушить правило о несообщении.

Если же приоритеты были никак не оговорены, то ни один туземец не может наверняка знать, какой вариант выберет другой туземец, а потому не может однозначно вычислить цвет своих глаз.

Даже единственный голубоглазый на острове мог бы счесть, что важнее не сообщать другим цвет их глаз, чем самоубиться после вычисления своей голубоглазости.

Однако, быть может, у туземцев всё-таки есть какие-то уточнения по этому поводу? Например, приоритет правил друг перед другом.


А, кстати, насколько они честны?



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

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

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

Одновременно с тем есть правило не сообщать никому цвет его глаз.

Если возможен обман, то это правило теряет смысл — ведь сообщение цвета ни к чему не приведёт. Даже изображение в зеркале можно подделать, не говоря уже про устные сообщения.

Это подводит к мысли, что туземцы могут сообщать только правду, и все поголовно знают, что все остальные сообщают только правду.


Варианты с честными островитянами



Итак, из условий задачи косвенно следует, что островитяне не только идеально логичны, но ещё и абсолютно честны.

Именно для этого случая мы и будем рассматривать варианты с приоритетами правил. Тут в каждом пункте они перечислены в порядке убывания их приоритета.

  1. Не сообщать другим цвет их глаз; самоубиться, если узнал свой; не знать цвет своих глаз.


  2. Не сообщать; не знать; самоубиться.


  3. Не знать; не сообщать; самоубиться.


  4. Самоубиться; не сообщать; не знать.


  5. Не знать; самоубиться; не сообщать.


  6. Самоубиться; не знать; не сообщать.



Не сообщать другим цвет глаз важнее, чем самоубиться, если узнал



Варианты 1, 2, 3.

В этом случае даже при наличии одного туземца процесс не пойдёт дальше — он не будет самоубиваться, чтобы не нарушить более важное правило о несообщении другим цвета их глаз, из-за чего не будет работать и вышеописанная рекурсия.

Все выживут.


Не знать свой цвет глаз важнее, чем не сообщать его другим



Варианты 4, 5, 6.

Поскольку самубийство следует только после узнавания цвета своих глаз, в данном случае без разницы, в каком порядке эти два правила расставлены по приоритетам друг относительно друга. Следовательно, мы можем рассматривать всё это как единый случай.

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

Однако, если голубоглазых больше одного, то ситуация уже меняется. Ведь если не знать цвет своих глаз важнее, то следует сказать кому-то о цвете его глаз, если это позволит не узнать цвет своих.

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

Следовательно, надо об этом сказать голубоглазому.

Даже если такой всего один, то всё равно уже никто не может быть уверен, покончил ли он с собой из-за того, что ему сообщили о цвете глаз, или же потому, что он его вычислил (а, значит, рекурсивный метод — в деле, и все остальные тоже автоматически вычислят свой цвет глаз).

Причём, каждый конкретный островитянин, в принципе, может даже не сообщать об этом самостоятельно — достаточно уже возможности того, что голубоглазому о цвете его глаз сообщил кто-то другой: в этом уже есть достаточная для невозможности вычисления своего цвета глаз всеми остальными неопределённость.

Однако тут есть тонкость: если единственный хотя бы один голубоглазый не самоубился, то, значит, ему не сообщили о цвете его глаз. А раз так, то рекурсивное вычисление всё ещё возможно.

Поэтому в данной ситуации с неизбежностью должен покончить с собой хотя бы один голубоглазый, чтобы рекурсивный процесс застопорился.

Что касается кареглазых, то для них ситуация идеальна — сколько бы ни было голубоглазых, кареглазым точно не сообщат о том, что они — кареглазые, поскольку это никак не поможет избежать вычисления цвета своих глаз, но при этом у них не будет уверенности, потому ли им не сообщили, что они — кареглазые, или потому, что они голубоглазые, которым повезло.

Иными словами, в данном случае, в зависимости от везения, самоубьётся минимум один голубоглазый, но вот все кареглазые и те голубоглазые, которым повезло, выживут.

При наличии человеколюбия у туземцев, вообще говоря, они должны догадаться, что тот, кто видит нескольких голубоглазых, должен при всех сказать одному из них: «ты — голубоглазый», а остальные должны промолчать — это сведёт количество жертв к возможному минимуму — одной.


Важность определённости приоритетов



Как можно видеть по вышеприведённым рассуждениям, от ответа на вопрос о приоритетах зависит исход ситуации.

Если приоритеты не определены, то, в зависимости от личных предпочтений, возможно, что не самоубьётся даже единственный на острове голубоглазый. Или же единственный голубоглазый самоубьётся, но остальные не будут знать, это потому, что он — единственный, или потому, что кто-то счёл более правильным вариантом неизбежного нарушения традиций сообщить единственному голубоглазому, что он — голубоглазый. Если же голубоглазых больше одного, то никто ни в чём не уверен, а потому выживут все.

Если не сообщать другим цвет их глаз важнее, чем самоубиться, если его ты узнал, то выживут все.

Если не знать свой цвет глаз важнее, чем не сообщать его другим, то, в зависимости от везения, самоубьётся от одного до полного количества голубоглазых, но все кареглазые выживут.

Задача имеет разные решения, в зависимости от тех условий, о деталях которых умолчали: как правила по своей важности соотносятся друг с другом.


А что если запрета на раскрытие цвета глаз другого нет?



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

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

Минимум один туземец умрёт, но, возможно, этим дело и кончится. Кареглазые же однозначно выживут.


Изворачиваемся с условиями



В общем-то, понятно, что хотели сказать авторы задачи. Что-то типа: «островитяне не могут сообщать другим цвет их глаз, кроме как вот этими вот своими самоубийствами».

Эта формулировка выглядит крайне натянутой, однако рекурсивное решение приводит к вымиранию всего острова только с ней — такой вот натянутой.

Или не приводит?



doc-файл



Первая часть в блоге автора
Первая часть на сайте «XX2 Век»



Вторая часть в блоге автора
Вторая часть на сайте «XX2 Век»



Третья часть в блоге автора
Третья часть на сайте «XX2 Век»



  • 1
Вот это логический поворот!
В таком направлении даже и не начинал думать.

И опять продолжение в следующей серии, ну что такое :(

А можно ещё раз объяснить, как получается, что идеально логичные островитяне (при количестве голубоглазых три и больше) предполагают, что кто-то из них узнал о наличии голубоглазых на острове только после речи путешественника? Что-то я это в прошлый раз не смог понять.

Слова путешественника -- необходимое условие для базы

Индуктивное решение:
1. База индукции: Если есть ровно 1 абориген -- то через 1 день он обязан покончить с собой, если не видит других голубоглазых (док-ся из слов путешественника, что голубоглазые есть).
2. Шаг индукции: Если есть N+1 аборигенов -- то через N+1 дней они обязаны коллективно покончить с собой (док-ся от противного: раз я вижу N абоигенов не покончивших с собой за N дней -- то я голубоглазый).


Так вот пункт "1" база индукции -- валидна только после слов путешественника.

А почему на пункте 1 этот единственный не может решить "соврал собака - нет у нас никаких голубоглазых"

Они не это предполагают.

Каждый из них строит модели других островитян, а затем строит модели, которые построили бы эти другие, а затем строит модели, которые построили бы эти модели других - и так далее.

Назовём меня X0.
Я вижу 19 голубоглазых. Беру любого из них. Называю его X1. Предполагаю, что я сам кареглазый. И строю X1-рассуждение. Как бы думал X1?

А он бы видел 18 голубоглазых. Выбрал бы из них X2. Предположил бы, что сам он кареглазый. И построил бы X2-рассуждение - как бы в этом случае думал X2?
А он бы видел 17 голубоглазых. Выбрал бы из них X3. Предположил бы, что сам он кареглазый. И построил бы X3-рассуждение - как бы в этом случае думал X3?

Обратите внимание. X3-рассуждение строит не реальный X3, не реальный X2 и не реальный X1. Его строю всё ещё я, X0. Я моделирую X1, который моделирует X2, который моделирует X3 - и так далее. И от шага к шагу количество голубоглазых уменьшается.

И так я дошёл бы до X19, который существует в представлении X18 и который голубоглазых не видит вообще. Вот тут оно бы и выстрелило. Если X19 голубоглазых не видит, а в общем знании информация о том, что они есть, не присутствует - то X19 не сделает никаких выводов. А если присутствует - то сделает, а значит, их сделает и X18, и X17, и так далее - до X1. И если поведение прототипа X1 будет отличаться от поведения X1 в моей голове - значит, моё исходное предположение было неверным, и я таки не кареглазый.

То есть если на 19-й день все голубоглазые, которых я вижу, не выпилились - на 20-й день мы с ними выпиливаемся хором.




А почему это ты решил, что ты кареглазый? Ты должен рассмотреть оба варианта. И тогда на втором шаге рекурсия стопорится.
Х0 не может достоверно знать 19 или 18 голубоглазых видит Х1, а значит предположения о том, что там мог бы думать Х2 не имеют никакого смыла, это всего лишь один из возможных вариантов.

И вообще, утверждать, что человек с идеально логическим мышлением видит 19 голубоглазых, но предполагает, что кто-то видит 17, это как-то слишком сурово.

островитяне должны были убить путешественника за нарушение табу.

Просто надо более строго переформулировать задачу.

Не в терминах "туземцев", а в терминах "теории игр".
Чтобы при наличии нескольких индивидуальных стратегий было понятно -- на какую коллективную стратегию должен рассчитывать каждый игрок.

ПС1:
Кстати если сфомулировать задачу о мудрецах -- то обычно решение из 1й части валидно (мы можем применять кооперативную коллективную стратегию -- поскольку можем рассчитывать на то, что другие мудрецы тоже стремятся быть кооперативными)

ПС2:
https://lex-kravetski.livejournal.com/599784.html?thread=75967976#t75967976

Edited at 2018-06-05 16:04 (UTC)

Re: Просто надо более строго переформулировать задачу.

> Кстати если сфомулировать задачу о мудрецах -- то обычно решение из 1й части валидно (мы можем применять кооперативную коллективную стратегию -- поскольку можем рассчитывать на то, что другие мудрецы тоже стремятся быть кооперативными)

Про ошибку в самой рекурсии будет в третьей части. И там, кстати, и о мудрецах тоже.

Красивое решение. Если, конечно, рассматривать задачу как задачу о туземцах.

Кстати, Лекс, читал вот это?

Edited at 2018-06-05 17:30 (UTC)

> Кстати, Лекс, читал вот это?

В числе прочего, когда пытался выяснить, нашёл ли хоть кто-то, кроме меня, хотя бы одну реальную ошибку в этом решении.

Насчёт "не сообщать цвет глаз любым методом" - нет, из контекста условия это неочевидно (по крайней мере, мне), там сказано только "не говорить". Мало того: при решении задачи всегда предполагается непротиворечивость условия, а из этого следует, что косвенно сообщать цвет глаз как раз можно.

> При наличии человеколюбия у туземцев, вообще говоря, они должны догадаться, что тот, кто видит нескольких голубоглазых, должен при всех сказать одному из них: «ты — голубоглазый», а остальные должны промолчать — это сведёт количество жертв к возможному минимуму — одной.

С идеальным логическим мышлением тут проблема: как определить, кто должен сказать, а кто молчать? Если выбрать какое-нибудь правило - например, "говорит самый высокий островитянин", то если он окажется единственным голубоглазым и промолчит, то все остальные узнают, что они кареглазые. Даже если сообщение цвета глаз сделать тайным, это не поможет: если все знают, кто должен указать на голубоглазого, и этот избранный (например, самый высокий) на следующий день самоубивается, значит, все остальные кареглазые. Так что вариант с самым высоким (или любым другим известным) не подходит. Никто не должен знать, кто же должен сообщить голубоглазому цвет глаз: и этот жребий должен быть тайным, и сообщение голубоглазому цвета глаз - тоже тайным. По крайней мере, я других вариантов не вижу.

> В общем-то, понятно, что хотели сказать авторы задачи. Что-то типа: «островитяне не могут сообщать другим цвет их глаз, кроме как вот этими вот своими самоубийствами».

Я вообще не понимаю, откуда взялось условие "не могут сообщать другим цвет их глаз" и зачем оно нужно. Оно делает условие задачи противоречивым, а это совсем плохо для логической задачи. Что мешает просто убрать его?

> Насчёт "не сообщать цвет глаз любым методом" - нет, из контекста условия это неочевидно (по крайней мере, мне), там сказано только "не говорить".

> С идеальным логическим мышлением тут проблема: как определить, кто должен сказать, а кто молчать?

> Я вообще не понимаю, откуда взялось условие "не могут сообщать другим цвет их глаз" и зачем оно нужно.

Наверно имеет смысл читать статью перед комментированием.

Мне было бы трудно взять цитаты из разных частей статьи и аргументированно возразить на их, не читая статью.
Если же вы не осилили мой коммент (может, я невнятно написал), повторю другими словами.

1. Формально условие непротиворечиво. Противоречие появляется только если "не говорить" превратить в "не сообщать любым способом". Но это как раз говорит о том, что такое превращение делать не следует.

2. Для вариантов 4,5,6 вы не предложили, кто именно из тех, кто видит нескольких голубоглазых, должен сообщить одному из них цвет глаз. Проблема в том, что любое правило, определяющее, кто должен сказать цвет глаз, приводит к смерти всех островитян. Так что предложенный вами вариант ошибочен (в отличие от варианта, предложенного мной в комментарии к первой части).

3. Вы пишете:
> В общем-то, понятно, что хотели сказать авторы задачи. Что-то типа: «островитяне не могут сообщать другим цвет их глаз, кроме как вот этими вот своими самоубийствами».

Справедливо замечая, что такая формулировка получается натянутой. Я не понимаю причин этого условия, а потому не считаю, что они хотели сказать именно так. Ведь непосредственно перед этим вы совершенно справедливо показали, что без него задача нисколько не теряет своей привлекательности (правда, и там ошиблись, написав "минимум один" вместо "ровно один"). Если вы считаете, что авторы задачи хотели сказать именно так, то, наверное, понимаете, почему они хотели так сказать. Можете ли объяснить смысл этого условия (с точки зрения авторов задачи или вообще)?

Я такие длинные логические цепочки в голове не умею строить, но мне вот чота не понятно - а кто первый себя убьёт?

Я там выше дал несколько корявый, непродуманный, и, в результате, неправильный ответ. Напишу-ка более осмысленно. Рекурсия тормозится на третьем шаге, то есть не работает, если аборигенов больше 3. Нужен один рассуждающий и по одному на каждый шаг.

Рассуждает абориген-0:
1 шаг. Я (0) вижу 19 голубоглазых, значит 1 видит, или 19, или 18. Если 18, то идет второй шаг
2 шаг. Я (0) думаю, что 1 видит 18 голубоглазых, и считает, что 2 видит, или 18, или 17. Если 17, то идет третий шаг.
3 шаг. Я (0) думаю, что 1 думает, что 2 видит 17 голубоглазых, и считает, что 3 видит, или 17, или 16. Если 16, то идет четвертый шаг.

Напоминаю, все рассуждения ведет один абориген, о рассуждениях остальных он делает предположения. На первом шаге никаких вопросов. На втором идут гипотетические рассуждения 1. Но 0 понимает, что вариант «или 17» неверен. Конечно, 1 пока этого не понимает, потому продолжаем. На третьем идут гипотетические рассуждения 2, в представлении 1. И 1, в свою очередь, должен будет понять, что вариант «или 16» неверен. А значит 0 понимает, что любой другой абориген двигаясь тем же путем, на том же шаге понимает то же самое. Таким образом, очевидно, что никто ни в каких рассуждениях не может предполагать наличие аборигена, видящего меньше 17 голубоглазых.

Да, странная задачка. Вроде рекурсия логична, но все равно непонятно, почему известный всем жителям факт, после озвучивания заставляет всех считать его некой точкой отсчета.
Может в рекурсии ошибка в том, что строится она на первой итерации, где сказанное путешествеником действительно имеет смысл, так как "открывает глаза" единственному голубоглазому. Но когда голубоглазых много, смысла в первой итерации нет, так как все и так знают что в деревне полно голубоглазых.
И, кстати, что если кто-то будет ежедневно собирать людей и объявлять им о наличии голубоглазых, будет ли процесс самовыпиливания откладываться?

Еще раз перечитал статью и предлагаю такое решение для случая, где голубоглазых больше трех. После размышлений над рагу из европейца, самый умный абориген встает и говорит:
Товарищи людоеды! Мы попали в логическую ловушку. Если следовать рекурсивной логике, то через некоторое время мы все умрем. Парадокс в том, что наличие или отсутствие массового суицида на определенный день дает нам информацию о цвете своих глаз. Соответственно, предлагаю отказаться от рекурсивной логики, и исходить из того, что на данный момент никто не знает цвета своих глаз и если никто не совершит суицид, то никто и не узнает цвета своих глаз. Не станем нарушать табу, и продолжим жить как прежде.

  • 1