Текст книги "Теории всего на свете"

Принцип голубей и ящиков

Джон Клейнберг

Тишевский профессор информатики Корнелльского университета (участник программы Тишевской школы искусств Нью-Йоркского университета); автор книги Networks, Crowds and Markets: Reasoning About a Highly Connected World («Сети, толпы и рынки. Рассуждения о чрезвычайно взаимосвязанном мире») (совместно с Дэвидом Изли)

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

Вот в чем его суть. Предположим, стая голубей садится на группу деревьев, причем голубей больше, чем деревьев. Тогда после того, как все голуби опустятся на ветки, по меньшей мере на одном из деревьев окажется больше двух голубей. [О «ящиках» в названии идет речь, так как они часто фигурируют в описании принципа вместо деревьев.]

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

Давайте перейдем к гораздо менее самоочевидному факту. Само по себе утверждение, которое мы сейчас приведем, весьма интригующе, однако еще более интригует та легкость, с которой оно выводится из принципа голубей и ящиков. Вот вам факт: на вашем фамильном древе (будем рассматривать лишь его участок, отвечающий последним четырем тысячам лет) есть два человека, назовем их А и В, причем А является предком матери В и одновременно предком отца В. Иными словами, на вашем фамильном древе имеется своего рода петля: две ветки, растущие вверх от В, сходятся к А, то есть среди ваших предков есть родительская пара, состоящая из кровных родственников – благодаря их сравнительно недавнему общему предку А.

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

1. У каждого человека двое биологических родителей.

2. Ни у кого не появляются дети после 100 лет.

3. Человечеству не менее 4 тысяч лет.

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

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

Вернемся к вам и вашим пращурам. Начнем рисовать ваше генеалогическое древо на 40 поколений в прошлое: вы, ваши родители, их родители и т. п., на 40 шагов назад. Поскольку каждое поколение, как правило, живет не больше 100 лет, последние 40 поколений на вашем фамильном древе все разместятся в прошедших четырех тысячах лет. (Собственно, они почти наверняка займут всего 1000–1200 лет, но помните, что мы всеми силами стараемся избежать возможных внутренних противоречий.)

Создание вашего генеалогического древа можно уподобить вычерчиванию «организационной схемы» – скажем, когда требуется отыскать людей для определенного набора профессий или ролей. Иными словами, кто-то должен быть вашей матерью, кто-то должен быть вашим отцом, кто-то должен быть отцом вашей матери и т. п., восходя вверх по древу. Каждую из этих позиций назовем «ролью предка»: это своего рода профессия, существующая в вашей генеалогической схеме, и мы можем говорить о работе вне зависимости от того, кто ее выполняет. При движении вверх (в прошлое) по вашему фамильному древу первое поколение над вами имеет две роли предка, соответствующие двум вашим родителям. Второе поколение содержит четыре роли предка (две ваших бабушки и два ваших дедушки), третье – восемь ролей (все ваши прабабушки и прадедушки). При подъеме на каждый следующий уровень удваивается число ролей предков (вакансий, которые необходимо заполнить). Расчеты показывают, что 40 поколений потребуют более триллиона ролей, и для каждой должен существовать исполнитель.

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

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

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

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

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

Еще кое-что о принципе голубей и ящиков

Чарлз Сейфе

Профессор журналистики Нью-Йоркского университета, бывший автор журнала Science; автор книги Proofiness: The Dark Arts of Mathematical Deception («Непроницаемость: темное искусство математического обмана»)

Порой даже простой подсчет может поведать нечто значительное. Однажды, еще в конце 1990‑х, будучи корреспондентом журнала New Scientist, я получил рекламное электронное письмо, воспевавшее какую-то необычайную компьютерную программу. В письме провозглашалось, что эта программа архивирования данных произведет настоящую революцию в цифровом мире, ибо она столь эффективна, что может сжать любой файл на 95 % или больше, не потеряв при этом ни единого бита данных. Может быть, мой журнал не упустит шанс поведать миру об этом софте, который позволит хранить на жестком диске в 20 раз больше информации, чем раньше?

Нет, мой журнал не станет об этом рассказывать, решил я.

Подобный алгоритм сжатия информации не может существовать. Это алгоритмический аналог вечного двигателя. Этот софт – жульничество. Причина – принцип голубей и ящиков.

Принцип голубей и ящиков – по сути, простое правило счета. Если у вас имеется n голубей и вам удалось запихнуть их менее чем в n ящиков, это означает, что по меньшей мере один ящик будет содержать в себе более одной птицы. Очевидно до банальности, не правда ли? Однако этот принцип – весьма полезный и мощный инструмент. К примеру, представим себе, что компрессионный софт, о котором шла речь, соответствует рекламному описанию и сжимает каждый файл в 20 раз без потери информации. Таким образом, каждый файл размером 2000 бит будет стиснут в какие-нибудь 100 бит, а при обращении алгоритма этот стобитный файл примет первоначальную форму, ничуть при этом не пострадав.

Сжимая файлы, вы волей-неволей натыкаетесь на принцип голубей и ящиков. Ведь общее количество 2000-битных голубей намного, намного больше (их 2²⁰⁰⁰, если быть точным), чем 100-битных ящиков (их 2¹⁰⁰). Если алгоритм позволяет полностью втиснуть первое во второе, это означает, что по меньшей мере один ящик должен содержать более одного голубя. Возьмем этот ящик (этот 100-битный файл) и попробуем обратить алгоритм сжатия, расширив этот файл до его исходной 2000-битной формы. Это не удастся сделать! Поскольку существует множество 2000-битных файлов, каждый из которых окажется сжатым в один и тот же 100-битный файл, алгоритм не сумеет определить, какой из этих 2000-битный файлов – истинный оригинал, так что компрессию будет невозможно обратить.

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

Подобного рода «пересчет» открывает перед исследователями обширные горизонты. Немецкий математик Георг Кантор использовал разновидность обратного принципа голубей и ящиков, дабы показать, что действительные числа невозможно упаковать в ящики, предназначенные для целых чисел (по одному ящику на каждое число), хотя целых чисел бесконечно много. Отсюда следовал трудновообразимый вывод: существуют различные уровни бесконечности. Бесконечность целых чисел ничтожна по сравнению с бесконечностью действительных чисел, которая, в свою очередь, смехотворно мала по сравнению с еще одной бесконечностью, а та – по сравнению с еще одной бесконечностью… бесконечное число бесконечностей, которые останутся неисследованными, пока мы не научимся как-то их считать.

Применение принципа голубей и ящиков к исследованию глубин космоса приводит к еще более странным умозаключениям. Один из физических принципов, так называемый принцип голографической ограниченности, гласит: для каждого конечного объема пространства существует лишь конечное число возможных конфигураций массы и энергии. Если, как склонны полагать космологи, Вселенная бесконечна, то в ней существует бесконечное количество объемов пространства размером с видимую вселенную – гигантских космических пузырей, содержащих материю и энергию. Если пространство более или менее гомогенно (однородно), то в пузыре, где мы с вами обитаем, нет ничего такого уж особенного и уникального. Из всех этих допущений, взятых в совокупности, следует ошеломляющий вывод. Бесконечность количества таких пузырей размером со вселенную при конечном числе конфигураций вещества и энергии в каждом означает, что существует даже не одна точная копия нашей Вселенной (и нашей Земли). Согласно космической версии принципа голубей и ящиков, существует бесконечное количество копий каждой (строго выражаясь, «почти каждой»: для этого выражения имеется точное математическое определение) из возможных вселенных. Мало того, что существует бесконечное количество ваших собственных копий на этом бесконечном количестве планет Земля, есть и бесконечное количество вариаций на ту же тему: вы с хватательным хвостом, вы с несколькими головами, вы как профессиональный жонглер хищными кроликоподобными зверьками, получающий драгоценности для украшения одежды в уплату за демонстрацию своего искусства. Как видите, даже простой счет «раз, два, три…» способен привести к причудливым и неожиданным результатам.

Почему в программах встречаются баги

Марти Хёрст

Кибернетик, факультет информации Калифорнийского университета в Беркли; автор книги Search User Interface («Пользовательские поисковые интерфейсы»)

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

Почему мы не можем в программировании быть так же успешны, как в других областях техники? Возможно, наиболее романтичным мыслителем из всех, кому следовало бы адресовать такой вопрос, является Фредерик Брукс, автор книги The Mythical Man-Month («Мифический человеко-месяц»). (Если обратить внимание на то, что эта книга со столь неудачным названием, как бы подразумевающим, что «человек» – это лишь «мужчина», man, впервые вышла в 1975 году, легче игнорировать сквозящий в ней сексистский душок: утверждения, которые Брукс сделал 4 десятка лет назад, почти все верны и на сегодняшний день, за исключением того, что программист – не всегда «он», как пишет Брукс, – бывает и «она».)

Делясь с читателями радостями программирования, Брукс пишет:

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

Но у этой магии есть своя оборотная сторона:

Во многих видах творческой деятельности средство исполнения не очень-то податливо и надежно. Древесина расщепляется, краска размазывается, электрические цепи дают короткое замыкание. Эти физические ограничения, присущие средству или материалу исполнения, сдерживают и выражение идей, создают непредвиденные трудности в их воплощении и развитии. …Между тем программист творит с помощью невероятно податливых средств. Он созидает новое из чистого мысленного вещества – идей и их весьма гибких представлений. А поскольку средство податливо, мы ожидаем лишь незначительных трудностей при воплощении наших мыслей; отсюда наш упорный оптимизм. Баги возникают из‑за того, что сами наши исходные идеи имеют погрешности; вот почему наш оптимизм не очень-то оправдан.

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

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

Узоры в честь Кейджа

Ханс-Ульрих Обрист

Куратор галереи Serpentine (Лондон); автор книг Ai Weiwei speaks («Говорит Ай Вэйвэй»), Project Japan («Проект “Япония”») и многих других

В искусстве название работы может часто служить ее первым объяснением. В этой связи особенно показательными мне представляются названия произведений Герхарда Рихтера. В 2006 году, когда я заглянул к Рихтеру в его кельнскую студию, он только что закончил цикл из шести взаимосвязанных абстрактных картин под общим названием «Кейдж».

Между полотнами Рихтера и композициями Джона Кейджа есть много общего. В книге, посвященной циклу «Кейдж», Роберт Сторр отмечает, что еще в 1963 году Рихтер посетил выступление Кейджа на дюссельдорфском фестивале «Festum Fluxorum Fluxus», и прослеживает аналогии в творческих процессах двух мастеров. Кейдж часто применял в своих композициях «метод случайности»: наиболее известно использование им для этих целей Книги Перемен. В своих абстрактных картинах Рихтер также намеренно вводит элемент случайности. Иной раз он наносит масляную краску на холст при помощи специальных больших шпателей, скребков и валиков. Цвет краски он выбирает сам, но тот след, который устройство оставит на холсте, в значительной мере зависит от случайных факторов. Подобное обращение к «управляемой случайности» роднит искусство Кейджа и Рихтера. Кроме того, у Рихтера само название «Cage», (в переводе с английского – клетка) несет и зрительные ассоциации: в своей совокупности эти шесть полотен кажутся чем-то герметичным, почти непроницаемым. Так что название имеет разные смысловые пласты.

Аналогии с творчеством Кейджа можно найти не только в абстрактных картинах Рихтера, но и в других его работах. Так, его книга «Узоры» – моя любимая среди всех вышедших в 2011 году. В ней описывается проведенный Рихтером эксперимент: изображение со своего «Абстрактного полотна «[CR: 724-4]» он разделяет на вертикальные полосы: сначала на 2, затем на 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048 и, наконец, на 4096 и 8190 полосок. Разумеется, в ходе этого процесса получаются всё более узкие полоски. Затем полоски зеркально отражаются и дублируются, что приводит к огромному разнообразию узоров. Результат – 221 узор. Все они напечатаны в виде 246 книжных разворотов. В своих «Узорах» Рихтер задает жесткие правила, однако он не манипулирует результатом, так что получающиеся изображения опять же являются плодом взаимодействия четко выстроенной системы и случайности.

«Узоры» – лишь одна из многих выдающихся арткниг, которые Рихтер сделал за последние годы. В их числе – «Лес» (2008), а также более давний «Лед» (1981), куда включены удивительные фотографии из его путешествия в Антарктиду, расположенные особым образом. В этих книгах серии фотографий прослоены пустым пространством, напоминающим паузы в музыке. Рихтер сам признался мне, что такая структура книги навеяна «музыкой, Кейджем и молчанием».

В 2007 году Рихтер спроектировал 20‑метровой высоты витраж для южного трансепта (поперечного нефа) Кельнского собора. «Окно для Кельнского собора» состоит из 11 тысяч сделанных вручную квадратиков стекла 72 оттенков, навеянных палитрой оригинальных средневековых витражей, уничтоженных во время Второй мировой войны. Раскраску половины квадратиков задал генератор случайных чисел, вторая же половина стала их зеркальным отражением. Таким образом, Рихтер снова сознательно выпустил из рук жесткий контроль над художественным процессом, подчинив индивидуальную волю творца силам, которыми он не может управлять. «Совпадения только приносят пользу, – говорил мне Рихтер, – поскольку они всегда значимы – и когда их просто допускаешь, и когда их подчеркиваешь, и даже когда их устраняешь».

Недавно в Хальберштадте состоялось исполнение кейджевской пьесы «ORGAN² / ASLSP». Аббревиатура «ASLSP» расшифровывается как «as slow as possible» – «как можно медленнее». Кейдж не дал иных уточнений к этой инструкции, так что каждое исполнение этого произведения должно поневоле отличаться от других. Если исполнять пьесу целиком, процесс займет 639 лет. Медленность этого кейджевского творения играет важнейшую роль для нашего нынешнего времени. С развитием глобализации и Интернета все процессы разогнались до скорости, при которой не остается времени на их критическое осмысление. А значит, кейджевское «Медленное движение» как бы советует нам не спешить с обдумыванием решений и применять подход, более ориентированный на местные особенности. Эта идея неспешности – одна из многих сторон кейджевского творчества, которые делают его наследие сегодня весьма актуальным.

Рихтеровское емкое название «Cage» можно развернуть до пространной интерпретации его цикла (да и других его работ), однако эта краткая форма, по сути, уже содержит в себе всё необходимое. Название, как и объяснение какого-нибудь явления природы, словно бы раскрывает тайны художественных произведений Рихтера, описывая их соотношение с одной из центральных фигур в культуре XX века – Джоном Кейджем, которого сближает с Рихтером постоянное обращение к великим темам случайности, неопределенности, зыбкости.