Как не ошибаться

означают «красный», «желтый», «зеленый» и «голубой» соответственно. Концептуальное сходство звучания слов имеет свой смысл, но именно это затрудняет разговор, например, о том же цвете на той же людной вечеринке: «Простите, вы сказали “bofoc” или “bofog”?»
[229]
Впрочем, некоторые современные искусственные языки устроены иначе: в них используют принципы, сформулированные Хэммингом и Шенноном. Один из самых успешных примеров такого подхода – язык ложбан
[230]

; в нем действует строгое правило, согласно которому два базовых корня (
ginsu
) не могут быть фонетически близкими.
Представление Хэмминга о расстоянии соответствует философии Фано: величина, которая крякает как расстояние, имеет право на то, чтобы вести себя как расстояние. Но нужно ли останавливаться на этом? Множество точек, расположенных от заданной центральной точки на расстоянии, меньшем или равном 1, имеет в евклидовой геометрии свое название: круг, или, в большей размерности, сфера

[231]
. Таким образом, мы должны обозначить множество строк, расстояние Хэмминга которых от кодового слова не больше 1
[232]
, термином «сфера Хэмминга», в центре которой находится кодовое слово. Для того чтобы код был кодом с исправлением ошибок, ни одна строка (ни одна
точка

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

Таким образом, задача конструирования кодов с исправлением ошибок имеет такую же структуру, что и классическая геометрическая задача про упаковку сфер: каким образом разместить множество сфер одинакового размера в небольшом пространстве как можно плотнее, при условии что любые две сферы никогда не пересекутся? Проще говоря, сколько апельсинов можно уложить в ящик?

Задача упаковки сфер гораздо старше кодов с исправлением ошибок; этой проблемой занимался в свое время астроном Иоганн Кеплер, в 1611 году написавший на латинском языке трактат Strena, seu de nive sexangula («Новогодний подарок, или О шестиугольных снежинках»)
[233]
{196}

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

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

Следующий слой должен выглядеть аналогично, но зернышки необходимо выложить так, чтобы каждое разместилось в маленьком треугольном углублении, образованном тремя зернами нижнего слоя. Затем необходимо точно так же выкладывать следующие слои зерен граната. При укладке требуется проявлять некоторую осторожность: только половина углублений будет поддерживать сферы следующего уровня, и на каждом этапе предстоит решать, какую именно половину углублений вы хотите заполнить. Традиционное решение, которое называется «гранецентрированная кубическая решетка», имеет одно замечательное свойство: на каждом очередном уровне есть сферы, расположенные непосредственно над сферами тремя уровнями ниже. По мнению Кеплера, не существует способа более плотной упаковки сфер в пространстве

[234]
. В гранецентрированной кубической решетке каждая сфера соприкасается ровно с двенадцатью другими сферами. Кеплер считал, что по мере роста зерен граната каждое из них начинает придавливать своих двенадцать соседей, из-за чего поверхность у точки соприкосновения становится плоской и зерна граната превращаются в фигуры с двенадцатью гранями
[235]
.
Понятия не имею, был ли прав Кеплер насчет граната
[236]

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

[237]

: открытия в области кодирования подстегнули прогресс в области упаковки сфер. Например, в 1960-е годы Джон Лич, применив один из кодов Голея, построил в двадцатичетырехмерном пространстве невероятно плотную упаковку сфер. Конфигурация, известная сегодня как «решетка Лича», представляет собой крайне густонаселенное место, в котором каждая из двадцатичетырехмерных сфер соприкасается с 196 560 соседними сферами. До сих пор неизвестно, обеспечивает ли она самую плотную упаковку сфер в двадцатичетырехмерном пространстве, но в 2003 году Генри Кон

[238]
и Абхинав Кумар доказали, что, если более плотная решетка и существует, она обеспечит плотность упаковки сфер больше плотности решетки Лича максимум в

1,00000000000000000000000000000165 раз,

то есть довольно близко к решетке Лича
{197}
[239]
.

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

лжно отнестись крайне серьезно. Как выяснилось, решетка Лича содержит множество симметрий поистине экзотического вида – Джон Конвей, крупный специалист в области теории групп, узнал о ней в 1968 году, за двадцать четыре часа непрерывных вычислений он выписал на огромный рулон бумаги все симметрии решетки Лича
{198}
. В конечном счете эти симметрии позволили сформулировать последние фрагменты теории конечных групп симметрии, занимавшей умы алгебраистов на протяжении большей части ХХ столетия

[240]
.

Что касается старых добрых трехмерных апельсинов… Оказывается, Кеплер был прав, настаивая, что его способ упаковки самый лучший, но это не было доказано еще целых четыре столетия, пока в 1998 году теорию Кеплера не подтвердил Томас Хейлс, в то время профессор Мичиганского университета. Хейлс решил этот вопрос с помощью сложного и изящного доказательства, в котором задача была сведена к анализу всего лишь нескольких тысяч сфер, выполненному посредством большого объема компьютерных вычислений. Для математического сообщества не проблема создать сложное и изящное доказательство (мы привыкли к такого рода трудам), и эта часть работы Хейлса быстро получила превосходную оценку и подтверждение правильности; но что касается большого объема компьютерных вычислений – тут сложилась более серьезная ситуация. Доказательство возможно проанализировать до последней детали, однако с компьютерной программой все обстоит иначе. Теоретически человек в состоянии проверить каждую строку кода, но, даже если он с этим справится, может ли он полагаться на то, что код будет выполняться корректно?

Почти все математики признали доказательство ученого, но, по всей видимости, самолюбие Хейлса было сильно задето сомнением коллег по поводу того, что при доказательстве ему пришлось воспользоваться компьютерными вычислениями. После подтверждения гипотезы Кеплера он отошел от геометрии, которая сделала его знаменитым, и занялся проектом формальной верификации доказательств. Хейлс предвидит появление математики будущего, отличной от современной, и работает над ее созданием. Он считает, что математические доказательства, независимо от того, как они выполнены – с помощью ли компьютера или с помощью карандаша и бумаги, – стали настолько сложными и взаимозависимыми, что мы больше не можем быть полностью уверенными в их корректности. Классификация конечных простых групп – к настоящему времени завершившийся проект, важной частью которого стал выполненный Конвеем анализ решетки Лича, – состоит из сотен работ сотен авторов. В итоге их труд занимает около десяти тысяч страниц, и не приходится утверждать, что хотя бы один человек из ныне живущих понимает его целиком. Так как мы можем быть уверены в его правильности?

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

генерировать идеи
без какого бы то ни было вмешательства человека.

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

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

Код Хэмминга довольно хорош, но наверняка найдется кто-то, рассчитывающий, что ему удастся создать код более совершенный. В конце концов, в коде Хэмминга присутствует определенная избыточность: даже во времена перфолент и механических реле компьютеры были настолько надежны, что почти все блоки из семи бит передавались без искажений. Этот код кажется слишком консервативным: мы вполне могли бы обойтись включением меньшего количества защитных битов в свои сообщения. И мы действительно можем это сделать – доказательством тому служит знаменитая теорема Шеннона. Например, если ошибки происходят с частотой одна ошибка на тысячу бит, Шеннон утверждает, что есть коды, которые сделают каждое сообщение всего на 1,2 % длиннее, чем то же сообщение без кода. Более того, делая базовые блоки все более длинными, можно найти коды, обеспечивающие заданную скорость и удовлетворяющие любым требованиям к надежности, какими бы жесткими они ни были.

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

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

Хэмминг в 1986 году посвятил Шеннону почти восторженные слова – даже сорок лет спустя его открытие производило на математиков огромное впечатление:

Храбрость – качество, которым Шеннон владел в полной мере. Достаточно вспомнить о его главной теореме. Он хочет создать метод кодирования, но не знает, что делать, поэтому создает случайный код. Затем он заходит в тупик. А после задает невероятный вопрос: «Что сделал бы обычный случайный код?» Позже он доказывает, что обычный код вполне хорош, а значит, должен существовать как минимум один хороший код. Кто кроме человека беспредельной храбрости посмел бы размышлять о чем-то подобном? Это и есть черта великих ученых: им свойственна храбрость. Они идут вперед при невообразимых обстоятельствах; они никогда не прекращают мыслить.

Но если случайный код с большой вероятностью может быть кодом с исправлением ошибок, в чем смысл кода Хэмминга? Почему просто не выбрать кодовые слова совершенно случайным образом, опираясь на знание – согласно теореме Шеннона, – что этот код, по всей вероятности, будет исправлять ошибки? Вот одна из проблем этого плана. Недостаточно, чтобы код в принципе был способен исправлять ошибки; он должен быть применимым на практике. Если в одном из кодов Шеннона используются блоки размером 50, тогда количество кодовых слов равно количеству строк из 0–1 длиной 50 бит, что составляет 2 в степени 50, немногим более квадриллиона. Большое число. Ваш космический корабль получает сигнал, который предположительно является одним из квадриллиона кодовых слов или как минимум близок к одному из них. Но какое именно кодовое слово? Не перебирать же квадриллион кодовых слов по одному! Снова происходит комбинаторный взрыв, и в данном контексте это влечет за собой еще один компромисс. Коды со сложной структурой, такие как коды Хэмминга, в большинстве случаев легко декодировать. Однако сугубо специальные коды оказались не столь эффективными, как совершенно случайные коды, которые изучал Шеннон! За прошедшие с тех пор десятилетия, вплоть до настоящего времени, математики пытались одолеть эту границу между структурой и случайностью, кропотливо работая над созданием оптимальных кодов – достаточно случайных, чтобы быть быстрыми, и достаточно структурированных, чтобы поддаваться декодированию.

Код Хэмминга прекрасно подходит для трансильванской лотереи, но он неэффективен в случае лотереи Cash WinFall. В трансильванской лотерее всего семь чисел, в лотерее штата Массачусетс их сорок шесть. Следовательно, нам понадобится код побольше. Лучший код, который мне удалось найти для этой цели, открыл в 1976 году Ральф Деннистон из Лестерского университета
{199}
. И это очень красивый код.
Деннистон составил список из 285 384 комбинаций шести чисел из сорока восьми. Этот список начинается так:

1 2 48 3 4 8
2 3 48 4 5 9
1 2 48 3 6 32

В первых двух билетах четыре общие числа: 2, 3, 4 и 48. Однако (в этом и заключается поразительная особенность системы Деннистона) среди всех этих 285 384 лотерейных билетов вы не найдете
пяти

совпадающих чисел. Систему Деннистона можно перевести в код, как мы сделали это с плоскостью Фано, – заменив числа каждого билета строкой из 48 единиц и нулей, в которой 0 стоит на позициях, соответствующих числам вашего билета, а 1 – на позициях, соответствующих числам, которых в билете нет. Таким образом, первый билет из приведенных выше можно представить в виде такого кодового слова:

000011101111111111111111111111111111111111111110

Проверьте сами: тот факт, что среди всех этих лотерейных билетов нет двух билетов с пятью совпадающими числами из шести, означает, что этот код, подобно коду Хэмминга, не содержит два кодовых слова, разделенных расстоянием Хэмминга, меньшим четырех
[241]
.
Это можно сформулировать так: каждая комбинация из пяти чисел присутствует в максимум одном из билетов Деннистона. На самом деле все даже лучше: по существу, каждая комбинация из пяти чисел присутствует
ровно
в одном билете
[242]
.

Можете представить, какой тщательности требует выбор комбинаций чисел, входящих в список Деннистона? Деннистон включил в свою работу компьютерную программу на языке алгол, которая проверяет список на предмет того, действительно ли он обладает заявленным магическим свойством – для 1970-х годов жест довольно прогрессивный. Тем не менее Деннистон настаивает, что роль компьютера в этой работе следует расценивать как вторичную по отношению к его собственной: «На самом деле я хотел бы заявить, что все объявленные здесь результаты были получены без использования компьютера, хотя я допускаю, что их можно проверить с помощью компьютеров».

В лотерее Cash WinFall всего сорок шесть чисел, поэтому, чтобы сыграть в нее по методу Деннистона, придется немного нарушить красивую симметрию его системы, выбросив из его списка все билеты с числами 47 и 48. После этого у вас все еще останется 217 833 лотерейных билета. Предположим, вы достанете из тайника 435 666 долларов и решите поиграть в числа. Что произойдет?

В розыгрыше лотереи выпадает по шесть чисел – скажем, 4, 7, 10, 11, 34 и 46. Если произойдет маловероятное событие, эти числа совпадут с числами в одном из ваших лотерейных билетов – и вы получаете джекпот. Но даже если этого не произойдет, вы все равно сможете выиграть кучу денег по тем лотерейным билетам, в которых совпадут пять из шести чисел. Есть ли у вас билет с числами 4, 7, 10, 11, 34? В 
одном

из билетов Деннистона такие числа есть, а значит, единственный случай, когда у вас не окажется такого билета, – если в нем были числа 4, 7, 10, 11, 34, 47 или 4, 7, 10, 11, 34, 48, поэтому вы его выбросили.

Но как насчет другой комбинации из пяти чисел, скажем 4, 7, 10, 11, 46? Может быть, вам не повезло в первый раз, потому что билет с числами 4, 7, 10, 11, 34, 47 был одним из билетов Деннистона. Но в таком случае билет 4, 7, 10, 11, 46, 47 не может быть в списке Деннистона, поскольку пять чисел этого билета совпадают с пятью числами билета, который, как вам известно, входит в этот список. Другими словами, если из-за злополучного числа 47 вы упустите один из призов за пять угаданных чисел, это не приведет к тому, что вы упустите и все остальные призы. То же самое можно сказать и о числе 48. Вот список возможных выигрышных билетов в категории «Пять угаданных чисел из шести»:

4, 7, 10, 11, 34
4, 7, 10, 11, 46
4, 7, 10, 34, 46
4, 7, 11, 34, 46
4, 10, 11, 34, 46
7, 10, 11, 34, 46

Минимум четыре из этих билетов
гарантированно
окажутся среди ваших. В действительности, если вы купите 217 833 лотерейных билета Деннистона, у вас будет такая вероятность выигрыша:
вероятность выиграть джекпот составляет 2 %;
вероятность выиграть шесть призов в категории «Пять из шести» составляет 72 %;
вероятность выиграть пять призов в категории «Пять из шести» составляет 24 %;

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