Парадоксы о сжатии данных

Задача сжатия данных в своей простейшей форме может относиться к числам и их обозначениям. Числа можно обозначать числительными («одиннадцать» для числа 11), математическими выражениями («два в двадцатой» для 1048576), строковыми выражениями («пять девяток» для 99999), именами собственными («число зверя» для 666, «год смерти Тьюринга» для 1954), или произвольными их комбинациями. Годится любое обозначение, по которому собеседник сможет однозначно определить, о каком числе речь. Очевидно, что сообщить собеседнику «факториал восьми» эффективнее, чем эквивалентное обозначение «сорок тысяч триста двадцать». Здесь возникает логичный вопрос: какое обозначение для заданного числа самое короткое?

Философ Бертран Рассел в 1908 опубликовал «парадокс Берри», который затрагивает вопрос обозначений чисел с противоположной стороны: какое самое маленькое число, для обозначения которого недостаточно восьмидесяти букв?
Такое число обязано существовать: из восьмидесяти русских букв и пробелов можно составить всего 3480 обозначений, значит, с использованием восьмидесяти букв можно обозначить не более 3480 чисел. Значит, некое число, не большее чем 3480, обозначить таким образом невозможно.

Значит, этому числу будет соответствовать обозначение «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв», в котором всего 78 букв! С одной стороны, это число обязано существовать; с другой, если это число существует, то его обозначение ему не соответствует. Парадокс!

Самый простой способ отмахнуться от этого парадокса — сослаться на неформальность словесных обозначений. Мол, если бы в обозначениях допускался лишь конкретно определённый набор выражений, то «самое маленькое число, для обозначения которого недостаточно восьмидесяти букв» не было бы допустимым обозначением, тогда как практически полезные обозначения типа «факториал восьми» остались бы допустимыми.

Есть ли формальные способы описания последовательности (алгоритма) действий над числами? Есть, и в изобилии — их называют языками программирования. Будем вместо словесных обозначений использовать программы (например, на Python), выводящие нужные числа. Например, для пяти девяток подойдёт программа print("9"*5). По-прежнему будем интересоваться самой короткой программой для заданного числа. Длину такой программы называют колмогоровской сложностью числа; это теоретический предел, до которого заданное число можно сжать.

Вместо парадокса Берри теперь можно рассмотреть аналогичный: какое самое маленькое число, для вывода которого недостаточно килобайтной программы?

Рассуждать будем так же, как и раньше: существует 2561024 килобайтных текстов, значит, килобайтными программами можно вывести не более 2561024 чисел. Значит, некое число, не большее чем 2561024, вывести таким способом невозможно.

Но напишем на Python программу, которая генерирует все возможные килобайтные тексты, запускает их на выполнение, и если они выводят какое-то число — то добавляет это число в словарь достижимых. После проверки всех 2561024 возможностей, сколько бы времени это ни заняло — программа ищет, какое самое маленькое число отсутствует в словаре, и выводит это число. Кажется очевидным, что такая программа уложится в килобайт кода — и выведет то самое число, которое невозможно вывести килобайтной программой!

В чём же подвох теперь? На неформальность обозначений его списать уже нельзя!

Если вас смущает то, что наша программа потребует астрономического количества памяти для работы — словарь (или битовый массив) из 2561024 элементов — то можно всё то же самое осуществить и без него: для каждого из 2561024 чисел по очереди перебирать все 2561024 возможных программ, пока не найдётся подходящая. Не важно, что такой перебор продлится очень долго: после проверки менее чем (2561024)2 пар из числа и программы он ведь завершится, и найдёт то самое заветное число.

Или не завершится? Ведь среди всех программ, которые будут испробованы, встретится while True: pass (и её функциональные аналоги) — и дальше проверки такой программы дело уже не пойдёт!

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

Источник: habr.com