Alan Turing

Alan Turing Soubor:Alan Turing Aged 16.jpg
	Londýn, Anglie
Datum a místo úmrtí	7. června 1954 Wilmslow, Anglie
	Sebevražda
	Svobodný
	Cambridge,
	Britské
Vzdělání	King’s College v Cambridge, Princeton USA
Pracoviště	Bletchley Park, Anglie
	Cena R.R. Hawkinse přínos v matematice, informatice, výpočetní technice a filozofii
Známý pro	Turingův stroj, prolomení Enigmy

Alan Mathison Tuging (1912-1954) byl významný britský matematik, kryptoanalitik, logik a je považován za zakladatele moderní informatiky. Během druhé světové války pomohl prolomit kód Enigma, čímž významě přispěl k jejímu konci. Zabýval se problémem nerozhutelnosti (Entscheidungsproblem) a univerzálním strojem - dnes Turingův stroj.

Životopis

Narodil se 23. června 1912 v Londýně. Jeho rodiče, Julius Mathison Turing a Ethel Sara Turing se krátce po jeho narození odstěhovali do Indie a Alana nechali v Anglii spolu s jeho starším bratrem Johnem, kterému tehdy byly 4 roky. Alana už jako malého zajímala věda.

V 6 letech začal navštěvovat základní školu Hazelhurst. V roce 1926 se dostal na školu Sherborne v Dorsete, kde se často dostával do konfliktů vzhledem k jeho tendenci brát všechno doslovně a z hlediska “matematické logiky”. Vzhledem k tomu, že byl introvert, neměl moc přátel. Velmi důležitý pro něj byl vztah s Christopherem Morcomem, jeho nejlepším přítelem z dětství se kterým sdílel vášeň pro vědu. Alan si už tehdy byl vědom své homosexuální orientace a Christopher byl asi jeho první láska. O to víc ho zasáhlo, když v roce 1930 zemřel na tuberkulózu.

V roce 1931 byl přijatý na King’s College v Cambridge, kde začal studovat matematiku a v roce 1934 získal první titul. O rok pozdějí se stal členem akademického sboru.(xy) V roce 1936 napsal svůj převratný článek - “On Computable Numbers, with an Application to the Entscheidungsproblem”, kde popsal Turingův stroj a ještě ten samý rok odešel do Princetonu. Pak se vrátil do King’s College, spravit doktorát, který získal roku 1938. Vyučoval i na univerzitě v Manchesteru.

Během druhé světové války začal pracovat v Bletchley Parku, kde navázal na polský vynález zvaný Bomba a spolu s ostatními jí radikálně změnil. Vytvořili tak stroj na prolomení kódu, který pomohl prolomit německý kódovací stroj Enigmu, čímž zkrátili válku alespoň o dva roky. Také pracoval na prolomení šifry německého námořnictva, což se mu podařilo v roce 1939. V tomto období se zasnoubil se svou kolegyní Joan Clarkeovou. Krátce na to se jí však přiznal se svou homosexuální orientací a zásnuby zrušil, protože by to vůči ní nebylo fér.

Turingův nejznámější a po mnoha stránkách nejpodivnější článek “Computing Machinery and Intelligence” (Výpočetní stroje a inteligence) vyšel v časopise Mind v roce 1950. Článek začíná úvahou, zda stroje dokážou myslet. Prezentuje zde imitační hru, která je dnes známá jako Turingův test. Test spočívá v komunikaci mezi dvěma subjekty, které na sebe nevidí. Člověk za jedním počítačem se snaží prostřednictvím otázek zjistit, zda je za druhým počítačem člověk nebo mu odpovídá počítač. Pokud člověk nedokáže určit, kdo odpovídá, můžeme tvrdit, že na druhé straně je někdo, kdo je inteligentní, tedy myslí. Do dnes se nepodařilo žádnému stroji překonat Turingův test.

Problém rozhodnutelnosti

V semináři na King´s Collage o základech matematiky se setkal s Gödelovou větou o neúplnosti. Kurt Gödel reagoval na podnět německého matematika Davida Hilberta, který předložil ve svém programu pro základy matematiky úkol sestavit systém axiomů, který by byl úplný, bezesporný a rozhodnutelný. Gödel dokázal, že systém axiomů obsahující aritmetiku nemůže být současně úplný a bezesporný ve smyslu definovaném Hilbertem.

Turing se soustředil na jinou část Hilbertova úkolu, na problém rozhodnutelnosti, tj. na otázku, zda je možné použít jistý postup, na základě něhož by bylo možno rozhodnout, zda je dané tvrzení v daném systému axiomů pravdivé či nepravdivé (německy: Entscheidungsproblem). Odborníci považovali problém rozhodnutelnosti řešitelný ve chvíli, kdy by byl vytvořen specifický algoritmus. Alan Turing odpověděl na otázku ve své práci "Co je algoritmus" kde ukázal, že řešení problému rozhodnutelnosti není možné. Své výsledky publikoval Turing v článku „On computable numbers, with an application to the Entscheidungsproblem“ (1936). Článek byl publikovaný v časopise “Sborník Londýnské matematické společnosti” (Proceedings of the London Mathematical Society). Prezentoval zde abstraktní stroj, který dnes nazýváme jeho jménem - Turingův stroj.

Enigma

Podobně jako u osobního počítače - který v mnohém předznamenávala - byla zdánlivá jednoduchost a snadná ovladatelnost Enigmy v rozporu s jejím důmyslným a velmi komplexním vnitřním mechanismem. Její používání nebylo o nic složitější než psaní na psacím stroji, který připomínala. Signální deska byla přikryta sklápěcím víkem se třemi malými okny. Po zvednutí tohoto víka bylo možno spatřit tři rotory (později pět), které byly klíčovou součástí Enigmy. Na každém z těchto rotorů byl otáčivý prstenec se šestadvaceti písmeny abecedy.

K obsluze přístroje nebylo třeba znát, co se odehrává uvnitř. Vše, na čem se odesilatel a příjemce museli předem shodnout, bylo jen pořadí rotorů a natavení prstenců. Předepsaná nastavení pro jednotlivé dny byla vytištěna v knihách nebo sešitech, jejichž kopie byly distribuovány odesilatelům i příjemcům v komunikační síti.

Rozluštění Enigmy

Po celou dobu války pracoval Alan Turing jako civilní zaměst­nanec Ministerstva zahraničí v Bletchley Park (poblíž dnešních Milton Keynes). Asi si představoval, že jeho pobyt v Bletchley bude trvat jen několik měsíců. Ve skutečnosti se hostinec Crown Inn ve vesnici Shlenley Brook End, kde byl ubytován a odkud každý den jezdil na kole do Bletchely, stal jeho domovem po skoro celou válku. Mezi ostatními akademickými znalci šifrování i amatérskými luštiteli rébusů mu zde nikdo neřekl jinak než „Prof“.

V Princetonu Turing sestrojil elektronický multiplikátor umožňující šifrovat zprávy pomocí násobení vysokých binárních čísel. Ačkoli základní myšlenka tohoto postupu byla velmi jednoduchá, stala se předlohou šifrovací metody založené na násobení obrovských prvočísel, která dnes chrání čísla našich kreditních karet při obchodování prostřednictvím internetu. Tento stroj však neměl žádnou spojitost s německými šiframi, se kterými se Turing a jeho kolegové museli nyní potýkat. V tomto případě šlo o velmi komplikované variace na nejzákladnější způsob šifrování, tzv. monoalfabetickou šifru. K prolomení kódu přispěla i polská skupina Rejewského. Vytvořili první prototyp tzv. Bomby. Byl to stroj, který měl porazit Enigmu. A zatímco většina vědců v Blentchley se snažilo Enigmu zlomit pomocí kryptoanalitické techniky Turing věděl, že k pokoření stroje potřebuje další stroj. Proto inovoval novou Bombu “La Bombe” a to je uznáno jako jeho největší přínos. Turing byl vizionář.

Díky neúnavné analýze matematických základů polyalfabetických šifer, vytrvalému hledání slabých míst v systému Enigmy a důmyslnému využití elektrického vybavení k mechanizaci se Turingovi podařilo udělat z Enigmy když ne zcela bezbranného, tak alespoň zvládnutelného soupeře. Nakonec dokázal prolomit i kód námořní Enigmy, a tak přispět k značnému snížení počtu spojeneckých lodí potopených německými ponorkami. To byl bravurní a heroický výkon, který výrazně přispěl k Hitlerově porážce. Náplň práce v Bletchley Park byla utajená i pro nejbližší rodinu a první informace byly odtajněny až po několika desítkách let po skončení války. I proto měl Turing poněkud problém s uplatněním svých myšlenek v poválečném období, protože jeho odbornost nemohla být oficiálně podložena dřívějšími zkušenostmi.

Turingův stroj

Je to v podstatě zjednodušený počítač, “nekonečný automat (akceptor)” . Nejúžasnější na něm je, že žil jenom v hlavě samotného Turinga, protože ho nesestrojil a ani to nikdy neměl v plánu. On sám stroj nazval “a-stroj” nebo “automatický stroj”. Skládal se z oboustranné nekonečné pásky, rozdělené na políčka a pohyblivé hlavy, které mohou číst i zapisovat na políčka symboly s1, s2, …, sk z nějaké konečné (alespoň dvouprvkové) abecedy. Na začátku stroje definujeme stavy a přechodové funkce, přijímající a zamítající stav a abecedu, nad kterou Turingův stroj pracuje. Stroji se na začátku přesně definují stavy, přechodové funkce a stejně tak i přijímací a zamítací funkce. Také musí mít zadané, nad jakou abecedou pracuje.

Když se stroj nachází v q, některém z konečných počtů stavů, může stroj provést tři věci:

• Z daného políčka vymaže symbol s, který tam byl předtím a nahradí ho symbolem s´. Potom stroj přejde do dalšího z konečných stavů, q´.
• Hlava nic nezmění, jen se posune o jedno políčko vlevo nebo v pravo a následně přejde do q´.
• Turingův stroj se může zastavit v jednom z q´.

Smrt

Dva roky před narozením Turinga byl známý dramatik Oscar Wilde souzený za homosexualitu a odseděl si dva roky ve vězení. Netolerance homosexuality ho zničila, stejně jako Turinga o několik desetiletí později. Turing svou orientaci nikdy neskrýval. Akceptoval ji a předpokládal (nesprávně), že ji ostatní také prostě přijmou. Situace vygradovala, když mu vykradli dům. Podezříval svého tehdejšího přítele Arnolda Murraye a ten se mu přiznal, že ho vykradl jeho kamarád, kterému říkal o jejich vztahu. Policie však místo řešení krádeže zatkla a odsoudila Turinga za “nemravné chování” - homosexualitu, která byla tehdy trestná. Dali mu na výběr způsob trestu - rok vězení nebo chemickou léčbu (estrogenové injekce, které měli vyléčit jeho homosexualitu). Vybral si léčbu, která se vlastně rovnala chemické kastraci. Jeho život se výrazně změnil. Celý život běhal, proto měl atletickou postavu. V důsledku injekcí mu ale narostly prsa, přibral. Na základě obvinění mu také zakázali přístup k vládním záležitostem a jeho práci. Byl neustále sledovaný ze strachu, že prozradí tajné informace do zahraničí. Všechno tohle spělo k jeho trpkému konci. Dne 8. června 1954 ho našla jeho uklízečka mrtvého na posteli. Vedle něho leželo nakousnuté jablko namočené v kyanidu. Jako příčina smrti byla určená sebevražda.

V roce 2009 se mu veřejně omluvil tehdejší britský premiér Gordon Brown. Jeho jméno však bylo oficiálně očištěné teprve 24. prosince 2013, kdy se mu téměř po 60 letech omluvila královna Alžběta II.

Význam pro informační vědu

Při své práci na univerzálnímstroji položil základ pro informatiku, protože z dnešního pohledu se jedná vlastně o zjednodušený počítač. Turing je tedy považován za jednoho ze zakladatelů informatiky a na jeho počest se uděluje každoročně cena za technický přínos v oboru.

Cena Alana Turinga

Každý rok, v den jeho narozenin (23. června 1912) uděluje Asociace výpočetní techniky (ACM) cenu jednotlivcům za jejich technický přínos v oboru informatiky a je považována za jednu z nejprestižnějších v tomto oboru. Cena má za úkol demonstrovat respekt ke všem oceněným, propagovat jejich úsilí a to, čeho dosáhli. Také zvýšit povědomí o informatice nejen pro informační vědce ale i pro širokou veřejnost. V roce 2012, při výročí Turingových 100 narozenin, se sešlo 32 z 39 žijících laureátů.

Zajímavosti

Elsevier, přední světový dodavatel vědeckých, technických a lékařských informačních produktů a služeb udělil v roce 2013 cenu R.R. Hawkinse Alanu Turingovi za jeho přínos v matematice, informatice, výpočetní technice a filozofii.

Už v 80. letech minulého století se v londýnské divadelní čtvrti West End objevila hra Breaking the Code, která popisovala Turingovu angažovanost v supertajném vládním projektu na prolomení Enigmy a zároveň jeho boj s homosexualitou.

V libereckém divadle zdramatizovali Turingův život ve hře s názvem Přísně tajné: Hrubá nemravnost.

Připravuje se i film The Imitation Game. Režie se ujal Morten Tyldum v hlavní roli Benedict Cumberbatch.

Po internetu kolují zvěsti, že jablko, které je na logu Apple Computers, odkazuje na Turinga. Společnost Apple však tuto souvislost popírá a naopak tvrdí, že její jablko je narážkou na Newtona. Proč je ale potom nakousnuté?

Zdroje

• "Alan Turing." Encyclopaedia Britannica. Encyclopaedia Britannica Online. Encyclopædia Britannica Inc., 2014. Web. 27 Apr. 2014. <http://www.britannica.com/EBchecked/topic/609739/Alan-Turing>.

• Belated Apology For Turing. Communications of the ACM [online]. 20091101, vol. 52, issue 11, s. 17-17 [cit. 2014-04-27]. Dostupné z: Business Source Complete, Ipswich, MA

• DURNOVÁ, Helena. ALAN MATHISON TURING (1912 - 1954). Ústav matematiky FEKT VUT [online]. 2004 [cit. 2014-04-24]. Dostupné z: [1]

• Elsevier Wins 10 PROSE Awards Including the R. R. Hawkins Award for Alan Turing: His Work and Impact. Business Wire (English) [online]. 2014, bizwire.c53235036 [cit. 2014-04-24]. Dostupné z: [2]

• FELDMAN, Stuart I. The Rewards of ACM's Awards. Communications of the ACM [online]. 2007, vol. 50, issue 11, s. 17-18 [cit. 2014-04-24]. DOI: 0001-0782. Dostupné z: [3]

• GOTTFRIED, Ted. Alan Turing: the architect of the computer age. New York: Franklin Watts, c1996, 128 p. ISBN 05-311-1287-X.

• HYMAN, Paul. In honor of Alan Turing. Communications of the ACM [online]. 2012-09-01, vol. 55, issue 9, s. 20- [cit. 2014-04-24]. DOI: 10.1145/2330667.2330675. Dostupné z: [4]

• JEŽO, Martin. Turingov test. Trenčín, 2010. Dostupné z: http://www.kiwiki.info/index.php/Turingov_test. Esej. Trenčianska Univerzita Alexandra Dubčeka v Trenčíne, Fakulta Mechatroniky. Vedoucí práce Ing. Andrea Julény.

• LEAVITT, David. Muž, který věděl příliš mnoho: Alan Turing a první počítač. Dokořán, 2007. ISBN 978-80-7363-086-7.

• MAREŠ, Milan. Slova, která se hodí aneb jak si povídat o matematice, kybernetice a informatice. Praha : Academia, 2006. 352 s. ISBN 80-200-1445-4. Kapitola Se složitostí to není jednoduché, s. 303-309.

• PUŽMANOVÁ, Rita. Alan Mathison Turing: Matematik, logik, kryptograf a zakladatel moderní informatiky. Akademický Bulletin. Dostupné z: [5]

• ROVAN, Branislav a Michal FORIŠEK. Formálne Jazyky a Automaty. Bratislava, 2013. Dostupné z: http://foja.dcs.fmph.uniba.sk/materialy/skripta.pdf. Skripta. Univerzita Komenského.

• Stránka Alana Turinga [6]

• Studijní materiál. Dostupný z: http://pascal.input.sk/index.php/18.Prednaska

• Studijní materiál. Dostupné z:[7]

• TEUSCHER, Christof. Alan Turing: Life and Legacy of a Great Thinker. New York: Springer, 2004, s. 542. ISBN 3-540-20020-7.

• The Prose Awards [8]

• VODSEĎÁLEK, Petr. Už dva roky ožívá příběh Alana Turinga v původní divadelní hře. Liberecky.denik.cz.2013.Dostupné z: [9]