Kolmogorov komplexitet

Från Wikipedia
Hoppa till: navigering, sök

Kolmogorov komplexitet (engelska Kolmogorov Complexity) av ett objekt, såsom en text-sträng, är ett mått på beräkningsresurserna som krävs för att specificera objektet eller med andra ord ett mått på hur kaotiskt objektet är. Det tillhör området Algoritmisk informations teori och är döpt efter Andrey Kolmogorov som publicerade artiklar under 60-talet på ämnet [1].

Om vi begrundar följande två strängar:

101010101010101010101010101010101010101010
111000110100011111100001001010001001010000

För den som endast tittar på dessa strängar är det trivialt vilken av dessa som är mer kaotisk. Den första strängen kan kort beskrivas som "10" skrivet 21 gånger. Den andra strängen blir däremot svårare att beskriva och har därmed en högra Kolmogorov komplexitet än den första. Som det formellt beskrivs nedan så mäter Kolmogorov komplexiteten den minsta resurserna som behövs för att beskriva ett objekt. Men, komplexiteten kan inte beräknas utan endast approximeras uppifrån.

Definition[redigera | redigera wikitext]

Säg att vi har objektet τ, en beskrivning av denna kan då sägas vara något ω om,

 f(\omega)=\tau .

Den formella versionen av Kolmogorov komplexitet är

C(x) = \begin{cases}
  min_p{|p|:U(p)=x}, & \mbox{if } x \in \mbox{ran }f \\
  \infty  & \mbox{otherwise,}
\end{cases}

där U är en Universell Turing Maskin, dvs en maskin som kan simulera en godtycklig maskin för godtycklig indata.

Egenskaper[redigera | redigera wikitext]

1.  C(x) \leq |x|+c, c är konstant.
2.  C(xx) \leq C(x) + c
3. För alla delvis beräknebara h är C(h(x)) \leq C(x) + c_h , där ch är längden av en beskrivning av h.
4.  C(x|y)\leq C(x) + c

Kolmogorov slump[redigera | redigera wikitext]

Sats: För alla n, existerar det något x där |x| = n, så att C(x) \leq n. Detta x kallar vi för kolmogorov slump.
Bevis: Antag motsatsen. Då är  C(x) < n för alla x. Alltså måste det existera ett program px, g(p_x) = x och |p_x| < n. Om  x \neq y så är heller ej p_x \neq p_y. Men det finns 2^n -1 program med kortare längd än n, och 2^n strängar av längden n. Om alla strängar av längd n har ett program som är kortare än n, då måste det finnas ett program som producerar två strängar. Uppenbarligen är det omöjligt och därav måste det finnas minst en sträng av längd n som har ett program av minst längden n.

Applikationsområden[redigera | redigera wikitext]

Kolmogorov komplexitet kan tillämpas i ett stort antal områden, bland annat har det tillämpats i

  • Per Martin-Löfs test för slumpmässighet, informations teori för individuella objekt
  • allmän sannolikhet, induktivt resonemang och interferens, förutsägbarhet
  • Kombinatorik, okompressibilitetsmetoden, grafteori
  • logiskt djup, universell optimal sökning, beräkningstermodynamik, statistisk termodynamik och Boltzmann entropi

m.fl

Till exempel kan Kolmogorv komplexitet tillämpas för att bevisa ett antal klassiska satser, som i följande exempel där teorin används för att bevisa att det finns oändligt många primtal.
Bevis för oändligt antal primtal: Antag först motsatsen, att det finns ett ändligt antal primtal. I så fall kan vi säga att det finns det k stycken primtal, p1, p2,...,pk för k  \in \N. Vi kan då ta ett tal m \in \N och skriva det som en produkt av primtalen  m = {p_1}^{e_1}* ...*{p_k}^{e_k}. Låt m vara Kolmogorov slumpen av längden n. Vi kan påstå att det ger en kort beskrivning av m. Först för att e_i \leq \log{m}. Då är |e_i| \leq \log{m}. Vilket ger |\langle e_1,...,e_k \rangle | \leq 2k\log{\log{m}}. Därav då  m \leq 2^{n+1} och |\langle e_1,...,e_k \rangle | \leq 2k\log{n+1} så blir C(m) = 2k \log{n+1} +c. Då m är slumpmässigt val så blir C(m) \geq n falskt för stora n.

Historik[redigera | redigera wikitext]

Kolmogorov komplexitet gjordes känd av matematikern Andrey Kolmogorov, men definierades tidigare av Raymond J. Solomonoff som en del i hans arbete kring algoritmisk informationsteori [2] och matematisk induktion och även senare av Gregory J. Chaitin som formulerade en riktig definition i den artikel han publicerade 1969[3]. Motivationen till Kolmogorovs arbete var informationsteoretisk och inriktad på slump/kaos medan Solomonoff var motiverat av matematisk induktion.

Paralleller till entropi[redigera | redigera wikitext]

I somliga fall kallas teorin för algoritmisk entropi. Detta härrör från att entropi i ett system är ett mått på systemets kaos. Inom informationsteori refererar entropi vanligast till Shannons entropi som delar flertalet egenskaper med Kolmogorov komplexitet.

Referenser[redigera | redigera wikitext]

  1. ^ Kolmogorov, Andrey (1963). ”On Tables of Random Numbers”. Sankhyā Ser. A. "25": sid. 369–375. 
  2. ^ Solomonoff, Ray (February 4, 1960). ”A Preliminary Report on a General Theory of Inductive Inference” (PDF). Report V-131 (Cambridge, Ma.: Zator Co.). http://world.std.com/~rjs/rayfeb60.pdf.  revision, Nov., 1960.
  3. ^ doi: 10.1145/321526.321530
    Den här DOI-referensen kommer automatiskt att kompletteras under de närmaste minuterna. Du kan gå före i kön eller expandera för hand