Завдання стиснення даних у своїй найпростішій формі може відноситися до чисел та їх позначень. Числа можна позначати чисельними ("одинадцять" для числа 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