Парадокси за компресиране на данни

Проблемът с компресирането на данни, в най-простата му форма, може да се отнася до числата и техните обозначения. Числата могат да се означават с цифри ("единадесет" за числото 11), математически изрази ("двама през двайсети" за 1048576), низови изрази ("пет деветки" за 99999), собствени имена ("числото на звяра" за 666, "година на смъртта на Тюринг" за 1954 г.) или произволни комбинации от тях. Подходящо е всяко обозначение, чрез което събеседникът може ясно да определи за какво число говорим. Очевидно, кажете на събеседника си "факториел от осем" по-ефективна от еквивалентна нотация "четиридесет хиляди триста и двадесет". Тук възниква логичен въпрос: кой е най-краткият запис за дадено число?

Философът Бертран Ръсел публикува през 1908 г "Парадоксът на Бери", който засяга въпроса за записването на числата от противоположната страна: Кое е най-малкото число, което не изисква осемдесет букви?
Такъв номер трябва да съществува: от осемдесет руски букви и интервали можете да съставите само 3480 обозначения, което означава, че с помощта на осемдесет букви можете да обозначите не повече от 3480 числа. Това означава, че е невъзможно да се обозначи определено число не повече от 3480 по този начин.

Това означава, че този номер ще съответства на обозначението "най-малкото число, за което осемдесет букви не са достатъчни", който има само 78 букви! От една страна, това число трябва да съществува; от друга страна, ако този номер съществува, тогава неговото обозначение не съответства на него. Парадокс!

Най-лесният начин да отхвърлите този парадокс е да се позовавате на неформалността на словесните означения. Например, ако само конкретно дефиниран набор от изрази беше разрешен в нотацията, тогава "най-малкото число, за което осемдесет букви не са достатъчни" не би било валидна нотация, докато практически полезни нотации като "факториел от осем" ще остане приемливо.

Има ли формални начини за описване на последователността (алгоритъма) от действия върху числа? Има и то в изобилие - наричат ​​се езици за програмиране. Вместо вербални означения ще използваме програми (например в Python), които показват необходимите числа. Например, за пет деветки програмата е подходяща print("9"*5). Ще продължим да се интересуваме от най-кратката програма за даден номер. Дължината на такава програма се нарича Колмогорова сложност числа; това е теоретичната граница, до която дадено число може да бъде компресирано.

Вместо парадокса на Бери, сега можем да разгледаме подобен: Кое е най-малкото число, което една килобайтова програма не е достатъчна да изведе?

Ще разсъждаваме по същия начин както преди: има 2561024 килобайтови текстове, което означава, че не повече от 2561024 числа могат да бъдат изведени от килобайтови програми. Това означава, че определено число не по-голямо от 2561024 не може да бъде извлечено по този начин.

Но нека напишем програма на Python, която генерира всички възможни килобайтови текстове, изпълнява ги за изпълнение и ако изведат число, добавя това число към речника на достъпните. След като провери всичките 2561024 XNUMX XNUMX възможности, независимо колко време отнема, програмата търси най-малкото липсващо число в речника и го отпечатва. Изглежда очевидно, че такава програма ще се побере в килобайт код - и ще изведе точно това число, което не може да бъде изведено от килобайтова програма!

Каква е уловката сега? Вече не може да се дължи на неформалността на нотацията!

Ако сте объркани от факта, че нашата програма ще изисква астрономическо количество памет, за да работи - речник (или битов масив) от 2561024 елемента - тогава можете да направите същото без него: за всяко от 2561024 числа, на свой ред , преминете през всички 2561024 възможни програми, докато няма подходяща. Няма значение, че такова търсене ще продължи много дълго време: след проверка на по-малко от (2561024)2 двойки от номера и програмата, то ще приключи и ще намери това много ценно число.

Или няма да свърши? Наистина сред всички програми, които ще се пробват, ще има while True: pass (и неговите функционални аналози) - и въпросът няма да стигне по-далеч от тестването на такава програма!

За разлика от парадокса на Бери, където уловката беше в неформалността на нотацията, във втория случай имаме добре прикрита преформулация "спиране на проблеми". Факт е, че е невъзможно да се определи изходът му от програма за крайно време. По-специално, сложността на Колмогоров неизчислим: няма алгоритъм, който би позволил за дадено число да се намери дължината на най-кратката програма, която отпечатва това число; което означава, че няма решение на проблема на Бери - да намери дължината на най-краткото словесно обозначение за дадено число.

Източник: www.habr.com