Здравый смысл и задача о разноцветных шляпах

[knop]

Моя (уже, как и я сам, бородатая) задачка-головоломка про 100 мудрецов, выстроенных в ряд с надетыми на них разноцветными шляпами, как недавно выяснилось, получила неожиданное продолжение, ставящее этот сюжет в один ряд с парадоксом Банаха-Тарского...

Вот вольный перевод на русский язык этого продолжения.
Рассмотрим такую вариацию этой задачи:

Comments

[spamsink]

Поскольку общее число последовательностей счетно

А оно счетно?

[knop]

Нет ;-)
Погрещности редактирования. Сначала хотел дать только "рационально-счетный" вариант, потом решил сообщить полный, а фразу убрать забыл. Теперь убрал.

[spamsink]

"(количество классов по-прежнему счетно!)" в последнем абзаце, видимо, тоже нужно убрать.

[knop]

О, точно!! Спасибо

[efimpp]

увы, для того чтобы вычислить класс последовательности, каждому мудрецу потребуется бесконечное время
палач же достигнет каждого N-го мудреца через конечное время N*K, таким образом каждый мудрец просто назовет один случайный цвет и будет казнен с вероятностю 1/C - где С - число цветов
таким образом бесконечное количество мудрецов все же будет казнено

[junipher_greene]

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

[efimpp]

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

[knop]

Дело в том, что по условию задачи каждый мудрец уже имеет охрененную "вычислительную мощность", недоступную современным компьютерам - а именно, сиюмоментно видит (и запоминает) вперед бесконечную последовательность значений. Я думаю, что если в computer science разрешить такой тип данных
и считать, что элементарные действия с данными такого типа (как минимум, лексикографическое сравнение двух таких массивов и сложение их в модулярной арифметике) выполняются за конечное время, то и все наши представления о вычислительной трудности задач будут несколько поколеблены... ;-)

[junipher_greene]

Спасибо вам, Константин, за эту бородатую задачу! До сих пор хорошо помню, как заработал за неё четыре очка - а ведь это было почти 12 лет назад.

[knop]

не хотите тряхнуть стариной и "заработать 4 очка" еще и на бесконечном варианте?

[rus4]

А я заработал 0! Один из немногих.

[rioman]

Костя, а классов разве не континуум будет?

[knop]

Тьфу, хрень написал. Да, именно это и ховут континуум. Ну и что?

[rioman]

Ничего. Это я торможу. Мне показалось, что ты устанавливаешь соответствие между мудрецами и классами.

[rioman]

> (количество классов по-прежнему счетно!)
Это ошибка, но не имеющая значения.

[57ded]

Хорошо :)
Ещё один забавный пример, иллюстрирующий сомнительность аксиомы выбора :)
Скажем, если потребовать вычислимости от последовательности, и чтобы мудрецы вместо себя поставили бы машины Тьюринга, то удалось бы казнить бесконечно много мудрецов.
Если я не ошибаюсь :)