Sestavil také samotný koncept současného počítače v podobě Turingova stroje. Napsal první funkční šachový algoritmus, ukázal současně ale i meze počítačových programů.
Letošní rok se označuje za Turingův, protože od jeho narození uplynulo 100 let. V červnu (Alan Turing se narodil 23. 6. 1912) se pak konala celá řada akcí na jeho počest. V tomto článku vynecháme Enigmu, Turingův test i Turingův stroj.
Na toto téma současného vývoje Turingova testu viz např. článek: Chatboty 100 let po narození Alana Turinga
(V této souvislosti jen poznámka: Snad je zajímavé, že Turing navrhl test v poněkud složitější podobě, než jak je dnes běžně uváděn. V původní verzi je imitace vícenásobná. Muž předstírá, že je žena, a počítač se pak snaží imitovat muže, který předstírá, že je žena...)
Turing už ve 30. letech 20. století, tedy ještě před existencí reálných počítačů, vyřešil problém zastavení (halting). Ukázal, že nemůže existovat obecný algoritmus, který by dokázal určit, zda se libovolný jiný program zastaví. Trocha upřesnění: jistěže existují programy ovládané vstupem uživatele, kde to, zda se nekonečně zacyklí, závisí na vstupu. Úloha se ovšem zabývá programy, které se spustí bez dalšího vstupu, respektive vstup známe předem. Řešení je založeno na principu, že hypotetickému „všemocnému" programu se předhodí upravené varianta jeho samého a dojde se ke sporu. Význam problému zastavení se blíží Goedelovým důkazům neúplnosti formálních systémů.
(Mimochodem, v této souvislosti je zajímavé, že jiná úloha, vytvořit program, který tiskne sám sebe, naopak řešitelná je; v tomto případě se kód sám sebou „zadávit" nemusí.)
Z neřešitelnosti problému zastavení pak vyplývá další omezení, že totiž nemůže existovat ani univerzální program, který by dokázal říci, zda libovolný program počítá správně – protože konec konců nelze ani obecně určit, zda svůj výpočet vůbec kdy dokončí.
Turing je autorem nejstaršího fungujícího algoritmu pro hraní šachů. (Teoreticky je možné, že nějaký napsal už Charles Babbage, neúspěšný tvůrce obecného počítače už z 19. století. Babbage o strojovém šachu opravdu uvažoval, žádný konkrétní výstup se ale nedochoval.) I v tomto případě algoritmus předběhl reálný počítač; Turing však program napsal tak výpočetně nenáročný, že příslušné výpočty mohl provést i na papíře a skutečně takto sehrát partii. Na to, že výpočty každého tahu lze provést na papíře za pár minut, hraje program až neuvěřitelně dobře.
Podrobnosti Scienceworld
Turing jako matematik přispěl také k úvahám o možnostech a omezeních tzv. diagonálních důkazů. Tuto metodu jako první použil v 19. století matematik Cantor k důkazu, že zatímco celých a racionálních čísle je stejně (= obě nekonečna mají stejné vlastnosti), reálných je více. Turing ovšem diagonální metodu výrazně vylepšil tak, že při ní nebylo třeba používat pojem aktuálního nekonečna. Diagonálním důkazem lze mimochodem dokázat i neřešitelnost problému zastavení.
Turingovo jméno se objevuje i v rámci tzv. Churchovy-Turingovy teze, která říká, že cokoliv je vypočitatelné, je vypočitatelné nějakým Turingovým strojem; nebo jinak řečeno, že existuje ekvivalence mezi Turingovými stroji a algoritmy. Takový výrok zní snad až příliš filozoficky, Turing se podobným filozofickým otázkám ovšem nevyhýbal, jak svědčí např. jeho debata se známým filozofem L. Wittgensteinem o tom, zda chyba v matematice může způsobit pád mostu – Scienceworld).
Chuchova-Turingova teze se pokládala dlouho za zřejmě pravdivou, ale nedokazatelnou, protože je formulována příliš vágně („vše, co je vypočitatelné"). V poslední době se ale objevilo i tvrzení, že je chybná: Existují systémy, které dokáží vypočítat více než Turingův stroj. Jejich návrh ovšem počítá s relativistickými efekty nekonečného zpomalení času a pádem objektů do černé díry. Zda to tak může opravdu fungovat, na to by asi málokdo byl ochoten dát ruku do ohně.
Pro luštění německé Enigmy Turing sestrojil mechanický počítač Bomba, jednoúčelový, avšak překvapivě účinný stroj. Zdaleka tedy nešlo jen o člověka, který by se pohyboval ve sféře čistých algoritmů zcela odtržených od fyzické reality. Faktem ale je, že v poválečném období se Turing podílel v Británii na konstrukci prvních digitálních počítačů v rámci projektů, které příliš úspěšné nebyly.
Alan Turing na počátku 50. let 20. století odhadoval, že do cca 50 let bude k dispozici výpočetní kapacita plně dostačující na to, aby programy procházely Turingovým testem. To se však nepotvrdilo. Turing ve svém odhadu vycházel prostě z předpokládaného pokroku výpočetní kapacity/paměti počítačů, kterou srovnával s hardwarem lidského mozku.
Jaký ze současných programů má mimochodem k Turingovu tvrzení nejblíže? Snad Apple Siri nebo Honda Asimo? Do ní (něj?) se lze dokonce i zamilovat, alespoň se to stalo v seriálu Big Bang Theory...
O univerzálnosti Turingova talentu svědčí i jeho příspěvky dalším vědním oborům. Zabýval se např. morfogenezí a navrhl zde několik teorií, které se podařilo potvrdit až v nedávné době spolu s pokrokem molekulární biologie...
PŘEDPLATNÉ
ČLÁNKY DO MAILU