Alan Turing a jeho univerzální stroje

V Computerworldu 11/2003 jsme se podívali na posun, který za posledních 50 let proběhl na poli umělé inteligence. Pokrok...


V Computerworldu 11/2003 jsme se podívali na posun, který za posledních 50 let
proběhl na poli umělé inteligence. Pokrok i změny přístupů jsme demonstrovali
především na příkladu Turingova testu. Nyní si trochu podrobněji představíme
další myšlenky člověka, který toto klíčové kritérium "strojového myšlení"
poprvé zformuloval. 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ázat; 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ěc: 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 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 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. Viz článek, který publikoval
v roce 1950 ve filozofickém časopise Mind. (poznámka redakce: Tímto problémem
jsme se podrobněji zabývali v CW 11/2003.)

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.

Nemrava
Turingův osud je ale i příkladem toho, jak málo si svět váží svých géniů a
hrdinů. Počátkem roku 1952 byl Turing 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 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.

Další informace
http://www.turing.org.uk/turing/ - Život a dílo Alana Turinga
http://www.nmia.com/soki/turing/ - Turingův stroj
http://www.xat.nl/enigma - simulátory práce šifrovacího stroje Enigma
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

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ého 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 Hacklheber 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?









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.