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

[knop]

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

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

Comments

[efimpp]

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

[junipher_greene]

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

[efimpp]

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

[knop]

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

[knop]

Да, кстати. Такой тип должен иметь название "really real".

[anatbel]

Это сильно. :)

[knop]

О, нет, тут мы не разбираемся со временем вычислений. Хотя это и интересный поворот сюжета.