Вы всё ещё верите в аксиому выбора?

[57ded]

Вам сюда.

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

Утверждение Рассмотрим следующую задачу. Счётное множество мудрецов выстроены в натуральный ряд (лицом в сторону возрастания ряда, так что каждый видит перед собой бесконечное число мудрецов). Каждый из

Comments

Кровожадно

[m_ustinov]

Ну это не фокус. Вот если бы выжило только конечное число мудрецов...

Re: Кровожадно

[57ded]

Интересно. Но не знаю, как решать (и возможно ли).
Также пока не придумал, как быть с теми задачами, что я сформулировал в конце поста. Может придумаем или
a_shen прочтёт и что-то вумное скажет.
Главное, удалось продемонстрировать несостоятельность аксиомы выбора :)

А давайте их всех казним

[yurymakarychev]

Пусть A_n множество таких раскрасок шляп ( = последовательностей 0 и 1), что палач казнит первых n мудрецов. Понятно, что

a) A_n - замкнуто. Действительно, проверим, что дополнение к A_n открыто. Рассмотрим раскраску x, при которой один из первых n мудрецов остаётся цел и невредим. Предположим, машина Тьюринга этого мудреца смотрит на шляпы только первых N мудрецов ("на входе" x). Тогда, как бы мы не поменяли цвета шляп у мудрецов N+1, N+2, ..., наш мудрец всё равно останется жив. Таким образом, некоторая окрестность x тоже лежит в дополнении к A_n.

б) A_n - не пустое множество. Оденем на всех мудрецов N+1, N+2, ... белые шляпы. Посмотрим, на предсказание МТ N-ого мудреца, и покрасим его шляпу в противоположенный цвет. Повторим эту процедуру для N-1, N-2, ..., 1-ого мудреца. Все они будут казнены :-(

Теперь рассмотрим пересечение всех A_n. В живых никто не останется...

Re: А давайте их всех казним

[57ded]

Хорошо.
Только вычислимо всех казнить не получится :)
Потому что эти гады могут сломать любую вычислимую стратегию. Причём сломать в бесконечном числе мест. Так что задача от Миши полностью решена.

Re: А давайте их всех казним

[m_ustinov]

В случае твоего решения с бесконечным числом казней стратегия такая же невычислимая, т.к. вычислимо определить, зависает ли на последовательности белых колпаков хотя бы один мудрец, невозможно, и если лишь конечное количество останавливаются, то алгоритм "зависнет". Таким образом, достаточно всем мудрецам, начиная с какого-то, не остановиться, и стратегия сломана. Т.е. твоя стратегия вычислимая только если лишь конечному числу мудрецов разрешено выбирать "плохие" алгоритмы, которые могут когда-либо не остановиться. Если же всем мудрецам запретить выбирать такие алгоритмы, то вычислимой становится и стратегия, предложенная для решения задачи от Миши. А именно, раз заранее известно, что каждая МТ остановится, то для любой n-й МТ можно вычислимо узнать максимальный номер мудреца, цвет которого она посмотрит при любом возможном раскладе впереди стоящих шляп, и таким образом узнать, когда цвет шляпы n-го мудреца полностью определен, двигаясь рекурсивно как предложено выше.

Re: А давайте их всех казним

[57ded]

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

Re: А давайте их всех казним

[m_ustinov]

1. Сорри, забыл, это Митя Любарский, у меня ЖЖ нету :)
2. Вычислимая последовательность мудрецов - это что такое? Надо ли трактовать буквально, т.е. что существует алгоритм, который для произвольного n сгенерит некую n-ю машину Тьюринга?

Re: А давайте их всех казним

[57ded]

Вычислимая последовательность -- это такая, для которой есть машина Тьюринга, которая по любому n останавливается и возвращает f(n).

Re: А давайте их всех казним

[m_ustinov]

Значит, f(n) - это n-й мудрец, т.е. n-я машина Тьюринга. Если f(n) == const = {всегда зависающая машина тьюринга}, то f(n) - вычислима. Имеем вычислимую последовательность всегда зависающих МТ, которые не остановятся, и в итоге раскраска будет невычислима. Митя Л.

Re: А давайте их всех казним

[57ded]

В этом случае она как раз будет вычислима g(n)=const="белый".

Re: А давайте их всех казним

[m_ustinov]

Понял. В таком случае твое утверждение можно упростить до "для ЛЮБОЙ последовательности мудрецов существует вычислимая раскраска, такая что...". И это утверждение, видимо, остается в силе и для задачи с убийством всех. Митя Л.

Re: А давайте их всех казним

[m_ustinov]

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

Точно получится спастись бесконечно многим

[57ded]

Это более-менее стандартная техника из матлогики. Мудрецы разбиваются на бесконечно число бесконечных "банд", каждая "банда" спасается от своей машины Тьюринга. А именно, мудрец запускает МТ, предназначенную для его банды и смотрит, какой колпак МТ наденет на него... Его и называет. Если МТ зависнет, зависнет и мудрец.

Re: А давайте их всех казним

[m_ustinov]

А почему? Или она мухлюет и при генерации последовательности тоже спрашивает оракула?
То есть, если f(n)=const понятно, а если f(n)=хуеблядскаяпиздопроебидина!?!

Re: А давайте их всех казним

[m_ustinov]

хуеблядскаяпиздопроебина, в смысле.
Извини, опечатался.

Re: А давайте их всех казним

[57ded]

1. Представьтесь, пожалуйста.
2. Сформулируйте, пожалуйста, Ваш вопрос/возражение точнее, чтобы я его понял.