Nová alchymie

Je to ledva pár desetiletí, co se člověku omrzelo ručně počítat. Vynalezl si stroje, aby za něj řešily rozmanité potřebné i nepotřebné úlohy. Ať jsme rádi či neradi, srostly již s námi tyto podivné stroje, splynuly s naší kulturou a asi se jich už nikdy nezbavíme, těchto vlezlých služebníků.

Dnes jsou počítače nesrovnatelně menší, rychlejší a po mnoha stránkách inteligentnější než v době svého vzniku. Zahledíme-li se však zkoumavým okem do jejich nitra, zjistíme, že co do základního principu jsou víceméně totožné se svými pradědečky. Jde vlastně o dvě vzájemně se doplňující myšlenky. První je založena na prostém faktu, že lze vyrobit prvky, které mohou mít dva a jen dva stavy a které lze spojovat tak, že stavy jedněch se vhodně kombinují se stavy druhých a že cokoliv z toho lze někam uložit pro pozdější použití.

Druhou myšlenkou je pojem algoritmu. Jakýkoliv typ služby, pokud ji lze vůbec od počítače žádat (znásobit čísla, vložit slovo do textu, najít cestu v síti, dokázat teorém), je třeba formulovat v podobě přesného návodu – posloupnosti instrukcí – jak v které situaci postupovat. Tento návod čili program je zpravidla obecný, to jest lze jej použít pro různá počáteční data (různá čísla, slova, sítě, teorémy). Jsou-li tato data větší a složitější, nevadí, bude to jen déle trvat. Jak déle, to lze někdy předem odhadnout a říká se tomu (časová) výpočtová složitost algoritmu (potažmo úlohy, máme-li na mysli pro ni nejefektivnější myslitelný algoritmus). Nehodnotí se délka výpočtu samotná, nýbrž to, jak rychle tato délka narůstá s velikostí vstupních dat. Proto je zcela nepodstatné, z jakých součástek je počítač vyroben.

O výpočtové složitosti jsme si mohli přečíst (při troše čtenářské píle celkem srozumitelně) v červnovém čísle Vesmíru¹⁾ a i v tomto čísle se k ní vracíme v článku Melánie a Petra Babincových (Vesmír 74, 545, 1995/10). Tentokrát se navíc dovíme o nejnovějším hitu, nové Adlemanově metodě řešení úloh²⁾, která zcela obchází popsaný princip dnešních počítačů.

Vzpomínáte-li si, ve zmíněném červnovém čísle se mluví o úlohách (“typu NP″) s tou vlastností, že pokud by řešení takové úlohy spadlo z nebe, poměrně snadno by se ověřila jeho správnost, pokud však nic z nebe nepadá, není znám jiný algoritmus, než trpělivě zkoumat jeden po druhém všechny možné kandidáty na řešení (jejichž počet roste závratně rychle s velikostí úlohy).

Právě s tím si Adlemanova metoda dovede výborně poradit. Vyrobí se jednoduše roztok, v němž jsou možní kandidáti na řešení obsaženi všichni najednou (zakódováni do posloupností bází molekul DNA). V tomto roztoku se pak rozličnými důmyslnými chemickými reakcemi rozmnožují nadějní kandidáti a jinými důmyslnými reakcemi se odstraňují chybní kandidáti. Po několika takovýchto úkonech (jejichž počet jen lineárně závisí na velikosti úlohy) spolehlivě dostaneme všechna správná řešení a není problém si je pak přečíst. Adleman to předvedl i prakticky – po týdenní práci v laboratoři nalezl Hamiltonovu cestu v grafu o sedmi vrcholech.

Jeho metoda využívá replikačních vlastností molekul nukleových kyselin a obratně aranžuje situace, v nichž se tyto dlouhé molekuly předepsaným způsobem spojují, dělí, množí a filtrují. Nemá to co dělat s principem tradičních počítačů, ba ani to nelze přirovnat ke konekcionistickému principu paralelních neuronových sítí. To je již samo o sobě pozoruhodné, daleko důležitější však je, že základní nositelé relevantní informace – velké molekuly – jsou tak malé, že v jediné zkumavce lze realizovat triliony trilionů operací najednou. O takovém paralelizmu se konstruktérům počítačů nikdy nesnilo.

Dá se to nazvat výpočtem? Snad ano, ale pak i filtrování kávy je paralelním výpočtem, a to celkem úsporným, protože rozměry filtru jen málo závisí na počtu zrnek namleté kávy.

Teď však něco pro skeptiky. Za ty triliony trilionů je třeba něčím zaplatit. Celkem jednoduchý výpočet ukáže, že kdybychom stejnou úlohu, jakou předvedl Adleman, chtěli jeho metodou řešit pro graf, který místo 7 má 200 vrcholů, museli bychom začít s roztokem o hmotnosti 3.10²⁵ kg, což je víc než váží Země³⁾.

Koho neodrazují takováto přízemní omezení, toho bude jistě zajímat, že Adlemanova metoda je univerzální (vyrovná se Turingovým strojům). Takže principiálně nic nepřekáží tomu, aby chemik ve svých kádinkách a křivulích napodobil i nejmoudřejší počítač, a tedy – jak by měli usoudit důslední funkcionalisté – i mozek mudrců.