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

Проблем компресије података, у свом најједноставнијем облику, може се односити на бројеве и њихове ознаке. Бројеви се могу означити бројевима ("Једанаест" за број 11), математички изрази ("два у двадесетом" за 1048576), стринг изрази ("пет деветки" за 99999), властита имена ("број звери" за 666, "година Турингове смрти" за 1954), или њихове произвољне комбинације. Погодна је свака ознака по којој саговорник може јасно одредити о ком броју говоримо. Очигледно, реците свом саговорнику "факторијал од осам" ефикасније од еквивалентне нотације "четрдесет хиљада триста двадесет". Овде се поставља логично питање: који је најкраћи запис за дати број?

Филозоф Бертран Расел објавио је 1908 "Беријев парадокс", који се дотиче питања записивања бројева са супротне стране: Који је најмањи број за који није потребно осамдесет слова?
Такав број мора постојати: од осамдесет руских слова и размака можете направити само 3480 ознака, што значи да помоћу осамдесет слова можете означити не више од 3480 бројева. То значи да је немогуће означити одређени број не више од 3480 на овај начин.

То значи да ће овај број одговарати ознаци "најмањи број за који осамдесет слова није довољно", који има само 78 слова! С једне стране, овај број мора постојати; с друге стране, ако овај број постоји, онда му његова ознака не одговара. Парадокс!

Најлакши начин да се одбаци овај парадокс је да се позове на неформалност вербалних нотација. На пример, када би у нотацији био дозвољен само посебно дефинисан скуп израза "најмањи број за који осамдесет слова није довољно" не би била ваљана нотација, док су практично корисне ознаке као "факторијал од осам" би остала прихватљива.

Постоје ли формални начини да се опише редослед (алгоритам) акција на бројеве? Има их, и то у изобиљу - зову се програмски језици. Уместо вербалних нотација, користићемо програме (на пример, у Пајтону) који приказују тражене бројеве. На пример, за пет деветки програм је погодан print("9"*5). И даље ћемо бити заинтересовани за најкраћи програм за дати број. Дужина таквог програма се зове Колмогоровска сложеност бројеви; то је теоријска граница до које се дати број може компримовати.

Уместо Беријевог парадокса, сада можемо размотрити сличан: Који је најмањи број за који програм од килобајта није довољан за излаз?

Резоноваћемо на исти начин као и раније: постоји 2561024 килобајтних текстова, што значи да килобајтни програми не могу да излазе више од 2561024 бројева. То значи да се одређени број не већи од 2561024 не може извести на овај начин.

Али хајде да напишемо програм у Питхон-у који генерише све могуће текстове у килобајту, покреће их за извршење и ако дају број, онда додаје овај број у речник доступних. Након провере свих 2561024 могућности, без обзира колико је потребно, програм тражи најмањи број који недостаје у речнику и штампа тај број. Чини се очигледним да ће се такав програм уклопити у килобајт кода – и да ће избацити баш онај број који не може да избаци програм од килобајта!

У чему је сада квака? То се више не може приписати неформалности нотације!

Ако сте збуњени чињеницом да ће нашем програму бити потребна астрономска количина меморије за рад - речник (или низ битова) од 2561024 елемената - онда можете да урадите исту ствар без њега: за сваки од 2561024 бројева, заузврат , прођите кроз свих 2561024 могућих програма, док не нађете ниједан одговарајући. Није важно што ће таква претрага трајати веома дуго: након провере мање од (2561024)2 пара из броја и програма, завршиће се и пронаћи тај веома драги број.

Или се неће завршити? Заиста, међу свим програмима који ће бити испробани, биће их while True: pass (и његови функционални аналози) - и ствар неће ићи даље од тестирања таквог програма!

За разлику од Беријевог парадокса, где је квака била у неформалности нотације, у другом случају имамо добро прикривену преформулацију "заустављање проблема". Чињеница је да је немогуће одредити његов излаз из програма у коначном времену. Конкретно, сложеност Колмогорова неурачунљив: не постоји алгоритам који би омогућио да се за дати број пронађе дужина најкраћег програма који штампа овај број; што значи да не постоји решење за Беријев проблем – пронаћи дужину најкраће вербалне ознаке за дати број.

Извор: ввв.хабр.цом