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

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

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

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

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

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

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

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