Tento obrázek ilustruje část Mandelbrotova množinového fraktálu. Pouhé uložení 24-bitové barvy každého pixelu v tomto obrázku by vyžadovalo 1,62 milionu bitů, ale malý počítačový program dokáže těchto 1,62 milionu bitů reprodukovat pomocí definice Mandelbrotovy množiny a souřadnic rohů obrázku. Kolmogorovova složitost surového souboru kódujícího tuto bitmapu je tedy mnohem menší než 1,62 milionu.
Vezměme si například následující dva řetězce o délce 64, z nichž každý obsahuje pouze malá písmena a číslice:
První řetězec má krátký anglický popis, konkrétně „ab 32 times“, který se skládá z 11 znaků. Druhý řetězec nemá žádný zřejmý jednoduchý popis (používá stejnou znakovou sadu) kromě zápisu samotného řetězce, který má 64 znaků.
Formálněji, složitost řetězce je délka nejkratšího možného popisu řetězce v nějakém pevném univerzálním jazyce popisu (citlivost složitosti vzhledem k volbě jazyka popisu je popsána níže). Lze ukázat, že Kolmogorovova složitost jakéhokoli řetězce nemůže být větší než několik bajtů než délka samotného řetězce. Řetězce, jako příklad ababu výše, jejichž Kolmogorovova složitost je malá vzhledem k velikosti řetězce, nejsou považovány za složité.
Pojem Kolmogorovovy složitosti může být použit ke zjištění a prokázání výsledků nemožnosti podobně jako Gödelova věta o neúplnosti a Turingova problém zastavení.
Abychom definovali Kolmogorovovu složitost, musíme nejprve zadat popisný jazyk pro řetězce. Takový popisný jazyk může být založen na jakémkoli programovacím jazyce počítače, jako je například Lisp, Pascal nebo Java virtual machine bytecode. Pokud P je program, který vypisuje řetězec x, pak P je popis x. Délka popisu je pouze délka P jako znakového řetězce, vynásobená počtem bitů ve znaku (např. 7 pro ASCII).
Mohli bychom alternativně zvolit kódování pro Turingovy stroje, kde kódování je funkce, která asociuje ke každému Turingovu stroji M bitstring . Pokud M je Turingův stroj, který na vstupu w, výstupy řetězec x, pak zřetězený řetězec w je popis x. Pro teoretickou analýzu je tento přístup vhodnější pro konstrukci detailních formálních důkazů a je obecně preferován ve výzkumné literatuře. V tomto článku je diskutován neformální přístup.
Každý řetězec s má alespoň jeden popis, a to program:
Je-li popis s, d(s) minimální délky (tj. používá nejméně znaků), nazývá se minimální popis s. Tedy délka d(s) (tj. počet znaků v popisu) je Kolmogorovova složitost s, psané K(s). Symbolicky,
Délka nejkratšího popisu bude záviset na volbě jazyka popisu; ale vliv změny jazyků je ohraničen (výsledek se nazývá invarianční věta).
Existují však některé jazyky popisu, které jsou optimální, v následujícím smyslu: vzhledem k jakémukoliv popisu objektu v jazyce popisu, mohu tento popis použít ve svém optimálním jazyce popisu s konstantní režií. Konstanta závisí pouze na použitých jazycích, nikoli na popisu objektu nebo popisovaného objektu.
Zde je příklad optimálního jazyka popisu. Naše popisy budou mít dvě části:
V odbornější terminologii je první část popisu počítačový program, přičemž druhá část je vstup do tohoto počítačového programu, který produkuje objekt jako výstup.
Na invariance věta vyplývá: Vzhledem k tomu, jakýkoli popis jazyk , Naše optimální popis jazyk je alespoň stejně efektivní jako , S některými konstantní režie.
Důkaz: Pokud máme popis v , můžeme jej převést do popisu v našem optimálním jazyce tak, že nejprve popíšeme jako počítačový program (část 1), a poté použijeme původní popis jako vstup do tohoto programu (část 2). The
celková délka tohoto nového popisu je (přibližně):
Délka je konstanta, která nezávisí na . Takže, tam je nanejvýš konstantní režie, bez ohledu na objekt se snažíme popsat. Z toho vyplývá, že náš optimální jazyk je univerzální až do této aditivní konstanty.
Důkaz: Podle symetrie, stačí dokázat, že existuje nějaké konstantní c taková, že pro všechny bitstrings
Nyní předpokládejme, že existuje program v jazyce L1, který funguje jako tlumočník pro L2:
kde p je program v L2. Interpret je charakterizován touto vlastností:
Pokud tedy P je program v L2, který je minimálním popisem s, pak InterpretLanguage(P) vrací řetězec s. Délka tohoto popisu s je součtem
To dokazuje požadovanou horní hranici.
Algoritmická teorie informace je oblast informatiky, která studuje Kolmogorovovu složitost a další měřítka složitosti na strunách (nebo jiných datových strukturách).
Koncept a teorie Kolmogorovovy komplexnosti je založen na zásadní větě, kterou poprvé objevil Ray Solomonoff, který ji publikoval v roce 1960 a popsal ji v „Předběžné zprávě o obecné teorii indukční pravděpodobnosti“ jako součást svého vynálezu algoritmické pravděpodobnosti. Podrobnější popis uvedl ve svých publikacích z roku 1964 „Formální teorie indukční pravděpodobnosti“, část 1 a část 2 v Informacích a řízení.
Věta říká, že mezi algoritmy, které dekódují řetězce z jejich popisů (kódů), existuje jeden optimální. Tento algoritmus pro všechny řetězce umožňuje kódy tak krátké, jak to dovoluje kterýkoli jiný algoritmus, až po aditivní konstantu, která závisí na algoritmech, ale ne na řetězcích samotných. Solomonoff použil tento algoritmus a délky kódu, které umožňuje, k definování „univerzální pravděpodobnosti“ řetězce, na které může být založena induktivní dedukce následných číslic řetězce. Kolmogorov použil tuto větu k definování několika funkcí řetězců, včetně složitosti, náhodnosti a informace.
Když se Kolmogorov dozvěděl o Solomonoffově práci, uznal Solomonoffovu prioritu. Po několik let byla Solomonoffova práce známější v Sovětském svazu než v západním světě. Všeobecný konsenzus ve vědecké obci však byl spojit tento typ složitosti s Kolmogorovem, který se zabýval náhodností sekvence, zatímco Algoritmická pravděpodobnost se stala spojována s Solomonoffem, který se zaměřil na predikci pomocí svého vynálezu univerzálního rozdělení pravděpodobnosti.
Existuje několik dalších variant Kolmogorovovy složitosti nebo algoritmické informace. Nejrozšířenější z nich je založena na samoohraničujících programech a je hlavně zásluhou Leonida Levina (1974).
Axiomatický přístup ke Kolmogorovově složitosti založený na Blumových axiomech (Blum 1967) byl zaveden Markem Burginem v dokumentu předloženém ke zveřejnění Andrejem Kolmogorovem (Burgin 1982).
Někteří se domnívají, že pojmenování konceptu „Kolmogorovova složitost“ je příkladem Matthewova efektu.
V následující diskusi, ať K(s) je složitost řetězce s.
Není těžké vidět, že minimální popis řetězce nemůže být příliš větší než samotný řetězec – program GenerateFixedString výše, že výstupy s je pevná částka větší než s.
Věta: Existuje konstantní c taková, že
Nesrovnatelnost Kolmogorovovy složitosti
Prvním výsledkem je, že neexistuje způsob, jak vypočítat K.
Věta: K není vyčíslitelná funkce.
Jinými slovy, neexistuje žádný program, který by vzal jako vstup řetězec s a jako výstup vytvořil celé K(s). Ukážeme to rozporem tím, že vytvoříme program, který vytvoří řetězec, který by měl být schopen vytvořit pouze delší program. Předpokládejme, že existuje program
který bere jako vstup řetězec s a vrací K(s). Nyní zvažte program
Tento program nazývá KolmogorovComplexity jako podprogram. Program zkouší každý řetězec, počínaje tím nejkratším, dokud nenajde řetězec se složitostí alespoň n (pokud nějaký existuje), pak tento řetězec vrátí (nebo přejde do nekonečné smyčky, pokud žádný takový řetězec neexistuje). Je zřejmé, že pro každé n existuje vždy alespoň jeden takový řetězec, protože jinak by všechny možné řetězce (nekonečně mnoho) mohly být generovány programy (konečně mnoho) s menší složitostí, takže GenerateComplexString se musí vždy vrátit. Proto, pokud je zadáno jakékoliv kladné celé n, vytvoří řetězec s Kolmogorovovou složitostí alespoň tak velkou jako n. Samotný program má pevnou délku U. Vstup do programu GenerateComplexString je celé n. Zde se velikost n měří počtem bitů požadovaných pro reprezentaci n, což je log2(n). Nyní zvažte následující program:
Tento program nazývá GenerateComplexString jako podprogram a má také volný parametr
n0. Program vypíše řetězec s, jehož složitost je alespoň n0. Příznivou volbou parametru n0 dojdeme k rozporu. Pro volbu této hodnoty si povšimněte, že s je popsáno programem GenerateParadoxicalString, jehož délka je nejvýše
kde C je „režie“ přidaná programem GenerateParadoxicalString. Protože n roste rychleji než log2(n), musí existovat hodnota n0 taková, že
To je ale v rozporu s definicí ‚s‘, které má složitost alespoň n0. To znamená, že podle definice K(s) má být řetězec s vrácený GenerateParadoxicalString generován pouze programem o délce n0 nebo delší, ale GenerateParadoxicalString je kratší než n0. Program s názvem „KolmogorovComplexity“ tedy nemůže ve skutečnosti výpočetně nalézt složitost libovolných řetězců.
To je důkaz rozporem, kde rozpor je podobný Berryho paradoxu: „Nechť n je nejmenší kladné číslo, které nemůže být definováno v méně než dvaceti anglických slovech“. Je také možné ukázat non-vyčíslitelnost K snížením z non-vyčíslitelnost zastavující problém H, protože K a H jsou Turingovy-ekvivalent.
V komunitě programovacích jazyků existuje důsledek známý jako věta o plné zaměstnanosti, která uvádí, že neexistuje dokonalý kompilátor optimalizující velikost.
Řetězové pravidlo pro Kolmogorovovu složitost
Řetězové pravidlo pro Kolmogorovovu složitost uvádí, že
Uvádí, že nejkratší program, který reprodukuje X a Y, není větší než logaritmický termín, než program na reprodukci X a program na reprodukci Y dané X. Pomocí tohoto tvrzení lze definovat analogii vzájemné informace pro Kolmogorovovu složitost.
Věta: S jednotným rozložení pravděpodobnosti na prostoru bitstrings délky n, pravděpodobnost, že řetězec je nestlačitelný o c je alespoň .
bitstrings délky n, které jsou nestlačitelné c. Chcete-li určit pravděpodobnost, vydělte .
Chaitinova věta o neúplnosti
Víme, že v množině všech možných řetězců je většina řetězců komplexní v tom smyslu, že je nelze popsat žádným výrazně „komprimovaným“ způsobem. Ukázalo se však, že skutečnost, že určitý řetězec je komplexní, nelze formálně prokázat, pokud je složitost řetězce nad určitým prahem. Přesná formalizace je následující. Nejprve opravte konkrétní axiomatickou soustavu S pro přirozená čísla. Axiomatická soustava musí být dostatečně mocná, aby bylo možné k určitým tvrzením A o složitosti řetězců přiřadit vzorec FA v S. Toto přiřazení musí mít následující vlastnost:
Pokud je FA prokazatelná z axiomů S, pak musí být odpovídající tvrzení A pravdivé. Této „formalizace“ lze dosáhnout buď umělým kódováním, jako je Gödelovo číslování, nebo formalizací, která jasněji respektuje zamýšlenou interpretaci S.
Věta: Existuje konstantní L (která závisí pouze na konkrétním axiomatickém systému a volbě jazyka popisu) taková, že neexistuje řetězec s, pro které je příkaz
Všimněte si, že při hojnosti téměř nesrozumitelných strun musí být naprostá většina těchto tvrzení pravdivá.
Důkaz tohoto výsledku je modelován podle sebe-referenciální konstrukce použité v Berryho paradoxu. Důkazem je rozpor. Pokud by věta byla nepravdivá, pak
Můžeme najít efektivní výčet všech formálních dokladů v S nějakým postupem
který bere jako vstup n a vypíše nějaký důkaz. Tato funkce vyjmenovává všechny důkazy. Některé z nich jsou důkazy pro vzorce, které nás zde nezajímají, protože každý možný důkaz v jazyce S je vyroben pro některé n. Některé z nich jsou složité vzorce tvaru K(s) ≥ n kde s a n jsou konstanty v jazyce S. Existuje program
který určuje, zda n-tý důkaz skutečně dokazuje složitost vzorce K(s) ≥ L. Řetězce, a celé číslo L zase, jsou vypočítatelné programy:
Zvažte následující program
Pokud je zadáno n, tento program zkouší každý důkaz, dokud nenajde řetězec a důkaz ve formálním systému S vzorce K(s) ≥ L pro nějaké L ≥ n. Program končí naším Předpokladem (X). Nyní má tento program délku U. Existuje celé číslo n0 takové, že U + log2(n0) + C < n0, kde C je režijní cena
(všimněte si, že n0 je pevně zakódováno do výše uvedené funkce a summand log2(n0) již umožňuje jeho kódování). Program GenerateProvablyParadoxicalString vypisuje řetězec s, pro který existuje L takové, že K(s) ≥ L může být formálně prokázáno v S s L ≥ n0. Zejména K(s) ≥ n0 je pravdivé. Nicméně, s je také popsáno programem o délce U + log2(n0) + C, takže jeho složitost je menší než n0. Tento rozpor dokazuje Předpoklad (X) nemůže obstát.
Podobné myšlenky se používají k prokázání vlastností Chaitinovy konstanty.
Princip minimální délky zprávy pro statistickou a induktivní inferenci a strojové učení byl vyvinut C.S. Wallacem a D.M. Boultonem v roce 1968. MML je bayesovské (tj. zahrnuje předchozí přesvědčení) a informačně teoretické. Má žádoucí vlastnosti statistické invariance (tj. inferenční transformace s re-parametrizací, např. z polárních souřadnic na kartézské souřadnice), statistické konzistence (tj. i pro velmi těžké problémy se MML přiblíží k jakémukoli základnímu modelu) a efektivity (tj. MML model se přiblíží k jakémukoli skutečnému základnímu modelu asi tak rychle, jak je to možné). C.S. Wallace a D.L. Dowe (1999) ukázali formální spojení mezi MML a algoritmickou teorií informace (nebo Kolmogorovovou složitostí).
Tato definice může být rozšířena tak, aby definovala pojem náhodnosti pro nekonečné posloupnosti z konečné abecedy. Tyto algoritmicky náhodné posloupnosti mohou být definovány třemi ekvivalentními způsoby. Jeden způsob používá efektivní analogii teorie měření, jiný efektivní martingales. Třetí způsob definuje nekonečnou posloupnost, která má být náhodná, pokud předpona-bez Kolmogorovovy složitosti jeho počátečních segmentů roste dostatečně rychle – musí existovat konstantní c taková, že složitost počátečního segmentu o délce n je vždy nejméně n−c. Tato definice, na rozdíl od definice náhodnosti pro konečný řetězec, není ovlivněna tím, který univerzální stroj je použit k definici předpony-bez Kolmogorovovy složitosti.
U dynamických systémů je míra entropie a algoritmická složitost trajektorií spojena s Brudnovou větou, že rovnost K(x;T) = h(T) platí pro téměř všechna x.