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

Проблемот со компресија на податоци, во наједноставна форма, може да се однесува на броевите и нивните ознаки. Броевите може да се означат со бројки ("единаесет" за бројот 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 (и неговите функционални аналози) - и работата нема да оди подалеку од тестирање на таква програма!

За разлика од Бериовиот парадокс, каде што уловот беше во неформалноста на ознаката, во вториот случај имаме добро прикриена преформулација „запирање на проблемите“. Факт е дека е невозможно да се одреди неговиот излез од програма во одредено време. Особено, комплексноста на Колмогоров непресметливи: не постои алгоритам кој би овозможил, за даден број, да се најде должината на најкратката програма што го печати овој број; што значи дека нема решение за проблемот на Бери - да се најде должината на најкратката вербална ознака за даден број.

Извор: www.habr.com