Algoritamske definicije slučajnosti. Nepredvidivost, tipičnost i nekompresibilnost beskonačnih nizova

Uvođenje "algoritma" u Misesovu definiciju slučajnosti učinilo ju je matematički preciznom i cijelo je područje učinilo trajno "algoritamskim", piše Zvonimir Šikić u sedmom nastavku serijala o vjerojatnosti. Iako danas većina stručnjaka smatra da je Church-Turingova teza "bolje potvrđena", mnogi se nadaju da će Martin-Löf-Chaitinova teza s daljim radom dosegnuti istu razinu sigurnosti.

• Naslovna fotografija: Richard von Mises, austrijski znanstvenik i matematičar koji se prvi usredotočio na matematičku bit slučajnosti. (University of St. Andrews)

• Prethodni članci: Proširena logika vjerojatnosti. Počeci i suvremeni kontekst, Očekivanje u vjerojatnosti. Petrogradski paradoks i problem dvije omotnice, Kako je manje ispravna metoda zamijenila puno ispravniju. Laplace vs. Fisher, Klasična vjerojatnost i primjeri povijesnog razvoja, Vjerojatnost kao frekvencija, Vjerojatnost kao stupanj plauzibilnosti. Matematički temelji bejesovske teorije

• Slučajni procesi i slučajni produkti

Zamislite “crnu kutiju” koja svoje ishode proizvodi “slučajno” (prema nekoj fiksnoj konačnoj distribuciji vjerojatnosti).

CRNA KUTIJA  → ishod

Dakle, postoji konačan broj mogućih ishoda, recimo o₁, o₂, . . . , o_n i svaki ishod o_i ima fiksnu vjerojatnost 0 < p_i < 1. To je apstraktni model slučajnog eksperimenta. Poznati primjeri su bacanje novčića, okretanje ruleta u kockarnici, dnevno stanje vremenskih podataka, vrijeme između dva uzastopna klika Geigerovog brojača, dnevne vrijednosti indeksa burze, itd. Kockarnice, meteorologe, burzovne mešetare i teoretičare vjerojatnosti suočene s crnom kutijom, zanima je li ona slučajni uređaj, tj. proizvodi li ona svoje ishode slučajno (uz pridržavanje fiksne distribucije vjerojatnosti). To je pitanje slučajnosti procesa, koje zahtijeva temeljnu analizu samoga procesa.

Za dani niz ishoda crne kutije, može nas zanimati je li on slučajan ili nije, bez obzira na proces koji ga generira. Tada nas zanima pitanje slučajnosti produkta, a ne pitanje slučajnosti procesa i to je jedno od temeljnih pitanja filozofije vjerojatnosti i statistike. Što je niz dulji, to imamo više informacija za određivanje je li slučajan ili nije. U idealnom slučaju, nizovi su beskonačni. Razmotrit ćemo pitanje slučajnosti produkta u oba slučaja – konačnom i beskonačnom.

Mises je bio prvi koji je rigorozno obradio ovo pitanje za beskonačne nizove čime je pokušao frekvencijski utemeljiti teoriju vjerojatnosti. Naime, frekventisti odbijaju klasičnu definiciju vjerojatnosti, koja se temelji na razumijevanju slučajnosti procesa pozivom na neku njegovu simetriju. Umjesto toga, oni je žele utemeljiti u slučajnosti produkta, koja garantira postojanje graničnih frekvencija koje identificiraju s vjerojatnostima (usp. 2. članak Vjerojatnost kao frekvencija).

• Pseudo-slučajni nizovi

Prije nego se posvetimo slučajnim nizovima primijetimo da su nizovi često pseudo-slučajni, tj. iako se mogu činiti “statistički slučajnima”, možda postoji (skriveno) determinističko pravilo za njihovo generiranje. Naravno, ako postoji takvo pravilo  niz nije slučajan. (Primijetimo da obrat ne vrijedi. Na primjer, postoji neprebrojivo mnogo beskonačnih binarnih nizova čiji su svi bitovi na parnim pozicijama 0, dok su im oni  na neparnim pozicijama slučajni. Intuitivno je jasno da nijedan od tih nizova nije slučajan, iako nema pravila koje bi ih generirala.)

Iako nas ovdje ne zanimaju pseudo-slučajni nizovi oni su iznimno važni. Nedvojbeno korisni programi za slučajno generiranje brojeva primjer su pseudo-slučajnih nizova. Nezaobilazni su u simulacijama koje svakodnevno koriste mnoge znanstvene discipline. Na njima se temelje  tajni kodovi koje koriste sigurnosne agencije, banke, internetske transakcije itd. Kada se ispostavi da nisu dovoljno slučajni, rezultat je loša znanost i loša sigurnost. Povijest takvih neuspjeha duga je i zabrinjavajuća. Na primjer, pokazalo se da je jedan novi i poboljšani generator slučajnih brojeva u simulacijama statističke fizike davao rješenja koja se ne poklapaju s ispravnim rješenjima do kojih se moglo doći analitičkim putem. Isto tako, svi dobro znamo da se bankovne prijevare i sigurnosni proboji u računalne sustave prijavljuju svakodnevno. Nadalje, znamo za kockare koji zarađuju na činjenici da današnji automati za kockanje koriste vrlo jednostavne generatore slučajnih brojeva. Promatrajući tek nekoliko stotina povlačenja ručke ti su kockari u stanju odgonetnuti pravilo koje generira ishod. Zatim prate igru ​ do predviđenog jackpota, kada “slučajno” proliju kavu po trenutnom igraču pa, nakon „oprostite i uzmite ovaj čip od 100 dolara za čišćenje“, preuzmu igru i pokupe jackpot.

Ako kockarnice, bankari i znanstvenici ne mogu stvari učiniti kako treba, očito postoji neki problem. Naravno, problem je da su generatori brojeva deterministička pravila. Ona odabiru x₁ i potom računaju x_n+1 = f (x_n), pri čemu je f potpuno determinirana funkcija. Klasičan primjer iz 60-tih bio je f (n) = 65539 · n (mod 231)  i masovno je korišten, dok se nije pokazalo da točke čije su koordinate tri uzastopna “slučajna” broja, gotovo sve leže u jednoj ravnini. To je izrazito neslučajan ishod. George Marsaglia je 1968. dokazao da sva pravila koja koriste funkcije f iz iste opće klase imaju taj isti nedostatak, tj. nijedna funkcija iz te klase pravila ne prolazi test trodimenzionalnosti. Naravno, generator je to bolji što više testova prolazi, s tim da se slučajno generirani  brojevi koriste za različite probleme i neki su testovi ključni za neke probleme, a neki za neke druge.

Slučajni nizovi ne bi smjeli imati takvih problema.

• Laplaceov problem

Neka je crna kutija pošteni novčić koji proizvodi glave (1) i pisma (0). Pogledajmo niz od 70 ishoda tog slučajnog procesa. Takav niz ishoda je binarni niz duljine 70 i ukupni broj takvih nizova je 2⁷⁰. Ako je produciran niz

1001000100110011101100101010000011010000110001110001110011100011000111,

nismo iznenađeni. Držimo ga “slučajnim binarnim nizom” i smatramo da eksperiment funkcionira normalno. Ali ako je produciran niz

0101010101010101010101010101010101010101010101010101010101010101010101,

smatramo da se radi o neobičnom događaju, te opravdano sumnjamo u slučajnost procesa koji ga generira. Ali ovaj binarni niz savršeno pravilnih izmjena 0 i 1, jednako je vjerojatan kao i prvi navodno “slučajni” niz – oba imaju vjerojatnost 1/2⁷⁰ – pa ga stoga ne treba smatrati ništa neobičnijim od prvog niza. Ipak, intuitivna “pravilnost” drugog niza u nekom ga smislu čini mnogo manje slučajnim od prvoga. Laplace je bio svjestan ovog problema i upozorio je na sljedeći razlog zašto pravilni ishod slučajnog događaja intuitivno smatramo malo vjerojatnim:

“U igri glava-pismo, ako se glava pojavi stotinu puta zaredom to nam se čini neobičnim, jer gotovo beskonačan broj kombinacija koje mogu nastati u stotinu bacanja mi grupiramo u pravilne nizove, tj. one čije je pravilo generiranja lako shvatiti, i u nepravilne nizove [za koje to nije lako i] koji su neusporedivo brojniji.”

Dakle, među svim konačnim nizovima dovoljno velike duljine (recimo duljine 100) opažamo da postoji samo relativno mali broj “neslučajnih” nizova – nizova koji posjeduju neku “pravilnost”. Ostale nizove nazivamo slučajnima. Zato se čini da za dovoljno duge nizove postoji neko svojstvo koje odgovara intuitivnom pojmu slučajnosti. Ali kako ga točno definirati? To intuitivno svojstvo mogli bismo možda aproksimirati svojstvima opisanim uobičajenim jezikom teorije vjerojatnosti. Na primjer, zahtjev da duljine slogova identičnih ishoda budu u granicama koje precizira teorija vjerojatnosti, mogao bi eliminirati regularne nizovi s pravilnom izmjenom 0 i 1. Takva su svojstva stvarno formulirana kao statistički testovi za procjenu “pouzdanosti“ slučajnog karaktera konačnog niza bitova (usp. http://faculty.rhodes.edu/wetzel/random/intro.html). Međutim, čini se da su ti testovi dosta loše aproksimacije te da nijedno svojstvo formulirano uobičajenim jezikom teorije vjerojatnosti precizno ne obuhvaća svojstvo slučajnosti na intuitivno zadovoljavajući način.

• Glavni problemi i tri pristupa

Gornja razmatranja dovode nas do dva klasična pitanja filozofije vjerojatnosti i statistike:

Konačni problem: Kada je konačni niz bitova slučajan?

Beskonačni problem: Kada je beskonačni niz bitova slučajan?

Baviti ćemo se samo nizovima bitova 0 i 1, s vjerojatnostima Pr (0) = Pr (1) = 1/2, tj. naša će crna kutija uvijek biti bacanje savršeno poštenog novčića. Ovo se na prvi pogled može učiniti prestrogim ograničenjem, ali dodatna općenitost dobivena razmatranjem općih distribucija, ne daje dodatni uvid u pitanja slučajnosti. (Za one koji znaju nešto teorije mjere evo i objašnjenja. Ako pretpostavimo da naša crna kutija ima općenitiju distribuciju vjerojatnosti, s n ishoda o₁, o₂, . . . , o_n ∈ O i vjerojatnostima Pr (o_i) = p_i, onda postoji bijekcija između O^N i {0, 1}^N koja čuva mjeru. To je tehnički rezultat o konačnim Borelovim mjerama na potpunim separabilnim metričkim prostorima. Osim toga, ako su p₁, p₂, . . . , p_n  izračunljivi realni brojevi, tada se može pretpostaviti da je ova bijekcija izračunljiva. Kasnije ćemo vidjeti da je Martin-Löfova definicija slučajnosti dovoljno fleksibilna da se može izravno primijeniti i na opće distribucije. Međutim, spomenuti tehnički rezultat pokazuje da je matematički korektno ograničiti razmatranja na pojednostavljeni slučaj poštenog novčića.)

Rad Emilea Borela (lijevo) o normalnim brojevima iz 1909. i teorem Hermanna Weyla (desno) o njihovoj jednolikoj distribuciji iz 1916. preliminarne su formulacije slučajnosti za beskonačne nizove. (Creative Commons)

Većina ranih matematičkih rezultata koji se tiču ​​slučajnosti odnosila se na beskonačne nizove. Borelov rad o normalnim brojevima iz 1909. i Weylov teorem o njihovoj jednolikoj distribuciji iz 1916. preliminarne su formulacije slučajnosti za beskonačne nizove, ali je Mises bio taj koji je 1919. dao temeljnu definiciju. Churchovo uvođenje “algoritma” u Misesovu definiciju 1940. godine učinilo ju je matematički preciznom i cijelo je područje učinilo trajno “algoritamskim” (usp. 2. članak Vjerojatnost kao frekvencija). Za doista zadovoljavajući odgovor trebalo je čekati Martin-Löfa koji ga je pronašao 1965.

Rad na definiranju slučajnosti za konačne nizove pokrenuli su Solomonoff, Kolmogorov  i Chaitin 1960-tih. (Kao što je govorio Ulam “beskonačno ćemo riješiti odmah, konačno će potrajati malo duže”.) Također se pokazalo da su ta dva pojma usko povezana te da “izračunljivost” igra središnju ulogu u njihovim definicijama. Iako su se zadovoljavajući odgovori na oba problema pojavili gotovo istodobno sredinom 1960-ih, važno je napomenuti da se i danas ulažu napori da se definicija slučajnosti dodatno izoštri kroz mnoga istraživanja u području algoritamske slučajnosti.

Postoje tri ključna pristupa definiranje slučajnih nizova: nepredvidivost, tipičnost i nekompresibilnost.

Nepredvidivost. Beskonačni niz bitova je slučajan ako je nemoguće efektivno specificirati strategiju klađenja koja može donijeti dugoročne dobitke za kockara koji igra protiv tog niza (frekvencijsku verziju slučajnosti kao nepredvidljivosti uveo je Mises).

Tipičnost. Beskonačni niz bitova je slučajan ako nema specijalnih svojstava. Svojstvo zovemo specijalnim ako je vjerojatnost da ga niz ima jednaka nuli, a zovemo ga tipičnim ako je ta vjerojatnost jedan (dakle, radi se o komplementarnim svojstvima). Na primjer, svojstvo da beskonačni niz ne sadrži slogove od deset nula je specijalno jer je vjerojatnost da se to desi  nula. Nešto preciznije, beskonačni niz bitova je slučajan ako nema specijalnih svojstava koje je moguće efektivno opisati. Ovo je Martin-Löfova definicija slučajnosti (on je matematički precizirao pojam efektivne opisivosti u ovom kontekstu).

Nekompresibilnost. Konačni niz je slučajan ako njegov najkraći opis ima duljinu jednaku duljini samog niza, tj. ako se niz ne može komprimirati. Beskonačni binarni niz je slučajan ako se niti jedan njegov početni segmenat ne može “jako” komprimirati.

Na primjer, niz

0101010101010101010101010101010101010101010101010101010101010101010101,

može se kratko opisati, tj. komprimirati, s “01 ponovljeno 70 puta”. Ovaj pristup, poznat kao Kolmogorovljeva složenost, uveli su Solomonoff, Kolmogorov i Chaitin.

Ova tri pristupa definiranju slučajnosti čine se neovisnima i mogli bismo očekivati da dovedu do različitih pojmova slučajnosti. Stoga je činjenica da su (uz odgovarajuću definiciju efektivne opisivosti) sve tri definicije međusobno ekvivalentne, zaista iznenađujuća i snažan je argument da se radi o dobroj  matematičkoj definiciji slučajnosti.

• Nepredvidivost

Misesova definicija slučajnog niza

Richard von Mises prvi se usredotočio na matematičku bit slučajnosti. Za njega su slučajni nizovi (koje on zove “kolektivima”) temelj frekvencijskog shvaćanja vjerojatnosti, a temeljna mu je intuicija nepromjenjivost graničnih frekvencija dopuštenom selekcijom mjesta.

Da bismo razumjeli što to znači, pretpostavimo da kockar promatra ishode bacanja poštene kovanice i temeljeći svoju odluku na poznavanju prethodnih ishoda, odlučuje hoće li se kladiti u sljedećem bacanju.

Primjer 1: Kockar se kladi na svako treće bacanje (potpuno zanemarujući prethodne ishode).

Primjer 2: Kockar se kladi nakon bilo kojeg niza od tri uzastopne 0.

Bacanja na koja se kockar može kladiti Mises zove “mjestima”, a “strategiju” kojom kockar odabire mjesta na kojima će se kladiti zove “pravilom selekcije mjesta”. Ideja je da odabirom mjesta klađenja kockar ne može poboljšati svoje šanse za dobitak, one su i dalje ½, pa je Misesova definicija:

Niz je Mises-slučajan ako za sva dopuštena pravila selekcije mjesta, selektirani dio niza ima graničnu frekvenciju ½ kao i izvorni niz.

Mises točno ne specificira što je  “dopušteno”. Zahtijevao je da su dopuštena samo “efektivno odlučiva” pravila, iako nije precizno definirao što to znači (pojam odlučivog svojstva i izračunljive funkcije Alan Turing i Alonzo Church definirali su tek 1936.). No, bilo je jasno da su efektivno odlučiva pravila opisiva konačnim nizovima simbola iz konačne abecede, što znači da je skup tih pravila sigurno prebrojiv, a Abraham Wald je 1936. dokazao da Mises-slučajni nizovi postoje za svaki prebrojivi skup pravila selekcije.

Church je 1940. predložio upotrebu odlučivih svojstava za pravila selekcije mjesta što je rezultiralo sljedećom preciznijom definicijom:

Niz je odlučivo Mises-slučajan ako za sva odlučiva pravila selekcije mjesta, selektirani dio niza ima graničnu frekvenciju ½ kao i izvorni niz.

Ako je intencija da su pravila selekcije (efektivno) izbrojiva, a ne nužno odlučiva, to vodi na sljedeću definiciju:

Niz je izbrojivo Mises-slučajan ako za sva izbrojiva pravila selekcije mjesta, selektirani dio niza ima graničnu frekvenciju ½ kao i izvorni niz.

Napomena. Skup S je odlučiv ako postoji algoritam (npr. Turingov stroj) koji za svaki x odlučuje je li x iz S ili nije, a izbrojiv je ako postoji algoritam (npr. Turingov stroj) koji redom producira sve elemente x iz S. Lako je dokazati da je S odlučiv akko su i S i njegov komplement –S izbrojivi. Naime, za dani x čekamo da jedan od algoritama koji redom producira elemente iz S i –S producira x, pa ako to bude S onda je x iz S, a ako to bude –S onda x nije iz S.

Tako je 1940. godine predložena prva precizna matematička definicija slučajnog niza.

Očekujemo da svaki pojam slučajnog niza zadovoljava  zakone vjerojatnosti poput jakog zakona velikih brojeva, zakona simetričnih oscilacija (relativne frekvencije osciliraju oko granične relativne frekvencije) itd. Na primjer, lako je vidjeti da svaki Mises-slučajni niz zadovoljava jaki zakon velikih brojeva, jer je pravilo selekcije koje odabire sva mjesta očito odlučivo, a rezultirajući podniz je naprosto izvorni niz. To vrijedi i za mnoge druge zakone vjerojatnosti, ali veliki udarac Mises-Wald-Churchovoj definiciji zadao je Ville 1939. kada je dokazao da postoje Mises-slučajni nizovi koji ne zadovoljavaju zakon simetričnih oscilacija. Naime, postoji Mises-slučajni niz, čije je postojanje dokazao Ville, a čije relativne frekvencije ne osciliraju, nego se graničnoj relativnoj frekvenciji približavaju striktno odozgo. To krši zakon simetričnih oscilacija.

Primijetimo da Villeov primjer Mises-slučajnog niza koji se graničnoj frekvenciji 1-ca približava striktno odozgo dopušta dobitnu strategiju klađenja. Naime, ako se stalno kladite na 1-ce očito će vaš dobitak rasti preko svih granica (iako ne možete naći selekcijsko pravilo koje bi generiralo podniz s graničnom relativnom frekvencijom 1-ca, koja bi bila veće od 1/2). Dakle, ideja nepostojanja uspješne strategije klađenja protiv slučajnog niza nije potpuno opisana pravilima selekcije mjesta.

Slučajnost definirana martingalima

Definicije slučajnosti koje, poput  Misesove, zahtijevaju nepromjenljivost granične frekvencije podniza koji je generiran pravilom selekcije mjesta, u modernoj se matematičkoj literaturi nazivaju definicijama stohastičnosti. Ville je predložio definiciju, koja u matematiku uvodi pojam martingala i koja suzuje klasu slučajnih nizova, jer uzima u obzir općenitiji pojam strategije klađenja.

Grubo kazano, Villeova definicija uzima u obzir kapital koji kockar ulaže na pojedino mjesto i definira da njegova strategija uspijeva na nizu ishoda ako njegov kapital uz tu strategiju neograničen raste na tom nizu ishoda. Te strategije danas zovemo martingalima, a slučajni niz Ville definira kao onaj na kojem ne uspijeva nijedan efektivno generirani martingal. „Efektivno generiranje“ danas precizirano definiramo kao Church-Turingovu izračunljivost ili parcijalnu izračunljivost (naravno, parcijalno izračunljiva Ville-slučajnost implicira izračunljivu Ville-slučajnost, ali obrat ne vrijedi).

Dakle, martingal je strategija klađenja koja generalizira pravila selekcije mjesta. Svakom pravilu selekcije f odgovara posebno jednostavan martingal koji uvijek koristi konstantni dio trenutnog kapitala kao uloge na selektiranim mjestima. Taj martingal ne uspijeva na nekom nizu akko selektirani dio tog niza ima graničnu frekvenciju 1/2.

Dakle, klasa Ville-slučajnih nizova suzuje klasu Mises-slučajnih nizova i ona nema Villeov problem konvergencije odozgo. No, tek je trebamo opravdati kao pravu definiciju slučajnosti, jer možda postoje još općenitije strategije klađenja koje dodatno suzuju klasu slučajnih nizova. Jedna takva mogućnost su nemonotone strategije klađenja.

Nemonotone strategije klađenja

Da bismo razumjeli nemonotono klađenje koje su za martingale i pravila selekcije mjesta uveli Kolmogorov i Loveland 1960-tih, pretpostavimo da bitovi niza x = <x₁, x₂, . . . > leže pokriveni na beskonačno dugom stolu (usp. prostorno-vremensko bacanje kovanice u članku „Vjerojatnost kao frekvencija“). Kockar ih otkriva ne nužno rastućim redoslijedom i usput odlučuje na koji će se kladiti. Na primjer, može odlučiti prvo otkriti peto mjesto kako bi saznao x₅, zatim dvadeseto mjesto kako bi saznao x₂₀, a zatim se, na temelju ova dva opažanja, odluči kladiti na petnaesto mjesto. Nakon što otkrije x₁₅ (i dobije ili izgubi ovisno o tome je li točno predvidio x₁₅) kockar može izabrati što će sljedeće otkriti, ovisno o tome hoće li x₁₅ biti 0 ili 1, i tako dalje. Izostavljamo formalne detalje i nadamo se da prethodni neformalni opis dovoljno razjašnjava što je nemonotono klađenje. Primijenjeno na martingale ili na pravila selekcije mjesta, nemonotono klađenje vodi na sljedeće definicije.

Kolmogorov-Loveland-slučajni niz je onaj na kojem ne uspijeva nijedan izračunljivi nemonotoni martingal.

Kolmogorov-Loveland-stohastički niz je onaj čiji svaki podniz koji je odabran izračunljivim nemonotonim pravilom selekcije mjesta, ima graničnu frekvenciju  1/2.

Dobra značajka nemonotonih strategija klađenja je da nije važno koristimo li u gornjim definicijama “izračunljiv” ili “parcijalno izračunljiv”. U oba slučaja dolazimo do ekvivalentnih pojmova. Stoga nemonotone strategije klađenja imaju vrstu robusnosti koju nemaju monotone strategije, budući da je parcijalno izračunljiva Ville-slučajnost striktno jači pojam od izračunljive Ville-slučajnosti, a odlučiva Mises-slučajnost striktno je jači pojam od izbrojive Mises-slučajnosti.

Budući da su nemonotoni martingali općenitije strategije klađenja od monotonih, koji su pak općenitije strategije od pravila selekcije mjesta, njihove veze možemo opisati sljedećom tablicom u kojoj svaki pojam implicira onaj ispod njega i onaj desno od njega.

STRATEGIJE KLAĐENJA	NEMNOTONE IZRAČUNLJIVE	MONOTONE P. IZRAČUNLJIVE	MONOTONE IZRAČUNLJIVE
MARTINGALI	KOLMOGOROV SLUČAJNI NIZOVI	P. IZRAČUNLJIVI  VILLE SLUČAJNI NIZOVI	IZRAČUNLJIVI VILLE SLUČAJNI NIZOVI
SELEKCIJE MJESTA	KOLMOGOROV STOHASTIKE	IZBROJIVI MISES SL. NIZOVI (STOHASTIKE)	IZRAČUNLJIVI MISES SL. NIZOVI (STOHASTIKE)

• Tipičnost

Martin-Löfova definicija slučajnog niza

Slučajni niz možemo shvatiti kao onaj koji zadovoljava sve “probabilističke zakone slučajnosti”, tj. onaj koji ima sva “tipična svojstva slučajnosti”. Komplementarno, slučajni niz ne bi trebao imati nikakvih “specijalnih svojstava”, tj. ne bi smio pripadati nijednom skupu “mjere 0”. Ta je ideja pala na pamet mnogima, ali je nije bilo lako precizno formulirati (već smo upozorili da takvih nizova prima facie nema; npr. specijalno svojstvo „biti jednak samom sebi“ jest mjere 0, a ima ga svaki niz). Rješenje je, naravno, u tome da specijalna svojstva moraju biti efektivno zadana. Dakle, ključno je pitanje kako precizno definirati da je nešto “efektivno mjere 0”. Dvadeset pet godina nakon Mises-Wald-Churchove definicije, Martin-Löf je riješio ovaj ključni problem:

Niz je Martin-Löf-slučajan ako ne pripada nijednom skupu efektivne mjere 0, tj. ako pripada svim skupovima efektivne mjere 1.

Ako o efektivnom zakonu slučajnosti mislimo kao o skupu efektivne mjere 1 onda Martin-Löfova definicija glasi:

Niz je Martin-Löf-slučajan ako zadovoljava sve efektivne probabilističke zakone slučajnosti.

(Za one koji razumiju potrebne pojmove evo i Martin-Löfove precizne definicije:

Skup E ⊆ {0, 1}^N je izbrojive mjere 0 ako postoji uniformno izbrojivi niz unija otvorenih intervala G₁, G₂, G₃, . . . takav da za sve n, E ⊆  G_n i μ(G_n) < 1/n. Skup je efektivne mjere 1 ako je njegov komplement efektivne mjere 0. O skupovima G₁, G₂, G₃, . . . možemo misliti kao o uniformno izbrojivom nizu statističkih testova slučajnosti, sa sve većom i većom pouzdanošću.)

Martin-Löf je također dokazao važnu činjenicu da skup svih Martin-Löfovih slučajnih nizova ima efektivnu mjeru 1, tj. skup U nizova koji nisu Martin-Löf slučajni ima efektivnu mjeru 0.

(Za one koji razumiju potrebne pojmove dodajmo da to znači da postoji niz efektivno otvorenih skupova U₁,U₂,U₃, . . . takvih da je μ(U_n) < 1/n i U ⊆ ∩U_n. Ali ∩Un ⊆ U po definiciji pa je U = ∩Un, i stoga je niz <U_n> univerzalni test za Martin- Löf slučajnost, tj.

Niz x je Martin-Löf-slučajan ako za neki n, x ∉ U_n.

Ovaj univerzalni test daje posebno jednostavnu karakterizaciju Martin-Löf slučajnosti.

Za znalce možemo dodati još i ovo. Borel-Cantellijeva lema dokazuje da će u nizu događaja ±G₁, ±G₂, ±G₃, . . .  vjerojatnost da svaki od njih uspije samo konačno mnogo puta biti 1, ako je ∑Pr (+G_n) < ∞ (usp. kraj 6. članka u ovoj seriji Vjerojatnost kao proširena logika). Solovay je dokazao da ovaj “Borel-Cantellijev uvjet” karakterizira Martin- Löf slučajnost, pod uvjetom da se radi o nizu efektivno otvorenih skupova:

Niz x  je Martin-Löf-slučajan akko za svaki niz efektivno otvorenih skupova G₁, G₂, G₃, . . . sa svojstvom ∑μ (G_n) < ∞, niz x pripada samo konačnom broju G_n-ova.

Taj uvjet koji karakterizira Martin-Löf slučajnost poznat je kao Solovayeva slučajnost. Primijetite da se u Solovayevoj karakterizaciji pretpostavlja samo da beskonačni niz ∑μ(G_n) konvergira, tj. ne treba pretpostaviti da konvergira na efektivni način.)

• Nekompresibilnost

Berryjev paradoks

Do daljnjega ćemo se baviti konačnim nizovima. Sjetimo se Laplaceovog zapažanja da se među svim nizovima fiksne dovoljno velike duljine samo mali broj ravna prema nekom “pravilu koje je lako shvatiti“. Ostali su nepravilni i “neusporedivo brojniji” pa ih „smatramo slučajnima“. Problem je precizno formulirati ovo zapažanje. Sredinom 1960-ih riješili su ga Solomonoff, Kolmogorov i Chaitin, tako da su mjeru informativnosti, tj. složenosti konačnog binarnog niza, definirali kao duljinu njegovog “najkraćeg mogućeg opisa”. (To, naravno, vrijedi i za svaki drugi konačni objekt, jer se on uvijek može predstaviti konačnim binarnim nizom.) Ideja se temelji na intuiciji da će jednostavni objekti imati kratke opise koje složeni objekti neće imati.

Naravno, važno je precizno odrediti što se podrazumijeva pod “opisom”, jer neprecizna uporaba toga pojma uzrokuje probleme poput Berryjevog paradoksa:

Berryjev broj je najmanji prirodni broj neopisiv s manje od trinaest riječi.

Taj se broj po definiciji ne može opisati s manje od trinaest riječi. Ipak, gornja definicija ga opisuje koristeći samo dvanaest riječi i to je Berryjev paradoks. Problem je u svojstvu “biti opisan s manje od n riječi”, koje nije precizno definirano. Kakvo god bilo njegovo rješenje, Berryjev nas paradoks podsjeća da moramo biti oprezni kada govorimo o “opisu” broja ili niza. Zato su se Solomonoff, Kolmogorov i Chaitin ograničili na izračunljive opise u skladu sa sljedećom definicijom.

P-složenost konačnog niza

Neka je P program izračunljive funkcije, npr. Turingov stroj, a s konačni niz bitova. Niz d je P-opis niza s, ako program P primijenjen na „input“ d daje „output“ s.

d    →   P   →   s

Najkraći takav opis zovemo mjerom složenosti od s u odnosu na P. Evo i definicije.

P-složenost od s označavamo s C_P (s) i ona je duljina najkraćeg niza koji P-opisuje s, pod uvjetom da postoje takvi nizovi. Ako ne postoji niz koji P-opisuje s, onda je C_P (s) = ∞.

Postoje programi P takvi da je složenost C_P (s) konačna za sve nizove s. Takve programe zovemo konačnima (npr. program J koji izračunava funkciju identiteta je konačan). Kažemo da je niz s komprimiran pomoću programa P ako postoji P-opis od s koji je kraći od s. Općenitije, kažemo da je s b-komprimiran pomoću programa P ako postoji P-opis od s koji je za najmanje b bitova kraći od s. Dakle, s je komprimiran pomoću P ako je 1- komprimiran. Omjer |s|/C_P (s) zove se “faktor kompresije” niza s, s obzirom na P.

Lako je dokazati da postoje konačni programi P koji komprimiraju beskonačno mnogo nizova s proizvoljno velikim faktorima kompresije.

(Za one koji razumiju potrebne pojmove evo i dokaza. Ako ulazni niz d sadrži 0, program P ispisuje 1 i staje; inače P generira 2^|d| uzastopnih 1-ca i staje. Za tako definirani P, C_P (s) ≤ |s| pa je P konačan. Ako za bilo koji n, definiramo d_n = 1ⁿ i s_n = 1^m gdje je m = 2ⁿ, onda je d_n P-opis od s_n, C_P (s_n) = n i faktor kompresije niza s_n iznosi |s_n|/C_P (s_n) = 2ⁿ/n. Budući da za bilo koji broj a, možemo pronaći n takav da je 2ⁿ/n > a, slijedi da su svi nizovi s_n, s_n+1, . . . komprimirani za faktor veći od a; npr. program P komprimira niz s₆₄ za faktor 2⁵⁸).

S druge strane, lako je dokazati da je samo mali broj nizova moguće komprimirati. Naime, vrijedi sljedeći teorem.

Samo manje od polovice svih nizova duljine ≤ k može se komprimirati (bilo kojom metodom). Preciznije, manje od 1/2^b svih nizova duljine ≤ k može se b-komprimirati (bilo kojom metodom).

(Za one koji razumiju potrebne pojmove evo i dokaza. Neka je A skup svih nizova duljine ≤ k, B skup svih nizova duljine ≤ k − b, a C neka je skup svih onih nizova iz A koji se mogu b-komprimirati. Očito je |C| ≤ |B| pa je i |C|/|A| ≤ |B|/|A|. Osim toga |A| = 2^k+1 − 1 i |B| = 2^k−b+1 – 1 pa slijedi da je udio onih nizova u A koje je moguće b-komprimirati jednak

|C|/|A| ≤ |B|/|A| = (2^k−b+1 – 1) / (2^k+1 – 1) < 2^k−b+1 / 2^k+1 = 1/2^b.)

Na primjer, među nizovima koji imaju manje od tisuću bitova, više od 99,9% se ne može komprimirati za više od 9 bitova, bez obzira na metodu komprimiranja.

Naravno, zanimaju nas što kraći opisi, tj. što veći faktori kompresije. Stoga, među programima preferiramo one koji daju kraće opise, tj. veću kompresiju. Dakle, za programe P i Q, smatramo da je P “bolji” od Q ako C_P (s) ≤ C_Q (s) za sve nizove s. Nažalost, ne postoji “najbolji” program u tom smislu, jer se za svaki program može pronaći drugi koji smanjuje složenost (tj. bolje komprimira) proizvoljno mnogo nizova za proizvoljno velike iznose. Preciznije, za svaki program P i svaki m i n, postoji program Q takav da je C_Q (s) < C_P (s) –n, za najmanje m nizova s.

(Za one koji razumiju potrebne pojmove evo i dokaza. Neka je m = 2^k − 1 i neka su s₁, . . . , s_m različiti nizovi, za koje je C_P (s_j) > n + k. Takvi nizovi postoje, jer postoji samo konačno mnogo nizova za koje je C_P (s) ≤ n + k. Neka je a₁, . . . , a_m lista svih nizova duljine  k. Dizajnirajmo program Q koji sadrži kodirane kopije nizova s₁, . . . , s_m i radi na sljedeći način: Za ulaz a_j ispiše s_j i stane; za druge ulaze ukloni njegovih prvih k bitova i zatim oponaša program P s tim skraćenim unosom.)

Kolmogorovljeva C-složenost konačnog niza

Zbog prethodnog rezultata programe P i Q uspoređivat ćemo ​​korištenjem nešto slabije relacije „dostizanja u smislu složenosti“:

P dostiže Q ↔ postoji broj k takav da za sve nizove s vrijedi C_P (s) ≤ C_Q (s) +k.

Programe P i Q smatramo ekvivalentima u smislu složenosti ako svaki dostiže onog drugog, tj. ako je razlika između P-složenosti i Q-složenosti uniformno ograničena nekom konstantom.

Uz ove definicije postoji optimalni program U koji dostiže svaki drugi program. On je jedinstven, u smislu da mu je bilo koji drugi optimalni program ekvivalentan. Takve međusobno ekvivalentne programe zovemo univerzalnim programima.

To su nezavisno dokazali Solomonoff, Kolmogorov  i Chaitin 1960-tih.

Ako trajno fiksiramo jedan takav univerzalni i optimalni program U onda jednostavnu algoritamsku složenost niza s definiramo na sljedeći način.

Kolmogorovljeva složenost niza s je C (s) = C_U (s).

Budući da je optimalan, U dostiže program J čija je složenost C_j (s) = |s| pa za Kolmogorovljevu složenost C (s) vrijedi sljedeći teorem.

Postoji k takav da za sve nizove s vrijedi C (s) ≤ |s | + k.

C-slučajni konačni nizovi

Izuzetno je značajno da je  Kolmogorovljeva složenost C (s) u biti neovisna o modelu računanja. Zato je možemo smatrati mjerom informacijskog sadržaja niza s. To vodi na sljedeću formalnu definiciju.

Niz s je b-kompresibilan ako je C (s) ≤ |s |- b.

Niz s je kompresibilan ako je 1-kompresibilan, tj. ako je C (s) < |s|.

Niz s je C-slučajan ako nije kompresibilan.

Sada je lako dokazati sljedeći teorem.

Za svaki n postoje C-slučajni nizovi duljine n.

Dokaz: Neka je |s| = n i neka je d_s opis od s najmanje duljine. Nizova čija je duljina manja od n ima 2ⁿ – 1, dok nizova duljine n ima 2ⁿ. To znači da je | d_s | ≥ n za bar jedan s duljine n. Dakle C (s) ≥ n, tj. s je slučajni niz duljine n.

Kratki konačni nizovi, kao što je 111, mogu biti C-slučajni iako su prilično pravilni. To nije iznenađujuće. Ako je generirana bacanjem poštenog novčića, seriju 111  lako je prihvatiti kao slučajnu. Naravno, dugi niz od milijun jedinica ekstremno je neslučajan pa s pravom možemo sumnjati u slučajnost procesa koji ga generira.

Važno svojstvo Kolmogorovljeve složenosti je da nije izračunljiva.

Funkcija Kolmogorovljeve složenosti C nije izračunljiva.

Dokaz: Ako bi C bila izračunljiva onda bi se mogao definirati program P koji bi za svaki ulazni niz s izračunavao niz s* takav da je C (s*) > 2|s|. No, zbog univerzalnosti od C znamo da postoji konstanta k takva da je C (s) < C_P (s) + k, za sve s. Za niz s = 1^k+1 imali bismo C (s*) > 2|s|, ali budući da je s P-opis od s* imali bismo i C (s*) ≤ C_P (s*) + k ≤ |s| + k < 2|s|, što je kontradikcija.

Gödelova nepotpunost

U bilo kojoj formalizaciji matematike (npr. u ZFC teoriji skupova), relacija C (s) = n može se formalno izraziti. Koristeći varijantu Berryjevog argumenta i činjenicu da je skup teorema formalizirane teorije izbrojiv (izračunljivo prebrojiv), dokazat ćemo da je od svih istinitih tvrdnji oblika C (s) = n samo njih konačno mnogo dokazivo u toj teoriji. To je “informacijska verzija” Gödelovog teorema nepotpunosti, koju je dokazao Chaitin 1974. Dodatno dokazujemo da postoji “gornja ograda dokazive složenosti”.

Gödelov teorem nepotpunosti: Samo konačno mnogo tvrdnji oblika C (s) = n formalni su matematički teoremi. Postoji prirodni broj m takav da se ni za jedan konačni niz s ne može dokazati da ima složenost veću od m.

Dokaz: Neka je C (x, y) formula koja u formalnoj teoriji izražava “Kolmogorovljeva složenost od x je y“, a za svaki konačni niz s i prirodni broj n, neka su ‘s‘ i ‘n‘ njihova imena u toj teoriji. Budući da je skup teorema izbrojiv, postoji program P koji, pokrenut na ulaznom nizu d, pretražuje sve teoreme i provjerava je li neki oblika C (‘s‘, ‘n‘), sa n > 2|d|, i ako pronađe takav teorem onda ispisuje niz s i zaustavlja se. Nadalje, znamo da postoji broj k takav da je C (s) ≤ C_P (s) + k za sve s. Ako program P pokrenemo na ulaznom nizu 1^k, budući da postoji beskonačno mnogo n za koje je C (‘s‘, ‘n‘) teorem, P na kraju pronalazi takav teorem sa n > 2k, ispisuje niz s i zaustavlja se. Ako je C (‘s‘, ‘n‘) teorem onda je C (s) = n. Ali C (s) ≤ C_P (s) + k ≤ |1^k| + k = 2k < n, što je kontradikcija. Dakle, C (‘s‘, ‘n‘) nije teorem iako je C (s) = n.

Iako se može dokazati samo konačno mnogo istinitih tvrdnji C (s) = n, lako je vidjeti da se istinita tvrdnja C (s) ≤ n može dokazati za svaki niz s. Drugim riječima, iako ne možemo dokazati da je složenost niza s jednaka C (s), osim za konačno mnogo nizova s, za svaki niz s možemo dokazati da mu složenost ne prelazi C (s).

Chaitin-slučajni beskonačni nizovi

Kolmogorovljeva C-složenost daje zadovoljavajuću teoriju slučajnosti za konačne nizove. No, ne možemo je jednostavno proširiti do teorije slučajnosti za beskonačne nizove. Naime, složenost C (s_n) početnih segmenata s_n = <x₁, x₂, . . . , x_n> beskonačnog niza x = <x₁, x₂, x₃,. . . >, postaje neželjeno mala na beskonačno mnogo segmenata s_n  pa ne možemo reći da je beskonačni niz x slučajan ako su mu skoro svi konačni segmenti slučajni. Taj je fenomen poznat kao oscilacija složenosti. Razvijeno je nekoliko ideja za rješavanje tog problema, ali se tzv. prefiksna složenost, pokazala najboljom. Smislio ju je Levin, a objavio  Kolmogorov 1974 (do nje su kasnije nezavisno došli G´acs i Chaitin). To je sada standard koji se zove Kolmogorovljeva K-složenost. K je zapravo restrikcija od C, koja kao „komprimirane opise“ dopušta samo nizove koji imaju svojstvo jedinstvene čitljivosti koje ovdje nećemo objašnjavati. Uz taj pojam kompresibilnosti konačnih nizova moguće je dobro definirati kompresibilnost i slučajnost beskonačnih nizova:

Beskonačni niz je b-nekompresibilan ako je svaki njegov početni segment b-nekompresibilan.

Beskonačni niz je nekompresibilan ako je b-nekompresibilan za neki b (tj. ako se niti jedan njegov početni segment ne može komprimirati za više od fiksnog broja bitova).

Beskonačni niz je Chaitin-slučajan ako je nekompresibilan (tj. nijedan njegov početni segment ne može se komprimirati za više od fiksnog broja bitova).

(Napomena: Uz “Chaitin-slučajan” u literaturi se koriste izrazi “Levin-Chaitin-slučajan”, “Levin-Chaitin-Schnorr-slučajan”, „K-nekompresibilan“ itd.)

Definicija Chaitinove slučajnosti bitno je drugačija od Martin-Löfove. Slučajnost niza u Martin-Löfovom smislu ne definira se promatranjem samog niza, već pripadanjem toga niza svim efektivno otvorenim skupovima mjere 1. S druge strane, Chaitinova definicija slučajnosti niza ne poziva se na ništa drugo osim na sam taj niz i njegovu mjeru složenosti (tako što reducira definiciju slučajnosti beskonačnog niza na slučajnost njegovih konačnih segmenata i tako uspostavlja ključnu vezu između ta dva pojma).

Ova bitna razlika čini slavni Schnorrov teorem doista izvanrednim.

Schnorrov teorem. Beskonačni niz je Martin-Löf-slučajan akko je Chaitin-slučajan.

Ekvivalencija Martin-Löfove definicije s Chaitinovom definicijom jak je argument da te definicije uistinu dobro definiraju pojam slučajnosti za beskonačne nizove, te da su zadovoljavajuće rješenje tog klasičnog problema filozofije vjerojatnosti.

Zato ćemo Martin-Löf-slučajne nizove i njima ekvivalentne Chaitin-slučajne nizove, naprosto zvati slučajnim (beskonačnim) nizovima.

Martin-Löf-Chaitinova teza

Tvrdnja da Martin-Löfova slučajnost ili ekvivalentno Chaitinova slučajnost obuhvaća “pravi pojam slučajnosti” naziva se Martin-Löf-Chaitinovom tezom. Ona je analogna klasičnoj Church-Turingovoj tezi da Turing-Church-Post-Gödel- Herbrand izračunljivost obuhvaća “pravi pojam izračunljivosti”. Većina stručnjaka smatra da je Church-Turingova teza “bolje potvrđena”, jer je definicija izračunljivosti jednostavnija od definicije slučajnosti, ali se nadaju da će Martin-Löf-Chaitinova teza s vremenom dosegnuti razinu sigurnosti sličnu Church-Turingovoj tezi.

U posljednjih nekoliko desetljeća istraživačke aktivnosti u području algoritamske slučajnosti opsežne su i temeljite. Proučavane su mnoge definicije slučajnosti, ali nijedna nije evidentno bolja od Martin-Löf-Chaitinove. U usporedbi s drugima ona se čini optimalnom, ni preslabom ni prejakom. Uostalom, iako smatramo da je Church-Turingova teza dovoljno potvrđena, postoji veliki broj jačih i slabijih pojmova izračunljivosti koji se još uvijek proučavaju, jer imaju svoje svrhe.

Schnorrov teorem i dalje ostaje najjača potvrda Martin-Löf-Chaitinove teze, jer dokazuje ekvivalentnost prirodno formulirane “definicije tipičnosti”  u slučaju Martin- Löf-slučajnosti i prirodno formulirane “definicije nekompresibilnosti” u slučaju Chaitinove slučajnosti. Da su obje ekvivalentne s Villeovom “definicijom nepredvidivosti” (formuliranom pomoću efektivnih martingala) također je jak argument, iako mnogi misle da ta definicija nije dovoljno intuitivna, jer nije čisto frekvencijska poput Misesove. Osobno smatram da je ona bolja od Misesove, jer se bazira na bolje definiranom pojmu strategije klađenja.

Neriješeni problem, ima li Kolmogorov-Lovelandovih slučajnih nizova koji nisu Martin-Löf-Chaitin slučajni, neće uzdrmati Martin-Löf-Chaitinovu tezu, kako god da se riješi. Ako ih ima to će samo značiti da Kolmogorov-Lovelandova nemonotonost nije dovoljno jaka da karakterizira slučajne nizove, a ako ih nema to će tezu dodatno ojačati.

Ukratko, Martin-Löf-Chaitinova teza možda nije tako jako uvjerljiva kao Church-Turingova teza, ali ne bi nas trebalo čuditi da je definicija slučajnosti, koja u svim slučajevima pretpostavlja definiciju algoritma, nešto problematičnija od definicije samog algoritma.