Alan Turing a jeho univerzální stroje

Před časem jsme si tu povídali o Enigmně a o panu Turingovi. Nyní si trochu podrobněji představíme další myšlenky člověka, který poprvé zformuloval klíčové kritérium „strojového myšlení“ – Turingův test. Alan Mathison Turing (1913-1954) přitom nebyl pouze teoretikem v oboru umělé inteligence, ale jeho práce se dotýkala i celý řady dalších oblastí informatiky.
Člověku vzdělanému v matematice či v informatice se Turingovo jméno pravděpodobně vybaví především ve dvou ustálených spojeních: Turingův stroj a Turingův test. Turingův stroj ovšem není žádné hmatatelné zařízení, je to Turingův pokus o matematické zachycení intuitivního pojmu vypočitatelnosti či ještě obecněji vyřešitelnosti.

Idea obecného stroje
Turing si uvědomil, že každý výpočet (či obecněji každé řešení) začíná nějakými vstupními daty, které si můžeme představit znak po znaku zapsané na papírové pásce, a končí nějakým výsledkem, který si opět můžeme představit v této podobě.
Výpočet je tedy z tohoto pohledu přechod od jedné sekvence znaků na pásce k jiné; a Turing usoudil, že ať už ten přechod provádíme jakkoli, na té nejelementárnější úrovni se nemůže než skládat z několika operací toho typu, jako je přečtení nějakého existujícího symbolu, posun pásky o jednu pozici tam či zpátky a zapsání nového symbolu či přepsání starého. (Toho, kdo ví, jak fungují procesory dnešních počítačů, asi myšlenka, že sebekomplikovanější výpočet je kombinací obrovského množství velice elementárních operací, moc nepřekvapí; Turing s ní však přišel ve třicátých letech, to jest v době, kdy se nikomu o skutečných počítačích ani nezdálo.)
Turing pak na základě těchto úvah definoval obecný abstraktní „stroj“ a předložil hypotézu, že jakýkoli výpočet, který je proveditelný, je v principu proveditelný pomocí stroje tohoto typu. Takovou hypotézu ovšem nelze definitivně prokázal; lze ji nanejvýš vyvrátit tak, že se najde výpočet, který na Turingově stroji reprodukovat nebude možné. Žádný takový výpočet ale dosud nikdo nenašel, a Turingova definice se navíc ukázala ekvivalentní několika jiným způsobům formálního zachycení pojmu vypočitatelnosti, navrženým nezávisle jinými matematiky. Tzv. Churchova teze, říkající, že cokoli je intuitivně vypočitatelné, je vypočitatelné pomocí kterékoli z těchto metod (tedy i pomocí Turingova stroje), se tedy dnes bere v podstatě za hotovou věc.

Počítačový vizionář
Turingovy výzkumy v oblasti Turingových strojů a vypočitatelnosti se odehrávaly na půdě čisté matematiky. Ta je charakterizována mimo jiné tím, že se v ní nebere ohled na faktická omezení nás, smrtelníků: vše se v ní odehrává ‘z pohledu Boha’. Vypočitatelným se zde rozumí cokoli, co by dokázala vypočítat idealizovaná bytost, která by měla k dispozici neomezené prostředky a neomezeně času.
Turing se však pokusil o nepříliš obvyklou věci: tak jako Prométheus ukradl bohům oheň, i on se pokusil přenést svou myšlenku „univerzálního stroje“ do reálného světa nás lidí. Myšlenka počítače, tak jak ho dnes známe, je totiž také myšlenkou přechodu od strojů, které vykonávají jeden určitý proces, ke stroji, který je univerzální v tom smyslu, že disponují natolik flexibilním souborem natolik elementárních operací, že z nich lze skládat v podstatě jakékoli představitelné výpočty. Turing tak byl předurčen hrát důležitou roli v oblasti rodící se počítačové vědy. Nešlo ovšem jenom o to, že se aktivně podílel se na vývoji prototypů prvních počítačů, které během druhé světové války a krátce po ní v Anglii vznikaly; vize budoucnosti počítačů, které se v tehdejší době objevily v jeho přednáškách a článcích, s neuvěřitelnou jasnozřivostí předpovídaly mnohé z toho, co prožíváme dnes.
Pojem Turingův test pak vznikl právě v rámci jeho úvah o možnostech počítačů. Turing byl přesvědčen, že lidský mozek nemůže být ve své podstatě nic jiného než jakýsi (nesmírně komplikovaný) druh počítače. V článku, který publikoval v roce 1950 ve filozofickém časopise Mind. (viz související článek).

Kryptoanalytik
Turingovy výsledky v matematické logice a jeho pionýrská práce v oblasti rodících se počítačů by jistě stačily k tomu, aby mu zajistily místo v pomyslné síni slávy vědy dvacátého století. Turing se však do historie tohoto století zapsal ještě podstatněji, a pro obyčejného člověka hmatatelněji. V roce 1939 byl naverbován do skupiny britských kryptoanalytiků, kteří se snažili luštit šifry, pomocí kterých německá armáda kódovala svou komunikaci. Nejdokonalejší z těchto šifer se opírala o mechanické šifrovací zařízení jménem Enigma, a právě na něj se Turing a jeho kolegové soustředili především. A za pomoci informací, které jim předali polští kryptoanalytici i za využití chyb německých spojařů se jim tento zdánlivě nerozluštitelný systém podařilo brzy prolomit a poskytovat vedení anglické armády nedocenitelné informace. Turing sám se soustředil především na variantu Enigmy používanou německými ponorkami, a zejména díky němu dokázali spojenci válku v Atlantiku, která se v jednu chvíli zdála právě kvůli německým ponorkám dopadat katastrofálně, zvrátit ve svůj prospěch.

Nemrava
Turingův osud je ale i příkladem toho, jak málo si svět váží svých géniů a hrdinů. Tento člověk, který tak zásadním způsobem posunul kupředu lidské poznání a současně se zasloužil o přežití západní demokratické civilizace, byl počátkem roku 1952 zatčen a při následném soudním přelíčení uznán vinným. Jeho zločin byl klasifikován jako gross indecency (hrubá nemravnost), což byl tehdejší právní eufemismus pro homosexualitu, která byla v tehdejší Británii trestným činem (ovšem pouze u mužů). Verdikt soudu naštěstí nebyl pro Turinga nejhorší: Nemusel do vězení, vyfasoval „pouze“ lékařský dohled a roční estrogenovou kůru směřující k neutralizaci jeho libida. Podařilo se mu tak nepřijít o zaměstnání i o některé přátele. Do jaké míry právě tato aféra stála u kořene Turingova rozhodnutí spáchat v roce 1954 sebevraždu (jablkem namočeným v kyanidu), není ale přesně známo.

Enigma inspirovala
Boj anglických a později amerických kryptoanalitiků s německou Enigmou je samozřejmě vděčným námětem na románové či filmové zpracování. Vedle u nás nedávno uvedeného hollywoodské filmu se ho chopil i Neal Stephenson, autor kyberpunkových románů Sníh (Snow Crash) a Diamantový věk; výsledkem je jeho dosud poslední, více než devítisetstránkový román Cryptonomicon.
Příběh začíná před válkou, kde se na vysoké škole potkávají tři mladíci, kteří pocházejí z různých zemí a které spojuje zájem o nové matematické myšlenky točící se kolem toho, čemu se dnes říká teorie informací. Jedním z nich je Turing, druhým Američan Lawrence Pritchard Waterhouse a třetím Němec Rudolf von Hacklheber. Brzy pak dostanou všichni příležitost uvést něco ze svých idejí do praxe, a to na různých stranách barikády druhé světové války: Turing stojí po prolomení Enigmy spolu s Waterhousem před problémem, jak informace získané z dešifrovaných nepřátelských depeší využít tak, aby Hakleheber a jeho němečtí kumpáni nepřišli na to, že tyto informace mají.
Vzniká totiž dilema: prolomení Enigmy má na jedné straně cenu jenom tehdy, když lze informace získané na jeho základě využít proti nepříteli, na druhé straně má však skutečnou cenu pouze tehdy, když se o něm nepřítel ihned nedozví a šifru nezmění – tedy když nebude schopen úspěchy protivníka ‚dešifrovat‘ a vytěžit z nich informaci, že byla Enigma prolomena. To navozuje otázku, která se potom celou knihou, jejíž děj pokračuje až do současnosti, proplétá jako červená nit: kdy je informace schována v „šumu“ tak, že ji tam nepovolaní nedokáží identifikovat?

Další informace na webu:
http://www.turing.org.uk/turing/ – Život a dílo Alana Turinga
http://www.xat.nl/enigma Emulátory Enigmy
http://cogsci.ucsd.edu/~asaygin/tt/ttest.html,
http://www.scienceworld.cz/sw.nsf/page/turing – Turingův test
http://frode.home.cern.ch/frode/crypto/Turing/ – Turing jako kryptoanalytik