Kolmogorovin monimutkaisuus

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 14. huhtikuuta 2022 tarkistetusta versiosta . tarkastukset vaativat 2 muokkausta .

Algoritmisessa informaatioteoriassa objektin (kuten tekstin ) Kolmogorov - monimutkaisuus on mitta laskentaresursseista, joita tarvitaan kohteen tarkkaan määrittelyyn.

Kolmogorov-kompleksisuus tunnetaan myös nimellä deskriptiivinen kompleksisuus, Kolmogorov -Khaitin- kompleksisuus , stokastinen kompleksisuus , algoritminen entropia tai algoritminen kompleksisuus .

Ilmaisee fraktaalikuvauksen mahdollisuuden.

Harkitse esimerkiksi kahta merkkijonoa, jotka ovat 64 merkin pituisia ja sisältävät vain pieniä kirjaimia ja numeroita:

abababababababababababababababababababababababababababababababababab 4c1j5b2p0cv4w1x8rx2y39umgw5q85s7uraqbjfdppa0q7nieieqe9noc4cvafzf

Ensimmäisellä rivillä on yksinkertainen kuvaus luonnollisella kielellä, eli ab 32 kertaa , joka koostuu 10 merkistä. Toisella rivillä ei ole selkeää yksinkertaista kuvausta, jossa käytetään samaa merkistöä, paitsi itse rivi, joka on 64 merkkiä pitkä.

Muodollisemmin merkkijonon monimutkaisuus on merkkijonon kuvauksen pituus jollakin yleismaailmallisella kuvauskielellä . Monimutkaisuuden kykyä muuttua kuvauskielen valinnan suhteen käsitellään alla. Voidaan osoittaa, että minkään merkkijonon Kolmogorov-kompleksisuus ei voi olla enempää kuin muutama tavu suurempi kuin itse merkkijonon pituus. Merkkijonoja, joiden Kolmogorov-monimutkaisuus riippuu heikosti itse merkkijonon koosta, ei pidetä kompleksina.

Määritelmä

Kolmogorovin monimutkaisuuden määrittelemiseksi meidän on ensin määritettävä merkkijonon kuvauskieli. Tällainen kuvauskieli voi perustua mihin tahansa ohjelmointikieleen , kuten Lisp , Pascal tai Java . Jos on ohjelma, jonka tulos on merkkijono , niin on kuvaus . Kuvauksen pituus on merkkijonon pituus. Pituutta määritettäessä selvitetään :ssä käytettyjen aliohjelmien pituudet . Minkä tahansa kohdassa esiintyvän kokonaislukuvakion pituus on bittien lukumäärä, joka vaaditaan esittämään , mikä on (karkeasti) . $P$ $x$ $P$ $x$ $P$ $P$ $P$ $n$ $P$ $n$ $\log _{2}n$

Vaihtoehtoisesti voimme valita Turingin koneelle koodauksen , jossa koodaus on funktio, joka kuvaa jokaisen Turingin koneen bittijonoon . Jos on Turingin kone, joka antaa merkkijonon syötteenä , niin yhdistetty merkkijono on kuvaus . Tämä on teoreettinen lähestymistapa, joka soveltuu paremmin yksityiskohtaisten muodollisten todisteiden rakentamiseen ja jota suositaan tutkimuskirjallisuudessa. Binäärinen lambdalaskenta voi antaa yksinkertaisimman määritelmän monimutkaisuudesta. Tässä artikkelissa otamme epävirallisen lähestymistavan. $M$ $\langle M\rangle$ $M$ $w$ $x$ $\langle M\rangle w$ $x$

Jokaisella rivillä on ainakin yksi kuvaus, eli ohjelma $s$

funktio GenerateFixedString() palauttaa s

Jos kuvaus , on minimipituinen, eli se käyttää vähiten merkkejä, niin sitä kutsutaan minimikuvaukseksi ja pituus , eli merkkien lukumäärä tässä kuvauksessa, on Kolmogorovin kompleksisuus , . Symbolisesti: $s$ $d(t)$ $s$ $d(t)$ $s$ $K(s)$

K(s)=|d(s)|.

Tarkastellaan, miten kuvauskielen valinta vaikuttaa arvoon , ja osoitetaan, että kuvauskielen muuttamisen vaikutus on rajallinen. $K$

Lause . Jos ja ovat monimutkaisuusfunktioita, jotka liittyvät kuvauskieliin ja , niin on olemassa vakio (riippuen vain kielistä ja ), joka $K_1$ $K_{2}$ $L_{1}$ $L_{2}$ $c$ $L_{1}$ $L_{2}$

\forall s|K_{1}(s)-K_{2}(s)|\leqslant c.

Todiste . Päinvastoin riittää osoittamaan, että on olemassa jokin vakio jokaiselle bittijonolle $c$ $s$

K_{1}(s)\leqslant K_{2}(s)+c.

Oletetaan, että kielellä on ohjelma, joka toimii tulkkina : $L_{1}$ $L_{2}$

funktio TulkitseLanguage( merkkijono p )

missä on kieliohjelma . Tulkille on ominaista seuraava ominaisuus: $s$ $L_{2}$

Syötetietojen käsittelyn tuloksena saatu palautusarvo on InterpretLanguagetyön tulos .

s

s

Jos siis on ohjelma kielellä , joka on minimikuvaus , niin ( ) palauttaa merkkijonon . Tämän kuvauksen pituus on summa: $P$ $L_{2}$ $s$ InterpretLanguage $P$ $s$ $s$

Ohjelman pituus InterpretLanguage, joka voidaan ottaa vakiona . $c$
Pituus , jonka määrittelee . $P$ $K_{2}(s)$

Tämä todistaa vaaditun ylärajan.

Historia ja konteksti

Algoritminen informaatioteoria on tietojenkäsittelytieteen ala, joka tutkii Kolmogorovin kompleksisuutta ja muita monimutkaisia merkkijonojen (tai muiden tietorakenteiden ) mittareita.

Ajatus Kolmogorovin kompleksisuusteoriasta perustuu avainlauseeseen, jonka ensimmäisenä löysi Ray Solomonoff , joka julkaisi sen vuonna 1960 ja kuvasi sitä julkaisussa A Preliminary Report on a General Theory of Inductive Inference [1] osana hänen keksintöään algoritmisesta todennäköisyydestä. . Hän antoi täydellisemmän kuvauksen julkaisuissaan "A Formal Theory of Inductive Inference" , osissa 1 ja 2 lehdessä Information and Control [2] [3] , julkaistu vuonna 1964.

Myöhemmin A. N. Kolmogorov julkaisi tämän lauseen itsenäisesti lehdessä Information Transmission Problems [4] , Gregory Khaitin esitteli myös tämän lauseen lehdessä J. ACM" . Khaitinin paperi lähetettiin lokakuussa 1966, tarkistettiin joulukuussa 1968, ja siinä lainataan sekä Solomonoffin että Kolmogorovin papereita. [5]

Lauseen mukaan algoritmien joukossa, jotka palauttavat (dekoodaavat) merkkijonoja niiden kuvauksista (koodeista), on yksi optimaalinen. Tämä algoritmi kaikille merkkijonoille antaa samat lyhytkoodit kuin muiden algoritmien antamat, vakion erolla, joka riippuu algoritmista, mutta ei itse merkkijonosta. Solomonoff käytti tätä algoritmia ja sen antamia koodin pituuksia määrittääkseen merkkijonojen "universaalin todennäköisyyden", johon merkkijonon myöhempien merkkien induktiivinen päättely voi perustua. Kolmogorov käytti tätä lausetta määrittämään useita merkkijonofunktioita: kompleksisuuden, satunnaisuuden ja informaation.

Kun Kolmogorov sai tietää Solomonoffin työstä, hän tunnusti prioriteettinsa [6] . Useiden vuosien ajan Solomonoffin työ tunnettiin paremmin Neuvostoliitossa kuin lännessä. Tiedeyhteisössä on kuitenkin yleistä yhdistää tämän tyyppinen monimutkaisuus Kolmogoroviin, joka puhui sekvenssien satunnaisuudesta, kun taas algoritminen todennäköisyys on liitetty Solomonoffiin, joka keskittyi ennustamiseen käyttämällä universaalia ennakkotodennäköisyysjakaumaa.

Kolmogorovin monimutkaisuudesta tai algoritmisesta tiedosta on joitain muita muunnelmia. Yksi laajimmin käytetyistä perustuu itserajoittuviin ohjelmiin ja liittyy pääasiassa L. A. Leviniin (1974). M. Burgin (1982) esitteli aksiomaattisen lähestymistavan Kolmogorovin kompleksisuuteen, joka perustuu Bloomin (1967) aksioomeihin.

Jotkut ihmiset ajattelevat, että nimi "Kolmogorov-kompleksisuus" on esimerkki Matteuksen efektistä [7] .

Tärkeimmät seuraukset

Seuraavassa päättelyssä tarkoitamme merkkijonon monimutkaisuutta . $K(s)$ $s$

On helppo nähdä, että merkkijonon minimikuvaus ei voi olla suurempi kuin itse merkkijono: yllä oleva ohjelma GenerateFixedString, jonka tulos on kiinteällä määrällä suurempi . $s$ $s$

Lause . On olemassa jatkuva sellainen $c$

\forall s\,K(s)\leqslant |s|+c.

Kolmogorovin monimutkaisuuden laskemattomuus

Ensimmäinen seuraus on, ettei ole tehokasta tapaa laskea . $K$

Lause . on laskematon funktio . $K$

Toisin sanoen mielivaltaisen merkkijonon algoritmisen monimutkaisuuden laskentaongelma on algoritmisesti ratkaisematon - ei ole ohjelmaa, joka ottaisi syötteenä ja tulostaisi kokonaisluvun . Osoitetaan tämä ristiriitaisesti luomalla ohjelma, joka luo merkkijonon, jonka voi luoda vain pidempi ohjelma. Oletetaan, että on olemassa ohjelma $s$ $s$ $K(s)$

funktio KolmogorovComplexity ( merkkijono )

joka ottaa syötteenä ja palauttaa . Mieti nyt ohjelmaa $s$ $K(s)$

funktio GenerateComplexString( int n ) arvolle i = 1 äärettömään : jokaiselle merkkijonolle s , jonka pituus on täsmälleen i, jos KolmogorovComplexity( s ) >= n return s quit

Tämä ohjelma kutsuu aliohjelmaa KolmogorovComplexity. Ohjelma yrittää jokaista riviä alkaen lyhyimmästä, kunnes se löytää rivin, jonka monimutkaisuus on vähintään , jonka se palauttaa. Siksi, jos mikä tahansa positiivinen kokonaisluku , se tuottaa merkkijonon, jonka Kolmogorov-monimutkaisuus on vähintään . Tällä ohjelmalla on oma kiinteä pituus . Ohjelman syöte on kokonaisluku ja koko mitataan sen esittämiseen tarvittavien bittien lukumäärällä, joka on . Harkitse seuraavaksi seuraavaa ohjelmaa: $n$ $n$ $n$ $U$ GenerateComplexString $n$ $n$ $\log _{2}n$

funktio GenerateParadoxicalString() return GenerateComplexString(n 0 )

Tämä ohjelma kutsuu GenerateComplexStringkuin aliohjelma ja sillä on myös vapaa parametri . Tämä ohjelma tulostaa merkkijonon , jonka monimutkaisuus on vähintään . Parametrin suotuisalla valinnalla pääsemme ristiriitaan. Jos haluat valita tämän arvon, huomaa, että sen kuvaa ohjelma, jonka pituus ei ole suurempi kuin $n_{0}$ $s$ $n_{0}$ $n_{0}$ $s$ GenerateParadoxicalString

U+\log _{2}n_{0}+C,

jossa vakio lisätään ohjelman takia . Koska se kasvaa nopeammin kuin , on olemassa sellainen arvo , että $C$ GenerateParadoxicalString $n$ $\log _{2}n$ $n_{0}$

U+\log _{2}n_{0}+C<n_{0}.

Mutta tämä on ristiriidassa sen määritelmän kanssa, että monimutkaisuus on vähintään . Eli määritelmän mukaan ( ) on sallittua, että GenerateParadoxicalString-ohjelman palauttama merkkijono voidaan luoda ohjelman avulla, jonka pituus on tai suurempi, mutta lyhyempi kuin . Joten ohjelma ei voi laskea satunnaisen merkkijonon monimutkaisuutta. $n_{0}$ $s$ $s$ $n_{0}$ GenerateParadoxicalString $n_{0}$ KolmogorovComplexity

Tämä on todiste ristiriitaisuudesta, jossa ristiriita on samanlainen kuin Berryn paradoksi : "Olkoon pienin positiivinen kokonaisluku, jota ei voida kutsua alle kahdellakymmenellä englanninkielisellä sanalla." [8] On myös mahdollista osoittaa laskemattomuus vähentämällä laskemattomuus pysäytysongelmaksi , koska ja ovat Turingin ekvivalentteja. [9] $n$ $K$ $H$ $K$ $H$

Ohjelmointiyhteisössä on seuraus, joka tunnetaan nimellä täyskäyttölause , jonka mukaan ei ole olemassa täydellisesti kokoon optimoitua kääntäjää.

Kolmogorov-kompleksisuuden ketjusääntö

Kolmogorovin kompleksisuuden ketjusääntö sanoo sen

K(X,Y)=K(X)+K(Y\mid X)+O{\big (}\log K(X,Y){\big )}.

Siinä todetaan, että lyhin ohjelma, joka toistaa ja on korkeintaan suurempi kuin toistava ohjelma , ja ohjelma, joka toistaa, on annettu . Tätä lauseketta käyttämällä voidaan määritellä keskinäisen informaation analogi Kolmogorovin kompleksisuudelle. $X$ $Y$ $\log K(X,Y)$ $X$ $Y$ $X$

Pakkaus

Ylärajan laskeminen on helppoa: sinun tarvitsee vain pakata merkkijono jollain menetelmällä, toteuttaa sopiva dekompressori valitulla kielellä, liittää dekompressori pakattuun merkkijonoon ja mitata tuloksena olevan merkkijonon pituus. $K(s)$ $s$

Merkkijono on pakattu, jos sillä on kuvaus, jonka pituus ei ylitä . Tämä vastaa lausuntoa . Jos tätä ei tehdä, sitä ei pakkaa . Merkkijonoa, joka ei ole pakattavissa luvulla 1, kutsutaan yksinkertaisesti pakkaamattomaksi; Dirichlet'n periaatteen mukaan kokoonpuristumattomia merkkijonoja on oltava, koska on olemassa bittijonoja, joiden pituus on , mutta vain merkkijonoja, joiden pituus on pienempi kuin [10] . $s$ $c$ $|s|-c$ $K(s)\leqslant |s|-c$ $s$ $c$ $2^{n}$ $n$ $2^{n}-1$ $n$

Samasta syystä useimmat merkkijonot ovat monimutkaisia siinä mielessä, että niitä ei voida merkittävästi pakata: ei paljon vähemmän kuin pituus bitteinä. Selvyyden vuoksi korjataan arvo . Siellä on pituisia bittijonoja . Tasainen todennäköisyysjakauma näiden bittijonojen avaruudessa määräytyy täsmälleen yhtä suurella painokertoimella jokaiselle pituudelle . $K(s)$ $|s|$ $s$ $n$ $2^{n}$ $n$ $2^{{-n}}$ $n$

Lause . Todennäköisyys, että merkkijonoa ei pakata , on vähintään yhtä suuri kuin tasainen todennäköisyysjakauma pituisten bittijonojen avaruudessa . $c$ ${\näyttötyyli 1-2^{-c+1}+2^{-n))$ $n$

Tämän lauseen todistamiseksi huomaamme, että pituuskuvausten määrä ei ylitä , joka saadaan geometrisesta progressiosta : $n.c.$

1+2+2^{2}+\ldots +2^{nc}=2^{n-c+1}-1.

Jää ainakin

2^{n}-2^{n-c+1}+1

bittijonoja, joita ei voi puristaa . Määritä todennäköisyys jakamalla . $c$ $2^{n}$

Khaitinin epätäydellisyyslause

Tiedämme, että kaikkien mahdollisten merkkijonojen joukossa useimmat merkkijonot ovat monimutkaisia siinä mielessä, että niitä ei voida kuvata millään riittävän ytimekkäästi. Osoittautuu kuitenkin, että sitä tosiasiaa, että tietty merkkijono on monimutkainen, ei voida todistaa muodollisesti, jos merkkijonon monimutkaisuus ylittää tietyn kynnyksen. Tarkka formalisointi on esitetty alla. Aluksi korjaamme tietyn aksiomaattisen järjestelmän luonnollisille luvuille . Aksiomaattisen järjestelmän on oltava riittävän tehokas, jotta tarkka arvio merkkijonon monimutkaisuudesta voidaan kuvata aksiomaattisen järjestelmän kaavaan . Tällä vastaavuudella on oltava seuraava ominaisuus: jos se johdetaan aksioomista , niin vastaava lause on tosi. ${\mathbf {s))$ $\mathbf {A}$ ${\mathbf {F}}_{{\mathbf {A}}}$ $s$ ${\mathbf {F}}_{{\mathbf {A}}}$ ${\mathbf {s))$ $\mathbf {A}$

Lause . On olemassa sellainen vakio (joka riippuu vain tietystä aksiomaattisesta järjestelmästä ja valitusta kuvauskielestä), että mille tahansa riville lause $L$

K(s)\geqslant L

sisällä ei voida todistaa . ${\mathbf {s))$

Kuitenkin, kuten on helppo ymmärtää, lause pätee äärettömälle määrälle rivejä tai pikemminkin kaikille paitsi äärelliselle määrälle rivejä. $K(s)\geqslant L$

Lauseen todistus perustuu Berryn paradoksissa käytettyyn itseviittauskonstruktioon . Todistus ristiriidalla. Jos lause ei pidä paikkaansa, niin

Oletus (X) : Jokaiselle kokonaisluvulle on merkkijono , jolle on olemassa johdannainen kaavasta " " (jolle oletimme, että se voidaan formalisoida muodossa ).

n

s

{\mathbf {s))

K(s)\geqslant n

{\mathbf {s))

Harkitse ohjelmaa, joka toteuttaa tehokkaan kaikkien muodollisten todisteiden luettelon ${\mathbf {s))$

funktio NthProof( int n )

joka ottaa n :n syötteeksi ja tuottaa jonkin verran todisteita. Jotkut niistä todistavat kaavan, kuten " ", jossa s ja n ovat vakioita kielessä . On olemassa ohjelma, joka tarkistaa, vahvistaako n:s todistus kaavan " ": $K(s)\geqslant n$ ${\mathbf {s))$ $K(s)\geqslant L$

toiminto NthProofProvesComplexityFormula( int n )

Päinvastoin, merkkijono s ja luku L voidaan laskea ohjelmien avulla

funktio StringNthProof( int n ) funktio ComplexityLowerBoundNthProof( int n )

Harkitse nyt seuraavaa ohjelmaa:

funktio GenerateProvablyComplexString( int n ) arvolle i = 1 äärettömään: jos NthProofProvesComplexityFormula(i) ja ComplexityLowerBoundNthProof(i) ≥ n palauttaa StringNthProof( i )

Kun syötteenä on n , tämä ohjelma tarkistaa jokaisen todisteen, kunnes se löytää jonkin merkkijonon s ja todisteen kaavasta K ( s ) ≥ L jollekin L ≥ n :lle . Tämä ohjelma pysähtyy Arvaa (X) . Olkoon tämän ohjelman pituus U . On olemassa luku n 0 , jolloin U + log 2 n 0 + C < n 0 , missä C on ohjelman lisäpituus

toiminto GenerateProvablyParadoxicalString() return GenerateProvablyComplexString( n 0 )

Huomaa, että myös numero n 0 on koodattu tähän ohjelmaan, mikä vaatii loki 2 ( n 0 ) -tiedot. GenerateProvablyParadoxicalString -ohjelma tuottaa merkkijonon s , jolle on olemassa L , joten K ( s ) ≥ L voidaan päätellä , missä L ≥ n 0 . Erityisesti K ( s ) ≥ n 0 on totta sille . Kuitenkin s voidaan kuvata ohjelmalla, jonka pituus on U + log 2 n 0 + C , joten sen kompleksisuus on pienempi kuin n 0 . Tuloksena oleva ristiriita todistaa oletuksen (X) virheellisyyden . ${\mathbf {s))$

Samanlaisia ajatuksia käytetään todistamaan Chaitinin vakion ominaisuudet .

Viestin vähimmäispituus

Sanoman vähimmäispituuden periaatteen tilastollisessa ja induktiivisessa päättelyssä ja koneoppimisessa kehittivät Wallace ( englanniksi CS Wallace ) ja Bolton ( englanniksi DM Boulton ) vuonna 1968. MDS-periaate on Bayesin (sisältää aiemmat todennäköisyydet) ja informaatioteoreettinen. Sillä on toivottavat ominaisuudet: tilastollinen invarianssi (päätelmämuunnos uudelleenparametrisoinnilla), tilastollinen liitettävyys (jopa erittäin vaikeassa ongelmassa periaate konvergoi taustalla olevaan malliin) ja tehokkuus (MDS-periaatteeseen perustuva malli konvergoi mihin tahansa pätevään taustalla oleva malli mahdollisimman nopeasti). Wallace ja Dowe ( eng. DL Dowe ) osoittivat muodollisen suhteen MDS-periaatteen ja algoritmisen informaatioteorian (tai Kolmogorov-kompleksisuuden) välillä.

Kolmogorovin mahdollisuus

Kolmogorovin satunnaisuuden (myös algoritmisen satunnaisuuden) määritelmän mukaan merkkijono sanotaan satunnaiseksi silloin ja vain, jos se on lyhyempi kuin mikään sen toistamiseen kykenevä tietokoneohjelma. Tämän määritelmän tarkentamiseksi yleistietokone (tai universaali Turingin kone ) on korjattava, jotta "tietokoneohjelma" tarkoittaisi tuon yleiskoneen ohjelmaa. Tässä mielessä satunnainen merkkijono on "pakkautumaton". Dirichlet-periaatteella on helppo osoittaa, että mille tahansa yleiskoneelle on olemassa minkä tahansa pituisia algoritmisesti satunnaisia merkkijonoja, mutta merkkijonon ominaisuus olla algoritmisesti satunnainen riippuu yleiskoneen valinnasta.

Tämä määritelmä voidaan laajentaa äärettömän aakkoston äärettömiin merkkijonoihin. Määritelmä voidaan ilmaista kolmella vastaavalla tavalla. Ensimmäinen tapa käyttää tehokasta mittateorian analogia; toinen käyttää tehokasta martingaalia . Kolmas tapa määritellä se on tämä: ääretön sekvenssi on satunnainen, jos sen alkusegmentin Kolmogorov-kompleksisuus kasvaa riittävän nopeasti — on olemassa vakio c siten, että minkä tahansa n pituisen alkusegmentin kompleksisuus on vähintään n − c . Osoittautuu, että tämä määritelmä, toisin kuin äärellisen merkkijonon satunnaisuuden määritelmä, ei riipu yleiskoneen valinnasta.

Suhde entropiaan

Brudnon lauseen mukaan dynaamisen järjestelmän entropia ja siinä olevien lentoratojen algoritminen monimutkaisuus liittyvät relaatioon lähes kaikille . [yksitoista] $K(x;T)=h(T)$ $x$

Voidaan osoittaa [12] , että Markovin tietolähteen työn tuloksen Kolmogorov-kompleksisuus liittyy sen entropiaan . Tarkemmin sanottuna Markovin tietolähteen lähdön Kolmogorov-kompleksisuus, normalisoituna lähdön pituuksiin, konvergoi lähes aina lähteen entropiaan.

Muistiinpanot

↑ Solomonoff, Ray Alustava raportti yleisestä induktiivisen päättelyn teoriasta // Raportti V-131 : aikakauslehti. - Cambridge, Ma.: Zator Co., 1960. - 4. helmikuuta. versio Arkistoitu1. elokuuta 2020Wayback Machinessa, marraskuuta 1960.
↑ Solomonoff, Ray. Induktiivisen päättelyn muodollinen teoria Osa I // Informaatio ja ohjaus : päiväkirja. - 1964. - Maaliskuu ( osa 7 , nro 1 ) . - s. 1-22 . - doi : 10.1016/S0019-9958(64)90223-2 .
↑ Solomonoff, Ray. Induktiivisen päättelyn muodollinen teoria Osa II // Informaatio ja ohjaus : päiväkirja. - 1964. - Kesäkuu ( osa 7 , nro 2 ) . - s. 224-254 . - doi : 10.1016/S0019-9958(64)90131-7 .
↑ Kolmogorov, A. N. Kolme lähestymistapaa "informaation määrän" käsitteen määritelmään // Tiedonsiirron ongelmat: päiväkirja. - 1965. - T. 1 , nro 1 . - S. 3-11 . (Venäjän kieli)
↑ Chaitin, Gregory J. Luonnollisten lukujen äärettömien joukkojen laskemiseen tarkoitettujen ohjelmien yksinkertaisuudesta ja nopeudesta // Journal of the ACM : Journal. - 1969. - Voi. 16 . - s. 407 . - doi : 10.1145/321526.321530 . Arkistoitu alkuperäisestä 25. elokuuta 2011.
↑ Kolmogorov, A. Tietoteorian ja todennäköisyysteorian looginen perusta (englanti) // IEEE Transactions on Information Theory : päiväkirja. - 1968. - Voi. 14 , ei. 5 . - s. 662-664 . - doi : 10.1109/TIT.1968.1054210 .
↑ Li, Ming; Paul Vitani. Johdatus Kolmogorov-monimutkaisuuteen ja sen sovelluksiin . – 2. - Springer, 1997. - ISBN 0387948686 .
↑ Alkuperäinen: "Olkoon pienin positiivinen kokonaisluku, jota ei voida määritellä alle kahdellakymmenellä englanninkielisellä sanalla". $n$
↑ Peter Bro Miltersen. Kurssin muistiinpanot tietojen pakkaamisesta. 2. Kolmogorovin monimutkaisuus (pääsemätön linkki) . Haettu 17. helmikuuta 2011. Arkistoitu alkuperäisestä 9. syyskuuta 2009. (määrätön)
↑ Koska on olemassa pituisia merkkijonoja, pituisten merkkijonojen lukumäärä on , joka on äärellinen geometrinen progressio , jonka summa on yhtä suuri . $n_{L}=2^{L}$ $L$ $L=0,\ldots ,(n-1)$ ${\displaystyle n_{0}+n_{1}+\ldots +n_{n-1}=2^{0}+2^{1}+\ldots +2^{n-1))$ $2^{0}+2^{1}+\ldots +2^{n-1}=2^{0}\times (1-2^{n})/(1-2)=2 ^{n}-1$
↑ Arkistoitu kopio . Haettu 6. kesäkuuta 2013. Arkistoitu alkuperäisestä 26. joulukuuta 2011. (määrätön)
↑ http://arxiv.org/pdf/cs.CC/0404039

Kirjallisuus

Vereshchagin N.K. Kolmogorov-kompleksin kulku .
Vereshchagin N. K., Shen V. A. Kolmogorov monimutkaisuus ja algoritminen satunnaisuus . – MTsNMO, 2013.
Vyugin VV Kolmogorov - monimutkaisuus ja algoritminen satunnaisuus .

Sanakirjat ja tietosanakirjat	iso kiinalainen Universalis