Что у Миши В. - тоска по элитарности. Наверное, да - физики-лирики. Но как это скучно, Господи! Как это безнадежно тоскливо и автоматично.
Действительно - отбойным молоток на ножках.

Неисправим все же.
Божья роса ему всюду.
Я б отлеживался пару дней тихохонько после вчерашнего.

Пресловутая жертвенность советских военных фильмов, романов, стихов и песен, ориентация не на побеждающего, а на погибающего/страдающего героя (в лучших образцах - "Летят журавли", "Баллада о солдате", "Иваново детство", "Враги сожгли родную хату...", "Сороковые, роковые" и так далее) обычно объясняется каким-то там особым менталитетом и прочей дерридой.
На самом же деле все довольно просто - о соотношении положенных между Прутом и Волгой советских/немецких солдат все примерно догадывались. Типичный случай прямой социологической функции искусства. Иначе и говорить невозможно. А там уж, конечно, советская агиография наложилась, но ведь наложилась на вполне честное переживание бездарной войны.

блин, из-за всех этих постов про 57-ую сижу и чуть ли не (почти уже) плачу, ностальгия (не люблю слово) замучила, все вспоминаю и вспоминаю и вспоминаю

ХААААЧУ ОБРАТНО! Господи! НУ ПОЧЕМУ! НЕЛЬЗЯ! ТУДА!

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

тьфу ты, что ж я по ним так плачу, как по...

Я больна не вами,
Вы больны не мной.
Под нашими ногами -
Тяжёлый шар земной.
И сердцем, и руками
Спасибо за покой,
Луну над головами
И солнце над луной.

Это бесценно
http://www.livejournal.com/talkread.bml?itemid=7576559

andrey_ohm
...Чтобы жить так, как я хочу
и привык, нужно постоянно наращивать обороты, постоянно увеличивать
скорость, постоянно, образно говоря, вдавливать педаль глубже в
пол. Если этого не делать, придется в чем-то себе отказывать, а
это not an option.

К тому же, я хочу добиться вполне определенных вещей ко вполне
определенному времени (Chrysler PT Cruiser к 25-ти, MBA к 27-ми,
пятизначная зарплата к 28-ми) - а для этого, в общем, нельзя
давать себе пощады.

И там же внизу рекоммендации по чтению

Пелевин - такой же онанизм для мозгов, как и
фантастика. Читать его - оскорбление своему
интеллекту, поскольку в большинстве своем это сильно
упрощенное, вульгарное изложение ряда (тоже
преимущественно неглубоких) философских концепций,
связанных с теорией СМК и всяких смежных вещей.

Начинать я бы порекомендовал с Ясперса, ЛеБона и
Манхейма.

Как все таки непрактичен условно-русский человек.
То есть вот уже казалось бы все мечты сводятся
к деньгам, дорогой машине и престижному
диплому - а надо же Ясперс.

Глупо даже как-то. Читать надо никак
не Ясперса и Манхейма, а Карнеги и Ли Якокку.

И книгу Билла Гейтса "Дорога в Будущее".
Особенно книгу Билла Гейтса.

Интересно, а Скелетрон (мечты andrey_ohm,
как известно, осуществивший) чего читает? Уж точно
не ЛеБона. Я думаю, Скелетрон читает сборник
кроссвордов.

Мораль этого простая: если andrey_ohm так
желает быть похожим на Скелетрона,
иметь машину, MBA и кучу бабок - ЛеБона надо
немедленно выкинуть с Ясперсом на помойку.

Кроссворды, юноша, кроссворды. А перед важными
совещаниями - Карнеги и Ли Якокку. И книгу Билла
Гейтса "Дорога в Будущее". Особенно книгу Билла
Гейтса. "Дорога в Будущее". Read my lips.
"Дорога". "В." "Будущее."

Привет
Миша.

Current mood: tired

Пионер-засранец обыкновенный. На каждом шагу такие в Москве. На каж-дом. Еще мы зовем их "ворошиловскими стрелками" (отметая говорухинскую - старперскую - коннотацию).

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

Такая порода - до полной гибели всерьез.

Но сие ненадолго. Года через три юноша обучится главным навыкам русского бизнеса - многозначительно морщить лобик и томно молчать в ответ на важные вопросы. У нас был некогда подобный "антикризисный управляющий". Бедра у него начинались там, где у нормальных мужиков колени. Отсюда, видимо, реваншистские игры. Совещания начинал с фразы: " Ребята, я согласился работать здесь за вдвое меньшую плату, чем я стою, но я человек АЗАРТНЫЙ". Когда сотрудники начинали наперебой выкладывать очень неглупые идеи спасения проекта, он смотрел на свой ботинок 37 размера и вздыхал: "Мне скучно, бес". Профессиональным багажом его был один успешно проваленный проект и нежная (и вряд ли платоническая) дружба с одним из руководителей нашей корпорации. Плюс, разумеетсЯ, МБА, - но, как он проговорился по пьяни, в каком-то "Иерусалимском университете".Последнее озадачивало.

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

Мы отработали с ним месяц, а потом ушли стройными колоннами. Еще через месяц проект накрылся окончательно. Было тому ублюдку всего-то 24 года. Так что у Ома, я думаю, все еще впереди.

Насчет распознавания образов. Сима считает, что компьютеру
просто не хватает памяти. (На самом деле, это ей не хватает
памяти, чтобы расщеплять углеводороды, то есть, ее машине.)
Всегда ли можно будет написать букву "а" таким образом, чтобы
компьютер не отличил ее от "б"? Это не знаю, но кажется,
люди как грибница, и человеческое "подсознание" тоже как
грибница или как дерево. На дне, во всяком случае, глубоко,
шевелятся сущности. Каждая живой корень, и из каждой
растет дерево, на котором каждый сук, каждая ветка и каждый
лист указывают на корень и друг на друга. Про корень человек,
пробудившись, может не знать. Человек может путать; так,
дядя Юлиус, увидев свой портрет, сказал Малышу: "Плохо ты
нарисовал лошадь." Но и это не случайно.

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

Не исключено, что не компьютеры научатся распознавать образы,
а люди разучатся. Чтобы этого не случилось, отменить все и
ввести иероглифическое письмо.

Current mood: tired

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

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

Короче говоря, у меня возникло ощущение, что столь модная ныне любовь к гр. "Ленинград" объясняется шансом самоотождествления с тем самым лиргероем, которым посещающей концерты группы публике никогда не стать (и которым она, разумеется, не является - чистенькие мальчики и девочки, которым вряд ли приходилось хоть раз объясняться с ментами по поводу наличия в их карманах пресловутых радостей ямайских негров - да и не носят их, радости, в карманах обычно-то...) - а тут (как ей - публике - кажется) социальный протест, бля, выход за пределы собственной личности, бля, шприцы, бля, об вены... Самое интересное, что гр. "Ленинград", по моему ощущению, сама плохо понимает, о чем поет, и уж во всяком случае проституирующе адаптирует смысл своих текстов для публики - той самой, чистенькой.

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

Error
You must be logged in to view this protected entry.

Оригинал сообщения

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

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

На некотором острове живут: люди, которые всегда говорят правду, люди, которые всегда лгут, и люди, которые просто отвечают наугад, случайным образом. Причём они всегда ходят по три человека, так, что в каждой тройке есть по одному представителю каждого типа. Путник встретил такую тройку. Может ли он определить, кто есть кто, задав всего три двоичных вопроса (т.е. вопроса, на каждый из которых существуют всего два ответа)? Каждый вопрос можно задавать только одному человеку. Жители острова знают друг о друге и о себе самих, кто есть кто.

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

Троих математиков сажают в тюрьму на бесконечное количество дней.

Бесконечность дней - счётная, она же алеф-ноль. Каждый математик сидит
в отдельной одиночной камере, и общаться между собой во время заточения
они никак не могут.

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

Математикам известен следующий факт. Распределение света по дням в камерах произойдёт по одному из двух сценариев:

1. В каждый отдельный день свет горит только в одной камере из трёх (но необязательно в одной и той же в разные дни).
2. Сначала, некоторое конечное количество дней, свет горит только в одной камере из трёх как и раньше, а потом, на протяжении всего срока, он горит каждый день в двух камерах из трёх (которые тоже могут меняться изо дня в день).

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

До начала заключения математики могут договариваться о чём угодно. Вопрос: могут ли они составить стратегию поведения, которая обеспечила бы им, что после отсидки срока их отпустят на свободу?

Update: Осторожно! В комментах находится правильное решение.

Current mood: content

В Амстердаме, по свидетельству some, живет
прекрасная обезьяна Владимир, Орангутанг. Он
выкуплен из Московского зоопарка.

"Этот Владимир, -- сказала some, -- ужасный
дрочила. Он огромный, как этот вот книжный шкаф,
у него здоровенные руки. Там же звери почти все
на свободе, но его держат за толстым стеклом, из-за
размеров.

Владимир очень любит детей. Можно сказать, без детей
он не начинает: ждет, когда их соберется побольше.
Вначале он приманивает их -- строит им рожи. Дети
в восторге подбегают поближе, все прилипают к стеклу.
Мамаши их очень рады: детям интересно смотреть на
обезьянку; сами где-то тут же и разговаривают,
смотрят на других обезьянок. И когда, наконец,
вся стенка вольера облеплена детишками, белокурыми,
в праздничных костюмчиках, в юбках, с бантами -- а
Владимир такой Лев Толстой, ему тем лучше, чем
больше -- он садится, разбрасывает в стороны свои
ноги, начинает копаться в своем меху и достает оттуда
громадную елду до колена. Дети, открыв рот, смотрят
на это хозяйство. Он показывает им, подмигивает,
строит рожи. Они, естественно, еще крепче прилипают
к стеклу. Тишина! А ведь голландских детей
невозможно заставить вести себя тихо. Мамаши
счастливы -- вероятно, очень интересная обезьянка.
Из раза в раз повторяется одно и то же. Никому и в
голову не приходит проверить, в чем, собственно,
дело. А он за стеклом входит в раж, поднимает все
время голову -- смотрят ли; придвигается поближе,
чтобы детям было лучше видно. Те смотрят, как
завороженные. И вот, наконец, одна из мамаш решает
взглянуть, что за милая штучка так надолго увлекла
малышей. Она подходит к стеклу. Владимир, видя
телку примерно своих габаритов, той же породы, и
приближающуюся -- естественно, сей же момент кончает
прямо на стекло. Дети смотрят на эту сметану,
мощным потоком стекающую по ту сторону стекла (к
другой прилипли их лица). Раз от разу повторяется
этот финал."

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

Итак, у нас есть гидра и Геркулес, который хочет её победить.
Гидра - любое конечное дерево, растущее из одного корня. Количество "сыновей" каждой вершины не ограничено (но конечно), равно как и высота дерева.
(заранее прошу прощения на случай, если моя терминология не совпадает с принятой в России — я нахально перевожу термины с английского)
Пример гидры с корнем в вершине А:


         A
        / \
       B   C
          / \
          D  E
            /|\
           F G H
 


Головами гидры назовём листья дерева - вершины, не имеющие сыновей. В данном примере головы - B,D,F,G,H.

Битва между Геркулесом и гидрой проводится дискретными ходами. На каждом ходу Геркулес отрубает одну из голов гидры (т.е. разрешается рубить только листья дерева).

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

Пример. Предположим, что своим первым ходом Геркулес отрубает голову G у гидры, изображённой выше. Тогда после первого хода гидра будет выглядеть так:


        A
       / \
      B   C
         /|\
        / | \
       D  E  E1
        / |  | \
       F  H F1 H1 
 


Если бы это был не первый ход, а 15-й, то после него от вершины C отходили бы 15 новых под-деревьев E1-F1-H1, E2-F2-H2, ..., E15-F15-H15.
С другой стороны, если у изображённой выше гидры Геркулес отрубает голову B, то у гидры не вырастают новые головы в результате этого хода.

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

Теперь собственно задачи:

1. Доказать: Для любой данной гидры у Геркулеса есть стратегия вырубки голов, позволяющая в результате полностью уничтожить эту гидру (за конечное число шагов).

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

2. Доказать: Для любой данной гидры любая стратегия Геркулеса по вырубке голов приводит к полному уничтожению гидры (за конечное число шагов).

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

Сначала немного мотивации. Предположим, что мне удалось бы найти некий способ пронумеровать деревья - присвоить натуральное число f(T) каждому дереву-гидре T - так, чтобы после операции отсечения головы и приращения новых число гидры всегда уменьшалось бы. Тогда задача была бы решена, т.к. бесконечной нисходящей последовательности натуральных чисел не бывает. Интуитивно это очевидно: если, например, последовательность натуральных чисел начинается с миллиона и всё время уменьшается, в ней не может быть больше миллиона членов. С формальной точки зрения это происходит потому, что множество натуральных чисел N вместе с порядком между его членами (т.е. отношением, задающим, какие члены больше каких других) вполне упорядоченно (по-английски well-ordered). Например, множество целых чисел Z не вполне упорядоченно: в нём есть бесконечная нисходящая последовательность -1, -2, -3, -4, ... .

Вполне упорядоченные множества тесно связаны с принципом математической индукции. В случае натуральных чисел этот принцип гласит следующее. Пусть некое утверждение верно для числа 0; кроме того, если оно верно для всех натуральных чисел меньше n, то оно верно и для n. Тогда это утверждение верно для всех натуральных чисел. Но почему это так - почему принцип верен? Предположим, что его заключение неверно, что есть число n₀, для которого утверждение не выполняется. Тогда должно быть какое-то число n₁ меньше его, для которого оно тоже не выполняется (иначе по условию оно выполнялось бы для n₀). Тогда в свою очередь должно найтись n₂ < n₁, для к-го условие не выполняется, и так далее; эта цепочка никогда не может завершиться на нуле, т.к. для него дано, что условие выполняется; поэтому неизбежно выстраивается бесконечная нисходящая последовательность n₀ > n₁ > n₂ > ..., что как раз и противоречит вполне-упорядоченности натуральных чисел.

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

Для этого нам и нужны ординалы.

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

0 1 2 3 4 5 6

На него можно посмотреть как на множество из семи объектов — не обращая внимания на порядок между ними. Такому взгляду на множества соответствуют кардинальные числа, измеряющие размеры множеств; кардинальное число этого множества - 7, т.к. у него семь членов.
Но можно на него посмотреть и как на упорядоченное множество из семи членов: 0 < 1 < 2 < 3 < 4 < 5 < 6.
Любые два упорядоченных множества из семи членов - будь то семь натуральных чисел, семь точек на прямой или семь любых других объектов, выставленных в каком-либо порядке - изоморфны между собой, то есть между ними всегда можно построить однозначное соответствие, сохраняющее порядок:



0 1 2 3 4 5 6
 | | | | | | | 
 a b c d e f g



Ординальное число 7 - в отличие от кардинального числа 7 - являет собой каноническое вполне-упорядоченное множество из семи элементов - например, <0 1 2 3 4 5 6>. Ординальные числа являются абстрактизацией идеи вполне-упорядоченного множества: если есть два разных вполне-упорядоченных множества, которые изоморфны друг другу - т.е. с точки зрения порядка членов они как бы "одно и то же" - то они обязаны соответствовать одному и тому же, идентичному ординальному числу.

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

Выстроим цепочку ординальных чисел:


0 - (пустое множество)
 1 - 0
 2 - 0 1
 3 - 0 1 2 
 4 - 0 1 2 3
 ...



И теперь построим новое, объединяющее все обозначенные выше, которое называется омега (w):



w - 0 1 2 3 4 5 6 7 8 9 10 11 12 13 ... 



Омега является порядковым типом множества всех натуральных чисел. Теперь добавим "в конце" ещё один объект:



w+1 - 0 1 2 3 4 5 6 7 8 ... a



В качестве упорядоченного множества w+1 выглядит так: сначала идут все натуральные числа, а "после них", после того как "все они кончатся", ещё один объект, который больше их всех. Я его здесь обозначил буквой a для простоты; формальный подход немного запутанней.

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

С одной стороны, любое упорядоченное множество, которое "устроено" таким же способом - сначала бесконечное счётное множество объектов, а потом ещё один, больше их всех - будет изоморфно w+1. С другой стороны, упорядоченное множество w+1 не изоморфно w. Не существует взаимно однозначного соответствия между w+1 и w (множеством натуральных чисел), сохраняющего порядок. Это легко видеть хотя бы потому, что у w+1 есть наибольший член, который больше всех остальных, а у w такого нет, поэтому куда бы этот наибольший член a ни "поставить" в таком соответсвии внутри w, там всегда будут числа больше его, в то время как в w+1 больше его ничего нет - порядок нарушится.

С другой стороны, размер, он же кардинальность, у множеств w и w+1 одинаковый, и равен размеру множества натуральных чисел. Иными словами, множество w+1 можно пересчитать, подставив ему в соответсвие натуральные числа из w:



a - 0
 0 - 1
 1 - 2
 2 - 3
 ...
 


Таким образом все члены w+1 "пересчитываются" при помощи членов w, и поэтому размер у них одинаковый. Но такое соответствие не сохраняет отношения порядка между членами. Тип размерности у них одинаковый, а порядковый тип - разный. Т.е. на бесконечных множествах понятия кардинала и ординала расходятся; ординалы более скрупулезно различают разные множества. Если у двух множеств один и тот же порядковый тип-ординал, т.е. если они изоморфны, то размер у них уж точно одинаковый; но обратное неверно.

Важно заметить также, что множество w+1 остаётся вполне упорядоченным. В нём нет бесконечных нисходящих последовательностей. В самом деле, мы можем начать такую последовательность членом a, но потом нам неизбежно придётся "прыгнуть" куда-то внутрь натуральных чисел, и куда бы мы не прыгнули, оттуда останется только конечное кол-во мест спускаться дальше.

Построение ординалов можно продолжить:



w+1 - 0 1 2 3 4 ... a
 w+2 - 0 1 2 3 4 ... a b
 w+3 - 0 1 2 3 4 ... a b c
 ............
 w+w - 0 1 2 3 4 ... a b c d e ...
 


Например, w+123 "выглядит" так: "сначала" все натуральные числа w, а "после них" и больше их всех ещё 123 выстроенных в каком-то порядке объекта (к-е я здесь пометил латинскими буквами, но на самом деле их природа неважна, важно только отношение порядка между ними).

w+w "выглядит" так: сначала все натуральные числа, а потом "за ними" и больше их всех ещё одна копия натуральных чисел. Даже и это множество остаётся вполне упорядоченным. В нём невозможно построить бесконечную нисходящую последовательность. Где бы её не начать, например, во второй копии w, через конечное число шагов придётся спуститься куда-нибудь в первую, где тоже останется только конечное число шагов.

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

Продолжая (заменяю теперь латинские буквы числами для удобства, но надо понимать, что это разные копии w и потому "разные" числа):



w+w+1 - 0 1 2 3 4 ... 0 1 2 3 4 ... 0
 w+w+2 - 0 1 2 3 4 ... 0 1 2 3 4 ... 0 1
 ...
 w+w+w - 0 1 2 3 4 ... 0 1 2 3 4 ... 0 1 2 3 4 ...


Сокращая и подразумевая всегда под w копию всего множества натуральных чисел:


w+w+w - w w w
 w+w+w+1 - w w w 0
 w+w+w+2 - w w w 0 1
 ...
 w+w+w+w - w w w w
 .......
 w * w = w w w w w w ...
 



Совершая как бы новый предельный прыжок, мы приходим к ординальному числу w*w, которое "выглядит" так: копия натуральных чисел, за ней ещё одна, и ещё, и ещё, и так бесконечное число раз. Даже и это множество остаётся вполне упорядоченным. Пытаясь построить в нём нисходящую последовательность, мы неизбежно выбираем первый член в какой-то из копий w, например в 127-й; после этого мы можем только конечное число раз спускаться в каждой копии, и у нас есть только 127 копий, в которых спускаться; поэтому через конечное число шагов мы придём в начало.
Обозначим w² = w*w.
Далее:


w2+1 - w w w ... 0
 ...
 w2+w - w w w .... w
 w2+w+1 - w w w ... w 0
 ...
 w2+w2 - w w w ... w w w ...
 ........
 w3 = w2+w2+... - (w w w ...) (w w w ...) (w w w ...) (w w w ...) ...
 



Таким образом можно продолжать и дальше. Повторяя бесконечное число копий w³ одна за другой, получим w⁴, повторяя его - w⁵, и так далее. Каждый такой повтор добавляет огромное количество предельных переходов "внутрь" порядка, оценить которые интуитивно становится очень нелегко уже на стадии w². Тем не менее можно убедиться (подробно объяснять это я уже не буду), что все возникающее множества-ординалы остаются хорошо упорядоченными. Несмотря на гигантское множество разных бесконечностей, таящихся в них, можно построить только конечные по длине нисходящие последовательности членов.

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

Если взять предел



w w2 w3 w4 ...


то мы получим ординал w^w. От него можно продолжить дальше: w^w+1 ...
w^w + w ... w^w + w² ... w^w + w^w ... w^w + w^w + w^w ... w^w*w = w^w+1.

На этом этапе уже совсем практически невозможно оценить "на глаз" внутреннюю структуру порядков этих ординалов, такой она становится сложной. Но отсюда можно продолжать и дальше и дойти постепенно до w^w*w, w^w*w*w, и в пределе этого - w^ww.

Продолжая всё тот же процесс добавления копий меньших ординалов и перехода к пределу, мы приходим к ординалам w^www, w^wwww, w^wwwww и т.д.

Наконец, взяв предел этой последовательности "лесенок" степеней ординалов, мы получаем ординал, больший их всех, который называется эпсилон-ноль - ε₀. От него тоже можно продолжать дальше и строить, скажем, ε₀+1 и т.п., но это нам уже не нужно. Важно понять, что ε₀ является ординалом, который объединяет в себе все возможные комбинации натуральных чисел, w и степеней w. Начиная с w, можно складывать, умножать и возводить в степень друг друга сколько угодно раз, и никогда не выйдешь за пределы ε₀.

И все эти ординалы, включая ε₀, остаются вполне упорядоченными множествами.

Более того, между самими ординалами (а не только между их членами) можно определить отношение порядка: какой ординал меньше какого другого. Собственно, это получается тривиально после очень важного результата: если есть два ординала A и B, то либо A является начальным сегментом B (в качестве упорядоченного множества), либо B является начальным сегментом A, либо они идентичны. Доказывать строго я это не буду, но объяснить на примерах это можно весьма убедительно. Например, w является начальным сегментом ординалов w+1, w+w, w², w²+w+1, w^w и т.п. - собственно все ординалы, кроме конечных натуральных чисел, начинаются с копии w, как легко видеть из нашего построения их выше. Ординал w²+w+1 является начальным сегментом ординала w³. И вообще благодаря тому, что мы всегда строили новые ординалы пристроением справа к уже существующим, очевидно, что они выстраиваются таким образом в упорядоченную цепочку. И все ординалы меньше ε₀ являются начальными сегментами (каждый из них - разным начальным сегментом) ординала ε₀, который включает их всех.

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

Тут мы и приходим к решению задачи о Геркулесе и гидре. Каждому дереву-гидре мы ставим в соответствие ординал, путём, описанным в решении задачи; при этом мы всё время рекурсивно возводим в степени и складываем, и поэтому никогда не выходим за пределы ε₀, все получающиеся ординалы меньше ε₀ (более того, как легко проверить, любой ординал меньше ε₀ образуется с помощью какой-то гидры - но это сейчас не важно). Операция отсечения головы и вырастания новых уменьшает ординал дерева (опять-таки см. решение). Поэтому, если бы Геркулес мог бесконечно долго рубить гидру, мы могли бы построить бесконечную нисходящую последовательность ординалов, что невозможно. Что и требовалось доказать.

Вопросы и предложения принимаются.

Эта запись продолжает цикл: задача о Геркулесе и гидре, решение, объяснение арифметики
ординалов.

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

Начну издалека — формальной логической системой PA (сокращённо Peano Arithmetic).

Ещё с конца 19-го века известно, что довольно простой набор аксиом полностью определяет все возможные арифметические истины. Аксиомы эти принято было называть аксиомами Пеано. Вот один возможных их набор. Скажем, у нас есть логический язык, в котором присутствует константа 0, функциональный символ S(x) (долженствующий обозначать "следующее за x натуральное число"), функциональные символы + и * (для сложения и умножения). Определим следующие аксиомы:

1. S(x) = S(y) => x=y.
2. ¬∃x ( S(x) = 0 ). ("не существует x такого, что S(x)=0")
3. x + 0 = x
4. x + S(y) = S(x+y)
5. x * 0 = 0
6. x * S(y) = x * y + x
7. Если M - множество натуральных чисел так, что 0 ∈ M, и для каждого x выполняется x∈M => S(x)∈M, тогда для каждого x выполняется x∈M (принцип индукции).

(словами без символов: 7. Если М - множество натуральных чисел, так, что 0 принадлежит к М и для каждого x из "x принадлежит к M" следует "S(x) принадлежит к M", то тогда любой возможный x принадлежит к M)

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

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

7". Пусть φ(x) - некоторая формула со свободным параметром x. Если выполняется φ(0) , а также утверждение ∀x (φ(x) => φ(S(x))), тогда формула φ верна для всех натуральных чисел: ∀xφ(x) (индукция первого порядка).

(словами эта формула говорит: если выполняется phi(0), а также для любого x из phi(x) следует phi(S(x)), то тогда выполняется phi(x) для любого x).

7" на самом деле является не аксиомой, а схемой аксиом: для каждой возможной формулы φ существует отдельная аксиома 7", которую формально можно записать так: [φ(0)∧∀x (φ(x) => φ(S(x)))] => ∀xφ(x) .

Формальную систему, построенную из аксиом 1-6 и схемы 7", называют обычно системой PA, Peano Arithmetic (хоть это и несколько анти-исторично, т.к. сам Пеано индукцию первого порядка не предлагал и о ней не задумывался).

PA - очень мощная формальная система по своей доказательной силе. Логики изучают доказательную силу формальных систем при помощи формализации в них абстрактных понятий и доказательств. Так, например, в PA можно очень легко формализовать практически все комбинаторные рассуждения и теоремы, манипулирующие конечным кол-вом объектов; множество результатов из теории графов и других подобных "дискретных" областей математики. Вполне нетривиальным является, скажем, вопрос о том, достаточна ли сила PA для того, чтобы формализовать в ней недавнее доказательство теоремы Ферма. В PA можно формализовать и доказать части анализа и теории множеств, и т.д. и т.п.

Короче говоря, PA - очень мощная формальная система, не такая мощная, конечно, как теория множеств, в которой мы обычно проводим математические доказательства и рассуждения, но всё же очень мощная. Она очень хорошо, в частности, "схватывает" все наши интуитивные представления и методы работы с натуральными числами.
По множеству разных причин PA - очень популярная для изучения система аксиом в логике последних 50 лет; например, она тесно связана с теорией вычислимости, машинами Тюринга и т.п.

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

Долгое время, однако, у математиков не было ни одного примера естественного математического утверждения, недоказуемого в PA. Например, в теории множеств таким утверждением является гипотеза о континууме. В арифметике же простого и естественного примера не было (конечно, "естественность" здесь - понятие очень неформальное; но ясно, что, например, недоказуемое утверждение, к-е строится в процессе док-ва теоремы Гёделя, независимого от логики математического интереса не имеет).

И вот в конце 70-х и начале 80-х Парис и Кирби нашли сразу несколько таких примеров — "естественных" математических утверждений, которые, с одной стороны, верны, с другой стороны, недоказуемы в PA. Само по себе это является очень интересным логическим результатом; но с интуитивной точки зрения что это говорит нам об этих проблемах? - да то, что любое их доказательство обязано использовать методы, не-формализуемые в PA, т.е. в какой-то мере "сложные", "бесконечные" методы. У такого рода задач не может быть "простых", легко формализуемых решений.

Первым примером такого рода утверждений была так называемая "конечная теорема Рамзи"; это теорема из комбинаторики. А вот задачка про Геркулеса и гидру тоже являет собой, открытый несколько позднее, пример утверждения, недоказуемого в PA. А именно: утверждение "Любая стратегия Геркулеса приводит к уничтожению гидры" верно, но недоказуемо в PA. Это и означает на практике невозможность относительно "простого" решения этой задачи, при помощи относительно элементарных рассуждений, стремящихся ограничить рост числа голов, или пытающихся перенумеровать гидры числами (а не ординалами, как в действительно работающем решении), и т.п.

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

Конечно, сами гидры-деревья легко представить в PA, закодировав их каким-нибудь образом при помощи натуральных чисел (такая кодировка позволит "говорить" о деревьях на языке арифметики; она не решит задачу, т.к. не будет выполнять того свойства, что после каждого хода Геркулеса код дерева уменьшается). Стратегии, однако, являются объектами второго порядка (произвольными функциями из множества всех деревьев в множество их голов), их слишком много и их невозможно перенумеровать числами. Поэтому, строго говоря, утверждение "любая стратегия Геркулеса приводит к победе" невозможно даже выразить в PA. Но можно выразить при помощи формулы более слабое утверждение "любая вычислимая стратегия Геркулеса приводит к победе", и даже это утверждение PA не может доказать. Под вычислимой стратегией я понимаю здесь стратегию, к-ю можно задать с помощью компьютерного алгоритма (он получает на входе дерево и номер хода, и выдаёт голову, к-ю по его мнению нужно срубить).

Почему PA не может доказать "любая вычислимая стратегия Геркулеса приводит к победе"?

В середине 30-х годов немецкий учёный Генцен доказал непротиворечимость формальной системы PA (точнее , немного другой системы, но различия незначительны). Согласно второй теореме о неполноте Гёделя, никакая непротиворечимая и достаточно сложная формальная система не может доказать собственной непротиворечимости. В частности, PA не может доказать Cons(PA), где Cons(PA) означает утверждение о непротиворечимости (consistency) PA. Мы предполагаем при этом, что PA действительно непротиворечима, что в рамках современной математики является тривиальным утверждением (т.к. пользуясь всей мощью теории множеств мы просто можем построить модель для PA - а именно, множество натуральных чисел N. Любой набор аксиом, имеющий модель, непротиворечив). Но доказать непротиворечимость PA при помощи финитарных (конечных) методов - невозможно, поскольку все такие методы можно формализовать внутри самой PA, а сама PA своей непротиворечивости доказать не может.

В свете этого понятно, что доказательство Генцена не могло быть полностью финитарным. Но оно было почти финитарным - оно использовало исключительно финитарные методы, кроме одного места в рассуждении, где использовалась трансфинитная индукция до ε₀.

Что такое эта индукция? Она совершенно аналогична обычной индукции по натуральным числам, только простирается "дальше" на бесконечные ординалы до ε₀. Она говорит следующее: если некоторое утверждение верно для 0, а также его истинность для всех ординалов меньше α влечёт его истинность для ординала α (и это верно для любого α<ε₀), тогда это утверждение верно для любого ординала меньше ε₀.

Этот принцип трансфинитной индукции верен потому, что ординалы до ε₀ (да и после тоже) вполне упорядочены (см. в записи про ординалы объяснение того, как из вполне-упорядоченности следует принцип индукции). То есть не существует бесконечной нисходящей последовательности таких ординалов.

Собственно говоря, доказательство Генцена можно представить в виде, напрямую использующем это свойство вполне-упорядоченности. Генцен построил некое отображение доказательств в формальной системе PA в ординалы, при котором каждому формальному док-ву присваивается свой ординал меньше ε₀, и показал, что если существует доказательство противоречия в PA (т.е. если PA противоречива), то это док-во можно сократить так, чтобы получить другое док-во противоречия в PA, которому соответствует меньший ординал. Продолжая так неопределённо долго, мы построим бесконечныю нисходящую последовательность ординалов, что невозможно; поэтому доказательства противоречия в PA быть не может.

Что из этого следует? А следующее: принцип трансфинитной индукции до ε₀, а вместе с ним и вполне-упорядоченность всех ординалов до ε₀, невозможно доказать в PA. Потому что если бы их там можно было доказать, всё док-во Генцена можно было бы формализовать в PA и тогда PA доказывала бы свою непротиворечимость, что невозможно согласно второй теореме Гёделя о неполноте.

Теперь вернёмся к задаче о Геркулесе и гидре. Для любого возможного ординала меньше ε₀ существует дерево-гидра, которое кодируется именно этим ординалом (согласно алгоритму кодирования, описанному в записи с решением). Это легко видеть из свойств ординалов.

Далее, можно описать следующую (легко алгоритмизуемую) стратегию поведения Геркулеса. Пусть есть некая гидра, неважно на каком ходу образовавшаяся. Пронумеруем её вершины ординалами, как описано в решении. Начиная с корня, будем двигаться всё время к тому сыну, ординал которого наименьший среди всех сыновей текущей вершины. Когда дойдём до головы, отрежем её.

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

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

Таким образом, если бы PA могла доказать, что эта конкретная стратегия, описанная выше, всегда приводит к победе Геркулеса, то PA могла бы доказать вполне-упорядоченность ординалов меньше ε₀ (несколько точнее - конечность всех спускающихся последовательностей ординалов, могущих возникнуть в док-ве Генцена), и следовательно могла бы формализовать доказательство Генцена и доказать свою непротиворечимость. Но это невозможно. Следовательно, PA не может доказать, что описанная выше стратегия всегда приводит к успеху Геркулеса.

А если PA не может доказать это для данной конкретной стратегии, то естественно она не может доказать и более сильное, и верное, утверждение "любая вычислимая стратегия приводит к победе Геркулеса". И поэтому "простого" доказательства у задачи о Геркулесе и гидре нет.

Всё.

P.S. Reference:
L. Kirby and J. Paris, Accessible independence results for Peano arithmetic. Bull. London Math. Soc. 14 (1982), p.285-225.

Current mood: tired

Это было напечатано в студенческой газете Хайфского университета, автор мне неизвестен; спасибо Андрею Асиновскому за то, что переслал.

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


Извините, огласовки расставлять нет сил. Думаю, текст вы узнаете.



על חוף מפרש, אלון תפארת,
שרשרת פז עליו תבריק.
חתול למדן אסיר-שרשרת
הולך ושב מזמן עתיק.
פונה ימינה, שיר ישמיע,
פונה לשמאל, סיפור נולד.

שם נפלאות, שם שד מפסיע,
בת-ים יושבת על הבד.
שם יש נחש בתוך גולגולת
המצפה לשעת קלון.
בקתה על כרע תרנגולת
עמדה בלי דלת או חלון.
שם רפאים בגיא ויער,
שם על הגל פוקד הסער
לשטוף חול רך בבוקר חם,
שלושים נוטרים יפים כזוהר
יוצאים בסך, מימי הטוהר,
איתם מגיע שר הים.
שם בן מלכים בלי להזיע
שובה קיסר מפיל אימה,
שם קבל עדה, בלב רקיע,
על פני חורשות ושדות כמה
כשפן נושא איש-מלחמה.
בשבי בת-מלך מקוננת,
וזאב אפור לה כאומנת.
שם המכתש עם כשפנית
ביערים טייל רגלית.
נשמט שלדאי על פז שוחפת.
שם ריח רוס! רוחה רוחפת!

הייתי שם, הדבש נלגם,
ראיתי שם אלון מרקיע,
ולרגליו חתול משמיע
שירים ואגדות העם.
אחת זכרתי, מפולפלת,
ואספרה עתה לחלד...



Этот текст -- чей-то самопальный перевод предисловия "Руслана и Людмилы" на иврит. Очень милый и смешной по многим причинам.

Очень люблю эту задачку за её неортодоксальное, поразительное своей красотой решение.

Задача: доказать, что существуют два иррациональных числа x и y, так, что x^y (икс в степени игрек) - рациональное число.

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

Решение: обозначим sqrt(2) = корень из двух. Рассмотрим число X = sqrt(2)^sqrt(2).

Одно из двух: либо X - рациональное число, либо иррациональное.

Если X - рациональное число, то sqrt(2) и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное, задача решена.

Если X - иррациональное число, то заметим, что X^sqrt(2) = (sqrt(2)^sqrt(2))^sqrt(2) = sqrt(2)² = 2. Таким образом, X и sqrt(2) - два иррациональных числа, одно в степени другого дают рациональное - двойку. Задача решена.



---


Итак, что есть примечательного в этом решении? Мы доказали, что существуют такие иррациональные x и y, что x^y - рациональное число. Но мы не показали ни одной такой пары x и y, вообще ни на шаг не приблизились к доказательству того, что вот эти конкретные x и y действительно представляют собой нужную пару.

В принципе понятно, конечно, что наше число X, по-видимому, иррациональное, и, возможно, есть способ это доказать (или нету ещё? я всё время путаюсь в том, что здесь уже умеют делать, а что нет -- кажется, иррациональность e^pi ещё не доказали, например?). Но в принципе можно себе представить ситуацию, при которой иррациональность или рациональность числа X в принципе были бы недоказуемы; это совсем маловероятно в данном случае, но в каком-нибудь несколько более сложном вполне могло бы такое произойти.

Но даже если бы в принципе невозможно было доказать, что X рационально или что X иррационально -- всё равно наше доказательство оставалось бы верным.

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

То, да не то. Существование базы требует "мощной" аксиоматической механики - аксиомы выбора. Она изначально и очевидно неконструктивна, затем и нужна. В случае нашей задачки никакой аксиомы выбора не требуется, конструктивность нарушается на гораздо более "примитивном", "осязаемом" уровне - это, может быть, и делает её столь интересной. Мы не привыкли к столь явному нарушению "осязаемости" в столь простых вещах. Нам хочется взять и "пощупать" руками наши x и y, но мы не можем.

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

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

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

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

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

Вот простой пример. Возьмём какой-то нерешённый математикой вопрос. Например:

Верно ли то, что любое чётное число может быть представлено в виде суммы двух простых чисел?

Обозначим утверждение любое чётное число может быть представлено в виде суммы двух простых чисел буквой G. Теперь спросим следующее:

1. Существует ли машина Тюринга (иными словами, алгоритм), который выдаёт на выходе 1, если гипотеза G верна, и 0, если она неверна?

Казалось бы, задать этот вопрос - всё равно, что спросить "можем ли мы решить G алгоритмическим путём?" Но выясняется что это не так. Оказывается, существует тривиальный положительный ответ на вопрос 1.:

Если G верна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 1 и останавливается.
Если G неверна, то возьмём в качестве нашей машины Тюринга машину, которая пишет в качестве вывода 0 и останавливается.
В любом случае, существует машина Тюринга, к-я пишет 1, если G верна, и 0, если G неверна.


---


Мы ощущаем, что такое "решение" является обманом, подлогом. Но почему? Что здесь происходит? Что не так?

Легко увидеть аналогию с доказательством задачки про иррациональные числа. Мы не знаем, верна G или нет. Но если она верна, то мы можем сделать так-то, а если неверна, то по-другому. В результате мы получаем вполне правильное доказательство существования искомой машины, которое, тем не менее, совершенно нас не устраивает.

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

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

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

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

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

Одна приятная рассудительная женщина жила
в хорошей квартире со звукоизоляцией,
работала врачом гинекологом. Все ее коллеги
были женщины, ее начальница была женщина и
пациентки ее, все до одной, были женщины.
Никаких гадостей у них не было между ног,
ни чтобы там яиц, рогов или бороды. Только
ноги у начальницы были слегка волосатые. За
ежедневными разговорами о менструациях,
месячных циклах и других интересных предметах
протекала жизнь женщины. Характер у нее был
уравновешенный, вот только одно мешало: мужика
не могла видеть спокойно. Ну воротило ее от
этой мрази. К счастью, вокруг нее мужиков
почти не было. Но уж если на улице повстречает,
подойдет и пиздык ногой в пах. Не может себя
сдержать никак. А шпильки на босоножках
пачкаются в этой дряни, ну домой придет, зажмет
нос и давай чистить. Кровь, сперма, смегма и
выделения. Вся квартира воняет козлом.

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

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

Линклист для чтения.

Введение

http://www.improvement.ru/bibliot/chrono/chrono07.shtm
http://www.improvement.ru/bibliot/chrono/chrono08.shtm
http://www.improvement.ru/bibliot/chrono/chrono09.shtm
http://www.improvement.ru/bibliot/chrono/chrono10.shtm

Чтение по диагонали

http://www.improvement.ru/zametki/litvak/index.shtm
http://www.improvement.ru/zametki/struktvn/strukt3.shtm
http://www.improvement.ru/zametki/struktvn/strukt4.shtm
http://www.improvement.ru/zametki/struktvn/strukt5.shtm
http://www.improvement.ru/bibliot/levitas.shtm
http://www.improvement.ru/bibliot/kozlovsk.shtm
http://www.improvement.ru/bibliot/babiy.shtm
http://www.improvement.ru/bibliot/popov/index.shtm
http://www.improvement.ru/bibliot/ogrchaos/index.shtm
http://improvement.ru/discus/messages/14/75.html?1027437773

Two minutes

http://www.paranoia.ru/~chuck/articles/org_yourself.htm
http://www.dkeener.com/keenstuff/tasks.html
http://www.dkeener.com/keenstuff/software.html

Бумажки

http://www.improvement.ru/zametki/grafiki.shtm

Фирмы

http://www.improvement.ru/bibliot/taylor/index.shtm [2R]
http://www.improvement.ru/bibliot/reandzi/index.shtm [2R]
http://www.improvement.ru/bibliot/neprozh/index.shtm [2R]
http://www.improvement.ru/bibliot/jullien/index.shtm [2R]

Иное

http://ek-lit.agava.ru/drucsod.htm [2R]
http://www.improvement.ru/bibliot/ford/index.shtm [2R]
http://www.improvement.ru/bibliot/morita/index.shtm [2R]
http://www.improvement.ru/bibliot/trizbank.shtm
http://www.improvement.ru/bibliot/fedin/index.shtm