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

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

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

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

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

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

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

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

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

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

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

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

В отличие от парадокса на Бери, където уловката беше в неформалността на обозначенията, в този случай имаме добре замаскирана переформулировка на „проблема на спирането“. Факт е, че по програмата не може да се определи нейният изход за крайно време. В частност, колмогоровската сложност не е изчислимаНе съществува алгоритъм, който да позволи за дадено число да се намери дължината на най-кратката програма, която го извежда; следователно, няма решение и за задачата на Берри — да се намери за дадено число дължината на най-краткото словесно представяне.

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