Aktuální číslo:

2021/6

Téma měsíce:

Fluor

1, 2, 3, 4, 5, 6, 7, ...

 |  5. 6. 1995
 |  Vesmír 74, 303, 1995/6

Slýcháme, že přirozená čísla jsou od Boha - či aspoň od přírody, jak svědčí jejich název -, vše ostatní si lidé nebo matematici vymysleli. Je-li tomu tak, naskýtá se otázka, jakým způsobem čísla v přírodě vůbec existují a jak se my o nich dovídáme.

Nějaké číslo vstupuje do bytí především jako počet něčeho. Na první pohled banální tvrzení, skrývá však háček: co si máme myslet o těch číslech, která shodou okolností nejsou ničeho počtem? Jsou to například hodně velká čísla - těch je dokonce většina! A vůbec, kdo rozhodne, které to entity světa mají povahu počítatelnosti? Když takto začneme uvažovat, brzy se dostaneme k otázce, kolik nám to čísel Bůh vlastně nadělil.

Několik málo nejmenších čísel lze přímo "vidět": stačí se přece podívat, abychom poznali, zda hřib, čáp, kůň, střevlík či pavouk má vždy správný počet nohou. Není nutno počítat. Horizont takovéto viditelnosti je někde mezi osmi a počtem nohou stonožky (který není sto ale 34, u některých druhů až 346, mám-li věřit knihám).

Za tímto horizontem už nezbývá než zdlouhavě počítat, či odpočítávat, jako ovčák ovce, jednu po druhé. Narazíme však brzy na další problém. Běžně máme za to, že počet nějakých reálných věcí, ať je jich sebevíc - počet ovcí v houfu, molekul v roztoku, hvězd v galaxii - je exaktní, objektivní, nezávislý na počítajícím. Představa, že k takto chápanému počtu se lze dobrat počítáním, by však vyžadovala něco závažnějšího než trpělivost: museli bychom počítajícího vysvobodit z našeho reálného času a prostoru. V něm totiž počítání předpokládá určitou prostorovou činnost, přenášení informace z místa na místo, nebo přeskupování počítané množiny - a nic nám přitom nezaručí, že se přitom počítaná množina nějak nepozorovaně nezmění.

Asi je to tak, že od Boha (či od přírody) máme jen malá čísla. Ta velká (rozuměj: větší, než lze v přírodě potkat) si matematici museli domyslet. Dobře udělali, protože se ukázalo, že teoretizovat lze daleko snáze o množině všech čísel vůbec než o některé její části. Hlavním trikem jsou aritmetické operace: sčítání a násobení. Aritmetika umožňuje mluvit o všech číslech najednou v jazyku malých čísel (stačí dokonce jednička) a definovat celou nekonečnou množinu čísel na malém kousku papíru. Stačí vyjít z několika základních zákonů (axiomů a odvozovacích pravidel), vše ostatní lze odvodit. Pozor! Opravdu vše?

Nekonečno, jehož přijetí umožňuje přemítat o množině všech přirozených čísel vcelku a tak o nich mluvit nezávisle na tom, zda jsou velká či malá, se nám vzepřelo dát do rukou vše. Od roku 1931 víme, že ať definujeme přirozená čísla sebelépe, vždy nám některé jejich vlastnosti zůstanou utajeny. Slavná Gödelova věta totiž praví, že žádný (konečný) systém zákonů nemůže být tak silný, aby byl schopen dokázat všechny pravdy o číslech, aniž by přitom nedokázal též nějaké nepravdy.

Existuje intimní souvislost mezi množinami čísel, výroky o číslech a algoritmy, které s čísly operují. Tak například výrok "číslo x je prvočíslo" říká, že číslo x je prvkem množiny prvočísel. K množině prvočísel pak existuje algoritmus (počítačový program), který rozpoznává prvočísla. Vložíme-li na vstup tohoto algoritmu číslo x, odpoví "ano" v případě, že náš výrok byl pravdivý.

Nelze se proto divit, že existuje stejně intimní souvislost mezi teorií čísel a teorií algoritmů. Zatímco teorie čísel je tu s námi již dlouho, je teorie algoritmů záležitostí tohoto století. Její rozvoj v posledních desetiletích je - jak by se dalo čekat - důsledkem existence počítačů. Jak už to bývá, praktické potřeby silně ovlivňují směr teoretického bádání (to je prostě fakt, nikoliv apel) a protože rychlost výpočtu (pro různá vstupní data) je z praktického hlediska snad nejdůležitější vlastností algoritmů, je teorie výpočtové složitosti jednou z nejživějších disciplín informatiky.

V tomto čísle je teorii složitosti věnován článek Pavla Pudláka (Vesmír 74, 305, 1995/6). Teorie výpočtové složitosti nahrazuje otázku principiální existence algoritmu (či důkazu nějakého tvrzení) otázkou existence zvládnutelného algoritmu pro danou úlohu - rozumí se takového, jehož nároky na výpočetní čas nerostou příliš strmě v závislosti na velikosti vstupních dat. Existuje zajímavá třída úloh (mnohé z nich jsou dokonce "ze života"), zvaná "NP", pro něž všechny známé algoritmy hledají řešení jen obtížně (zdlouhavě), přičemž však pokud nějaké řešení spadne z nebe, snadno se pozná, zda je správné. Nezbývá tedy než trpělivě probírat všechny případy, jeden po druhém.

Kdekdo se snaží zjistit, zda s tím lze něco dělat. Kdyby se totiž našel zvládnutelný algoritmus aspoň pro jednu úlohu z jisté dobře popsané podtřídy úloh typu NP, pak by už všechny úlohy typu NP měly zvládnutelný algoritmus.

Situace mi trošičku připomíná rozdíl mezi malými, "viditelnými" čísly a čísly, k nimž se lze jen dopočítávat, jak o tom byla řeč na začátku. Je možné, že ony zvládnutelné algoritmy, založené zpravidla na nějakém vhledu do podstaty úlohy, se vyskytují jen velmi vzácně mezi primitivními a zdlouhavými algoritmy, které neumějí než se probírat všemi možnostmi.

OBORY A KLÍČOVÁ SLOVA: Různé
RUBRIKA: Úvodník

O autorovi

Ivan M. Havel

Doc. Ing. Ivan M. Havel, CSc., Ph.D., (11. 10. 1938 – 25. 4. 2021) Po vyloučení z internátní Koleje krále Jiřího pro „buržoazní původ“ dokončil základní školu v Praze a poté se vyučil jemným mechanikem. Později však večerně vystudoval střední školu a večerně také vystudoval automatizaci a počítače na Elektrotechnické fakultě ČVUT (1961–1966). V letech 1969 až 1971 postgraduálně studoval na Kalifornské univerzitě v Berkeley, kde získal doktorát v matematické informatice. Po návratu se v Ústavu teorie informace a automatizace ČSAV zabýval teorií automatů. Z politických důvodů musel ústav v roce 1979 opustit a až do roku 1989 se živil jako programátor v družstvu invalidů META. Nespokojil se však s prací pro obživu. Organizoval bytové semináře, věnoval se samizdatové literatuře. Po sametové revoluci od listopadu 1989 do června 1990 působil v Koordinačním centru Občanského fóra. V polovině roku 1990 se stal spoluzakladatelem a prvním ředitelem transdisciplinárního pracoviště Centra pro teoretická studia UK a AV ČR. Nadále se zabýval kybernetikou, umělou inteligencí a kognitivní vědou, v souvislosti s transdisciplinaritou jej zajímala komplexita, emergentní jevy, vznik vědomí. V roce 1992 se habilitoval v oboru umělá inteligence. Do roku 2018 přednášel na MFF UK. Od srpna 1990 do konce roku 2019 byl šéfredaktorem časopisu Vesmír. Stejně jako v CTS i zde svou zvídavostí i šíří zájmů propojoval vědce, filosofy, umělce. Editoriály, které psal do Vesmíru, daly vznik knihám Otevřené oči a zvednuté obočí, Zvednuté oči a zjitřená mysl a Zjitřená mysl a kouzelný svět. Soupis významnějších publikací: (Úplný soupis publikací I.M. Havla je v knize Jana Lukeše „Právě proto, že jsem“ – rozhovor s Ivanem M. Havlem). Havel, I. M., The theory of regular events, I., II., Kybernetika 5, 400–419, 520–544, 1969. Havel, I. M., Strict deterministic languages, Ph.D. dissertation, Department of Computer Science, California at Berkeley, December 1971. Štěpánková O., Havel, I. M., A logical theory of robot problem solving, Artificial Intelligence 7, 129–161, 1976. Havel, I. M., On branching and looping I., II., Theoretical Computer Science 10, 273–295, 1980. Havel, I. M., Robotika. Úvod do teorie kognitivních robotů, Státní nakladatelství technické literatury, Praha 1980. Havel, I. M., Hájek P., Filosofické aspekty strojového myšlení, in Sborník SOFSEM’83, 7–64, 1983. Havel, I. M., Podivná setkání, In: Laudatio Z. N., samizdat 1982. Havel, I. M., Palouš M., Neubauer Z., Svatojanský výlet, s. 145–157 in Laudatio R. P., Edice Expedice, sv. 196. Později též jako kniha Svatojanský výlet, Malvern & B. Just, Praha 1999. Havel, I. M., Způsoby poznání, s. 137–148 in: samizdat, Edice Expedice, sv. 209, 1985. Později tiskem in: Hostina, Sixty-Eight Publishers, Totonto 1989, též in: Slovenské pohľady č. 7, 1991. Angl. Překlad pp. 222–232 in Good-bye, Samizdat, ed. M. Goetz-Stankiewicz, NorthwesternUniversity Press, Evanston, Ill. 1992. Neubauer Z. Havel I. M., Sidonia a Sakateky dialogů patero, ed. D. Bohdan, samizdat Praha 1986. Později rozšířené tiskem in: Sidonia a Sakateky Čtrnáctero vykročení, SOFIS, Praha 2004. Havel I. M., Artificial Thought and Emergent Mind, pp. 758–766 in Proc. IJCAI’93, Morgan Kaufman Profesional Book Center, Denver, SO, USA, 1993. Havel I. M., Scale Dimensions in Nature, Int. J. of General Systems 24, 295-324, 1996/3. Havel I. M., Arsemid, Hrnčířství a nakl. Michala a Evy Jůzových, Praha 1997, druhé rozšířené vydání: KANT, Praha 2004. Třetí, třikrát rozšířené vydání KANT – Karel Kerlický, Praha 2016. Havel I. M, Otevřené oči a zvednuté obočí, Vesmír, Praha 1998. Havel I. M., Causal Domains and Emergent Rationality, pp. 129–151 in: Rationality and Irrationality, B. Brodgaard and B. Smith (eds.), Vienna 2001, öbv & hpt. Havel I. M., Přirozené a umělé myšlení jako filosofický problém, s. 17–75 in Umělá inteligence III., ed. V. Mařík a kol., Academia, Praha 2001. Havel I. M., Modality subjektivně prožívaných situací, s. 159–178 in Kognice a umělý život IV., J. Kelemen a V. Kvasnička (eds.), Slezská univerzita v Opavě, Opava 2004. Havel I. M., Zvednuté obočí a zjitřená mysl. Dokořán, Praha 2005. Havel I. M., A structure of Experienced Time, pp. 163–188 in Endophysics, Time, Quantum and Subjective, R. Buccheri et al. (eds.), World Scientific Publisching Co., 2005. Ajvaz M., Havel I. M., Snování. Rok dopisů o snech. Nakl. Pavel Mervart, Červený Kostelec 2008. Havel I. M., Sixty years of cybernetics: Cybernetics still alive, Kybernetika 44, 314, 2008/3. Ajvaz M., Havel I. M., Sindibádův dům. Korespondence o epizodických situacích a také o dvou scénách, okamžicích, vzpomínkách, počátcích, prostředcích a koncích, pobřežních skaliskách, vlnách a gejzírech, hromadách, skládkách, patafyzických a jiných strojích, nakl. Pavel Mervart, Červený Kostelec 2010.  Havel I. M., Dopisy od Olgy. Knihovna Václava Havla, Praha 2010. Havel I. M., Epizodické situace našeho života, s. 213–238 in Spor o přirozený svět, eds. B. Velický et al., Filosofia, Praha 2010. Havel I. M., Seeing numbers, pp. 312–329 in Best Writings on Mathematics 2010, ed. Mircea Pitici, Princeton University Press 2011. Havel I.M., Cestou k inteligenční singularitě, s. 183–217 in Hlavou zeď – Úvahy nad civilizací a její budoucností, ed. A. Pelán, dybbuk, Praha 2011.  Havel I. M., Slavná Hofstadterova kniha konečně v českém překladu, část I., Vesmír 91, 746, 2012/12, část II. Vesmír 92, 51, 2013/1 , část III. Vesmír 92, 116, 2013/2, část IV. Vesmír 92, 181, 2013/3. Havel I. M., Zjitřená mysl a kouzelný svět, Dokořán, Praha 2013. Havel I. M., Odvěta, s. 171–237 in Protázky a odvěty, Lucerna & nakl. Lidové noviny, Praha 2015. Havel I. M., Model prožívaného času podle Petra Vopěnky, Filosofický časopis 2016/4, s. 539-560. Havel I. M., Mitášová M., Vnímání pohybu: Reflektovaný a nereflektovaný pohled v souvislosti s architekturou, s. 64–70 in Kognicia a umelý život 2017, eds. I. Farkaš a kol., Univerzita J.A. Komenského, Bratislava 2017. Ajvaz M., Havel I. M., Pokoje u moře. Sedm let korespondence o živém těle, o trčení a vyčnívání, o větvení a sítích, o písmenech, houbách, kostrách a kostlivcích, o škálových úrovních, o agregátech a seskupeních, o totalizaci a diferenciaci, o prázdnotách, o přidávání a odebírání, o moři, o vánicích a sněhových vločkách, o obrazech, o jednotícím rozvrhu a nakonec i o rámech uvnitř rámů. Nakl. Pavel Mervart, Červený Kostelec 2017. Havel I. M., Zápisky introspektora, OIKOYMENEH, Praha 2018
Havel Ivan M.

Doporučujeme

Havlův Vesmír

Havlův Vesmír

Ivan Boháček  |  31. 5. 2021
Vesmír byl časopis mých prvních námluv s vědou a dodnes se pamatuji, jak jsem jako kluk měl vždy radost z nového čísla…
35 let s HIV

35 let s HIV

Eva Bobůrková  |  31. 5. 2021
Přítomnost nové záhadné choroby oficiálně potvrdily americké úřady, když 5. června 1981 oznámily podezřelý výskyt pneumocystické pneumonie u pěti...
Fluor v organických sloučeninách

Fluor v organických sloučeninách

Jaroslav Kvíčala  |  31. 5. 2021
Z přírody známe jen asi dvacet organických sloučenin obsahujících atomy fluoru. Člověk jich ale syntetizoval mnohem víc a organofluorová chemie...

Předplatným pomůžete zajistit budoucnost Vesmíru

Tištěná i elektronická
verze časopisu
Digitální archiv
od roku 1994
Speciální nabídka
pro školy a studenty

 

Objednat předplatné