Джордан Элленберг - Как не ошибаться. Сила математического мышления

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

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

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

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

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

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

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