Student World

Toto číslo je pravděpodobně náhodné:

10097325337652013586346735487680959091173929274945…

Zároveň je však i zvláštní – začíná jím kniha z roku 1955 s názvem A Million Random Digits (Milion náhodných číslic). Společnost RAND Corporation získala tyto číslice „elektronickou ruletou“ – pomocí pulsního generátoru, který za vteřinu vydával 100 000 pulsů, jež procházely pětimístným binárním čítačem a dále převaděčem z binární do desítkové soustavy. Dekadickými číslicemi pak byl naplněn děrnoštítkový stroj IBM a vytiskly se na účtovacím stroji IBM 856 Cardatype. Celý proces trval řadu let. Při testování první sady číslic statistici zjistili závažné odchylky – číslice nebo jejich skupiny či struktury, které se objevovaly příliš často nebo naopak příliš málo. Nakonec však tabulky vyšly. Redakce zahořkle poznamenala: „Kvůli samotné povaze tabulek se nám nezdálo nutné, abychom k vychytání náhodných chyb Cardatypu museli kontrolovat každou stránku poslední verze.“

Kniha šla na odbyt – vědci potřebovali k práci náhodná čísla ve velkém množství. Používali je k návrhům statisticky neutrálních experimentů a k budování realistických modelů komplexních systémů. Nová simulační metoda Monte Carlo využívala náhodného výběru vzorků k vytvoření jevu, který se nedal řešit analyticky. Metodu Monte Carlo vymyslel a pojmenoval von Neumannův tým, když se při projektu realizace atomové bomby zoufale snažil vygenerovat náhodná čísla, která by pomohla vypočítat neutronovou difuzi. Von Neumann si uvědomil, že mechanický počítač se svými deterministickými algoritmy a konečnou pamětí nikdy nemůže vygenerovat skutečně náhodná čísla. Musel se spokojit s pseudonáhodnými čísly – jednalo se o deterministicky vygenerovaná čísla, která se chovala jako náhodná. Pro praktické účely byla náhodná dostatečně. Von Neumann prohlásil: „Každý, kdo uvažuje o tom, že by aritmetickými metodami vytvářel náhodná čísla, se jistě nachází ve stavu hříchu.“

Náhodnost je možné definovat z hlediska řádu – vlastně jeho nepřítomnosti. Následující uspořádanou posloupnost čísel můžeme sotva nazvat náhodnou:

00000,

přestože se uprostřed slavného milionu náhodných čísel vyjímá jako drahokam. Z hlediska pravděpodobnosti to lze očekávat: „00000“ se může vyskytnout se stejnou pravděpodobností jako kterýkoli z dalších 99 999 možných pětimístných řetězců. Na jiném místě v milionu náhodných číslic nacházíme:

010101.

I toto se zdá složené podle vzorce.

Rozeznat fragmenty struktury v této džungli čísel vyžaduje inteligentního pozorovatele. Máme-li dostatečně dlouhý náhodný řetězec, někde se v něm objeví jakýkoli dostatečně krátký podřetězec. Jednou to bude kombinace k bankovnímu trezoru, podruhé zase zakódované celé Shakespearovo dílo. Nepřinesou však žádný užitek, protože je nikdo nenajde.

Snad můžeme říci, že čísla jako 00000 a 010101 mohou být náhodná v určitém kontextu. Když si někdo dostatečně dlouho hází mincí (což je jeden z nejjednodušších mechanických generátorů náhodných čísel), v jednu chvíli mu desetkrát za sebou padne panna. Jakmile se to stane, hledač náhodných čísel obvykle výsledek zavrhne a odejde na kávu. To je pouze jeden příklad toho, jak špatně si lidé při generování náhodných čísel počínají, dokonce s mechanickou pomocí. Výzkumy zjistily, že lidská intuice nemůže náhodnost ani předpovědět, ani rozpoznat. Lidé chtě nechtě tíhnou k pravidelnosti. Newyorská veřejná knihovna knihu A Million Random Digits zakoupila a zařadila ji mezi psychologické publikace. Ještě v roce 2010 byla na Amazonu ke koupi za 81 dolarů.

Číslo, jak již nyní víme, představuje informaci. Když my, moderní lidé a Shannonovi dědicové, uvažujeme o informaci v její nejčistší podobě, možná si představíme řetězec nul a jedniček, binární číslo. Zde vidíme dva binární řetězce s 50 číslicemi:

A: 01010101010101010101010101010101010101010101010101

B: 10001010111110101110100110101000011000100111101111

Když budou Alice (A) i Bob (B) tvrdit, že vygenerovali své řetězce házením mincí, Alici nikdo neuvěří. Je jisté, že řetězce nejsou stejně náhodné. Běžná teorie pravděpodobnosti nenabízí žádný podstatný důvod k tvrzení, že B je náhodnější než A, protože náhodný proces mohl vytvořit kterýkoli ze dvou řetězců. Pravděpodobnost se týká celků, ne jednotlivých dějů. Teorie pravděpodobnosti zpracovává děje statisticky. Nemá ráda otázky typu: „Jaká pravděpodobnost byla, že se to stane?“ Pokud se to stalo, stalo se.

Claudu Shannonovi by tyto řetězce připadaly jako zprávy. Zeptal by se: Jaké množství informace obsahuje každý řetězec? Každý zjevně obsahuje 50 bitů.

Telegrafista, který si účtuje podle počtu znaků, by změřil délku obou zpráv a naúčtoval Alici i Bobovi stejně. Na druhou stranu se však obě zprávy od sebe významně liší. Zpráva A nás okamžitě začne nudit – jakmile zjistíme vzorec, další opakování nepřináší žádnou novou informaci. Ve zprávě B má každý bit stejnou hodnotu jako všechny ostatní. Shannonova první verze teorie informace zpracovávala zprávy statisticky, jako volby z celku všech možných zpráv – jichž v případě A i B bylo 250. Ale Shannon bral v úvahu i ve zprávě skrytou redundanci – vzorec, pravidelnost či řád, který by dovolil zprávu zkrátit. Čím je ve zprávě více pravidelnosti, tím je předvídatelnější. A čím je předvídatelnější, tím je redundantnější. Čím je zpráva redundantnější, tím menší je její informační obsah.

Telegrafista, který odesílá zprávu A, má k dispozici zkratku – může vysílat něco ve stylu: „Pětadvacetkrát opakujte ‚01‘.“ V případě dlouhých zpráv se snadnými vzorci se ušetří obrovské množství úderů telegrafního klíče. Jakmile je vzorec jasný, znaky navíc jsou zdarma. Telegrafista, který odesílá zprávu B, se musí prodírat trnitou cestou a odesílat každý znak, protože ten vždy představuje dokonalé překvapení; každý znak má cenu jednoho bitu. Ukazuje se, že dvě otázky – jak náhodná a jaké množství informace – jsou stejné. Je na ně jediná odpověď.

Chaitin však nepřemýšlel o telegrafech. Zařízení, které mu stále leželo v hlavě, byl Turingův stroj – ta nemožně elegantní abstrakce, která se posouvá tam a zpět po nekonečné papírové pásce a čte a zapisuje symboly. Je zbavena nepořádku skutečného světa, skřípání kol, výpadků elektřiny i potřeby rychlosti– zkrátka se jedná o ideální počítač. I von Neumann se neustále vracel k Turingovým strojům. Byly ideální laboratorní myší teorie počítačů. Turingův stroj U měl transcendentní schopnost – univerzální Turingův stroj může simulovat jakýkoli jiný digitální počítač, a informatici si tak nemusí všímat zapeklitých detailů každého konkrétního typu či modelu. Přináší to pocit osvobození.

Claude Shannon, který se z Bell Labs přestěhoval do MIT, v roce 1956 Turingův stroj znovu analyzoval. Rozebral ho až na samotné jádro a dokázal, že univerzální počítač lze zhotovit s pouhými dvěma vnitřními stavy a stejně tak i s pouhými dvěma symboly – 0 a 1, prázdný a neprázdný. Důkaz vylíčil slovy, která byla spíše pragmatická než matematická – přesně popsal, jak se bude Turingův stroj s dvěma stavy pohybovat doleva a doprava, „odrážet se“ tam a zpět, aby mohl nasimulovat větší počty stavů ve složitějším počítači. Všechno to bylo velmi spletité a zvláštní a připomínalo to Babbageův styl.

Například toto:

Když se snímací hlava pohybuje, informace o stavu se musí přenést k dalšímu dílku pásky, který má navštívit, a to s použitím pouhých dvou vnitřních stavů stroje B. Pokud má být dalším stavem ve stroji A například stav 17 (podle nějakého libovolně zvoleného systému číslování), stroj B to napodobí „odražením“ snímací hlavy sedmnáctkrát tam a zpět mezi starým a novým dílkem pásky (vlastně jde o 18 skoků k novému dílku a 17 zpátky ke starému).

„Odrážecí operace“ přenáší informaci z dílku na dílek a tyto dílky se pak chovají jako „vysílač“ a „řadič“.

Turing nazval své velkolepé pojednání „O vypočitatelných číslech“, ale skutečným středem pozornosti byla samozřejmě nevypočitatelná čísla. Mohla nevypočitatelná a náhodná čísla spolu souviset? V roce 1965 Chaitin studoval na newyorské City College a sepisoval svůj objev, který chtěl nabídnout nějakému časopisu. Měla to být jeho první publikace. Začal: „V tomto pojednání je

Turingův stroj uvažován jako univerzální počítač a klademe si praktické otázky o jeho programování.“ Chaitin, který jako středoškolák studoval ve výběrovém programu Columbia Science Honors Program, využil možnosti věnovat se programování ve strojovém jazyce na obrovských sálových počítačích IBM, jež používaly sady děrných štítků – jeden štítek pro každý řádek programu.

Zanechával svou sadu štítků v počítačovém středisku a druhý den se vracel pro výstup. Turingovy stroje uměl rozběhnout i ve své mysli – zapiš 0, zapiš 1, zapiš prázdno, posuň pásku doleva, posuň pásku doprava… Univerzální počítač mu vhodně umožnil rozlišovat mezi čísly jako mezi A a B, jež patřila Alici a Bobovi. Uměl napsat program pro Turingův stroj, který by pak milionkrát vytiskl „01“ – program byl docela krátký. Pro milion předem daných náhodných číslic (bez struktury, pravidelností a ničeho zvláštního) však žádná taková zkratka neexistuje. Počítačový program by musel celé číslo obsahovat ve svém těle. Aby sálový počítač IBM tento milion číslic vytiskl, musel by Chaitin celý milion číslic přepsat na děrné štítky. Aby k tomu přiměl Turingův stroj, také by na vstupu potřeboval milion číslic. Podívejme se na další číslo (tentokrát desetinné):

C: 3,1415926535897932384626433832795028841971693993751…

I toto číslo vypadá náhodně. Statisticky se každá číslice objevuje s očekávanou četností (jedenkrát z deseti číslic) – stejně je tomu s každou dvojicí číslic (jedenkrát ze sta), každou trojicí a podobně. Kdekdo může říci, že statistikovi by se číslo zdálo „normální“. Další číslice je vždy překvapením. I toto číslo v sobě obsahuje celé Shakespearovo dílo. Brzy si však všimneme, že je to důvěrně známé číslo π. Nakonec tedy tak moc náhodné není.

Proč ale říkáme, že π není náhodné? Chaitin navrhl jasnou odpověď: číslo není náhodné, jestliže je vyčíslitelné – pokud ho definovatelný počítačový program vygeneruje. Mírou náhodnosti je tedy vyčíslitelnost.

Turing vnímal vyčíslitelnost jako vlastnost ano/ne – dané číslo takové buď je, nebo není. My bychom však chtěli umět říct, že některá čísla jsou náhodnější než jiná – třebas když nejsou tak uspořádaná nebo když nemají tak jednoduchý vzorec. Chaitin prohlásil, že vzorec a řád vyjadřují vyčíslitelnost.

Vzorce jsou generovány algoritmem. Vyčíslitelnost tedy můžeme zjistit tak, že se podíváme na délku algoritmu. Máme-li dané číslo v podobě libovolně dlouhého řetězce, ptáme se: jak dlouhý je nejkratší program, který ho vygeneruje? Pokud použijeme jazyk Turingova stroje, tato otázka může mít jednoznačnou odpověď, která se měří v bitech.

Chaitinova algoritmická definice náhodnosti poskytuje i algoritmickou definici informace – délkou algoritmu se měří, kolik informace daný řetězec obsahuje.

Tento text je úryvkem z knihy:
James Gleick: Informace – Historie. Teorie. Záplava
Argo a Dokořán 2013
O knize na stránkách vydavatele

autor