Escherichia, mýdlové bubliny a černé díry aneb co všechno může počítat

DNA

Algoritmy lze implementovat do elektromagnetických vlastností (jako v běžných počítačích), máme zde i více či méně použitelné DNA počítače nebo počítače kvantové. Nicméně existují ještě mnohem kurióznější přístupy.

Výpočet může být třeba realizován přímo živými organismy. Teď nejde o to, že by tyto představovaly nějakou součást počítajícího systému (např. bakterie jako baterie, geneticky modifikovaný virus výhodně měnící vlastnosti čipu, články založené na vnitrobuněčných organelách – mitochondriích – nebo memristor z lidské krve nebo prvok fungující jako kurzor v počítačové hře; to jsou příklady projektů mnoha tohoto typu), ale skutečně realizují výpočet.

Sudoku, hradla a železnice

Japonští vědci takto přiměli bakterii Escherichia coli, aby luštila Sudoku na zmenšené ploše 4×4. Geneticky od sebe odlišné kmeny bakterií reprezentovaly jednotlivá políčka. Kolonie přitom navíc mohly vytvářet různé barvy, ty zase odpovídaly jednotlivým číslům. Informaci o vstupních hodnotách (kmeni i barvě) přenášely mezi bakteriálními kolonie viry – přenášené zprávě odpovídala různá podoba RNA. Tato RNA pak bránila syntetizovat příslušnou barvu, tj. doplnit do políčka zakázané číslo. Detailněji algoritmus bohužel popsán nebyl, takže není jasné, jak se zařídilo, aby omezující podmínky platily pouze pro stejný řádek, sloupec nebo větší čtvereček a negenerovaly se ze situace na celé herní ploše.

Jako jednoduchý počítač, respektive spíše logický spínač, funguje bakterie Escherichia coli i ve svém přirozeném prostředí. Hladová bakterie zkoumá, zda v prostředí je přítomna glukóza nebo laktóza a podle toho syntetizuje enzymy potřebné pro jejich metabolismus (je-li k dispozici oboje, bude se přednostně krmit na laktóze; není-li přítomno nic, nebude syntetizovat žádné enzymy, bylo by to neekonomické). Chování bakterie pak odpovídá výpočtu funkce L AND (NOT G) pro oba enzymy (podrobněji: Martin Amos, Na úsvitu živých strojů, Mladá fronta 2008).

Zdroj obrázku: Wikipedia http://cs.wikipedia.org/wiki/V%C3%A1penatka_mnohohlav%C3%A1

Vápenatka mnohohlavá. Zdroj obrázku: Wikipedia

Hlenka vápenatka mnohohlavá (hlenky jsou podivné organismy někde mezi jedno- a mnohobuněčnými) zase prý dokáže řešit optimalizační úlohy spojené s hledáním maxim nebo minim při analýze roviny. Vědci z Hokkaido University provedl následující „výpočet“. Na mapě Japonska založili vstupní kolonii hlenek na místě Tokia, na dalších městech pak umístili zdroje potravy, jejichž velikost odpovídala velikosti města. Buňky se snažily růst tak, aby kolonizovaly místa, kde najdou jídlo. V první fázi se hlenka šířila „plošně“ všemi směry, ale posléze na místě zůstala příslušná síťovitá struktura vláken propojující jednotlivé zdroje potravy – města. A tato struktura odpovídala víceméně současné železniční síti (včetně frekvence provozu po tratích).

Mimochodem, síť byla navíc redundantní, takže se nerozpadla ani při náhodném přerušení některých spojů. Není to první příklad toho, jak hlenky dokáží najít optimální cestu za potravou – před několika lety byly provedeny experimenty, ve kterých zvládly také objevit nejrychlejší cestu bludištěm. Asi nejde předpokládat, že by se hlenky začaly používat pro návrh třeba mobilní infrastruktury, ale zajímavé to určitě je.

Obchodní cestující, mýdlové bubliny a brachistochrona

Složitá (NP úplná) úloha obchodního cestujícího k sobě samozřejmě pozornost matematiků a informatiků vábí jako světlo můry. Počítat zde mohou klasické počítače, DNA počítače (právě na této úloze byly ostatně jejich možnosti poprvé demonstrovány; o vývoji DNA počítačů viz i článek zde na Zdrojáku DNA počítače: technologie nespí), kvantové počítače (ne, i když se občas lze setkat s opačným tvrzením, žádný efektivní algoritmus se zde ale zatím navrhnout nepodařilo), úlohu dokáží do jisté míry efektivně (ve smyslu nalezení nějakého rozumného, byť ne optimálního řešení) luštit i živí lidé.

Zdroj obrázku: Wikipedia http://en.wikipedia.org/wiki/Soap_bubble

Zdroj obrázku: Wikipedia

Pak jsou zde ale kurióznější přístupy. Tentokrát namísto počítání pomocí mikroorganismů budeme počítat mýdlem. Matematik a popularizátor David Acheson (1089 a další parádní čísla, Dokořán 2006) uvádí, že úlohu lze totiž analogově modelovat pomocí mýdlového filmu. Model měst a jejich propojení ponoříme do kapaliny; mýdlové bubliny se ve struktuře seskupí tak, aby blána měla co nejmenší povrch, který odpovídá nejkratší cestě. Samozřejmě nevíme, zda jde o optimální řešení nebo jen nějaké jemu hodně blízké (můžeme si dejme tomu představit, že energie pro přechod do optimálního stavu by byla větší, než co by se ušetřilo, je zde nějaká potenciálová bariéra apod.). Z druhé strany ale, pokud máme nějaké řešení úlohy obchodního cestujícího, pak ověřit ho můžeme za mnohem kratší čas, než odpovídá samotnému řešení.

Dalším analogovým přístupem k problému obchodního cestujícího je strukturu namodelovat ve vodičích světla a pak zjistit, kdy dorazí k cíli první paprsek. Potřebujeme ovšem v každém uzlu paprsek nějak označit, abychom vůbec věděli, kudy ten nejrychlejší putoval. Je také obtížné přesně reprodukovat různé délky a spoje, alespoň u úloh s miliony bodů. Přístup je to tedy velmi zajímavý, ale prakticky nepoužitelný, alespoň v současné podobě. Chtělo by to nějak domyslet… Jinak by se dalo uvažovat i o implementaci do vody proudící systémem kanálků. Zajímavý přístup, používaný k podobným problémům (procházení bludištěm apod.) představuje rovněž „chemická vlna“, tedy rychlost šíření produktů určité chemické reakce, které pak ve zkoumaném prostoru detekujeme. Nejlépe tak, pokud při reakci dochází k barevné změně, takže k záznamu stačí kamera.

Mimochodem, skupina vědců z University of West Virginia dokonce zkusila tímto způsobem řešit i složitější úlohy s více kroky. Přitom se měly uplatnit různé „cyklické“ (částečně cyklické, entropii nakonec neošidíme) reakce, jako je známá reakce Bělousova-Žabotinského.

Ještě zpět k šikovným mýdlovým bublinám. Jejich snaha o minimalizaci povrchu se dá využít i jinak. Carlos Criado a Nieves Álamo z University of Málaga s pomocí mýdlových bublin zkusili najít křivku brachistochrona. Tato křivka je řešením následující úlohy: jak z jednoho bodu dostat co nejrychleji do druhého, níže položeného bodu, kuličku? Intuitivně se zdá, že přímka není rozhodně optimální, kulička dojede do cíle velmi rychle a část energie se při tom nevyužije. Nejlépe by asi bylo na začátku kuličku pořádně rozjet, dostat ji níž, než je cílový bod, do kterého by pak „jenom“ dojela setrvačností.

Jak ale řešení přesně vypadá? Na této úloze si údajně vylámal zuby už Galileo, mýdlové bubliny ale řešení zvládnou. I když jen analogově, takže nezjistíme, brachistochrona je totožná s částí oblouku cykloidy (křivka, kterou při pohybu kola po vodorovné silnici opíše bod na jeho povrchu).

Šachy a černé díry

Příkladů kuriózních počítačů je nepřeberně, od známého strojku z antického vraku nalezeného u Antikythéry (do sebe zapadající ozubená soukolí je jistě důmyslná věc minimálně z hlediska mechanické konstrukce, jenže přece jen je otázka, zda tomu říkat počítač – říkali bychom tak třeba hodinkám?) po otáčecí kotouče Raymunda Lulla (kolem roku 1300), které měly zjišťovat pravdivostní hodnotu složených formulí.

Zcela futuristickou myšlenkou je naopak použít k počítání černou díru. V první řadě by mohlo jít o systém s obrovskou rychlostí – to když si uvědomíme, kolik částic je v černé díře chyceno (abstrakt v PDF původního článku na Scientific America).

Zdroj obrázky: Wikipedia http://en.wikipedia.org/wiki/Black_hole

Černá díra. Zdroj obrázku: Wikipedia

Druhá myšlenka je však ještě revolučnější, protože v určitém uspořádání pádu do černé díry lze dokonce postavit systém, který dosáhne něčeho, co je zdánlivě úplně nemožné – vyřeší některé z úloh neřešitelných Turingovými stroji (což by dokonce znamenalo, že známá Churchova teze „vše, co je vypočitatelné, je vypočitatelné nějakým Turingovým strojem“, neplatí!). Další informace viz např. kniha Umělá inteligence 5 (Academia 2006, kapitola Výpočetní meze kognitivních a inteligentních systémů od Jiřího Wiedermanna), beletristické zpracování v povídce Planckův skok (ve sbírce Greg Egan: Luminous, Talpress 2011).

Nakonec, nepodceňujme ani člověka v roli výpočetního zařízení. Jsou zde zázrační počtáři. Alan Turing mezi ně nepatřil, přesto však dokázal napsat algoritmus pro hraní šachů, kdy každý tah v rozumném čase zcela „mechanicky“ vypočítal na papíře. Partii sice prohrál, překvapivé ovšem je, že tahy i takto jednoduchého algoritmu dávaly celkem rozumný smysl.

Obrázek převzat z Wikipedie http://en.wikipedia.org/wiki/El_Ajedrecista

Šachový automat. Zdroj obrázku: Wikipedia

A když už jsme u umělých systémů pro hraní šachů, za pozornost stojí nejstarší funkční stroj (tedy opravdu fungující, existoval i „šachový Turek“, kdy se v příslušné figuríně ovšem ukrýval liliputánský šachista). Na počátku 20. století se objevil automat El Ajedrecista, který ze vstupní pozice dokázal dát králem a věží mat soupeřovu králi. Rozpoznávání polí a figur se odehrávalo na magnetickém principu. Zajímavé z dnešního pohledu je, že logika byla implementována přímo do hardwaru. Šlo opravdu o jednoúčelový stroj, do něhož se nenačítal žádný program (byť teoreticky už v té době takto postupovat šlo, Charles Babbage žil dříve a děrné štítky se jako řídicí software používaly ještě déle), takže dokázal hrát pouze příslušnou koncovku. Je zajímavé, jak daleko by se s tímto přístupem dalo dojít, šel by takto třeba postavit stroj, který by uměl dát mat dvěma střelci?

Věděli jste, že nám můžete zasílat zprávičky? (Jen pro přihlášené.)

Zdroj: http://www.zdrojak.cz/?p=3631