Trikrát o limitoch: Informatika

Jeden z nich bol plachý a druhý, aspoň vtedy, odmeraný a aj keď sa stretli naživo, nebola z toho vášnivá diskusia. Škoda, kým Kurt Gödel spravil dieru do sveta odhalením neúplnosti matematiky, Alan Turing objavil diery v informatike.

Kurt Gödel mal v niečom ľahšiu prácu: matematika už v tom čase existovala ako veda v podstate tisícročia, informatika v čase Turingovho objavu ešte neexistovala. Ako rozumný odhad jej začiatku môže slúžiť rok 1937, vtedy Claude Shannon napísal svoju prácu, aj keď prvé úvahy o limitoch výpočtových strojov siahajú až do polovice 19. storočia.

Dešifrovanie a inteligencia strojov

Široká verejnosť si A. Turinga spája hlavne s dvomi úspechmi. Po prvé, pomohol rozlúštiť nemecký systém šifrovania Enigma počas druhej svetovej vojny, čím ju podľa odhadov odborníkov pomohol výrazne skrátiť a zachránil množstvo životov. Okrem geniálneho vhľadu do šifrovania (ktorému sa mimochodom venoval aj C. Shannon) mu pomáhal aj stroj Bombe, ktorý v niektorých aspektoch pripomínal počítač. Na dnešné pomery však bol ešte vždy prevažne mechanický, elektrina mu slúžila len na pohyb. Digitalizácia informácie nastala až vďaka Shannonovej práci, ktorá prepojila svet informácií s elektrinou.

Druhý známy Turingov výsledok v súčasnosti voláme Turingov test. Zamýšľal sa nad tým, či by sa mohli zamýšľať stroje. Navrhol test, ktorý si v modernej adaptácii môžete predstaviť tak, že si s niekým píšete cez internet a ak neviete určiť, či si píšete s človekom, alebo so strojom, tak stroj prešiel Turingovým testom. V 19. storočí o mysliacich strojoch premýšľala Ada Lovelaceová a jej záver bol taký, že stroje nie sú schopné originality, chrúmu a trávia len to, čím sme ich nakŕmili. Ak sledujete súčasné diskusie o umelej inteligencii a o tom, či naozaj myslí, alebo nie, tak viete, že A. Turing aj A. Lovelaceová trafili klinec po hlavičke a predbehli dobu.

Nezostrojiteľný program

Fascinujúci Turingov výsledok, ktorým mal tak blízko Gödelovmu dielu, sa týkal limitov programov. Vieme si predstaviť nejaký program, ktorý sa nedá zostrojiť? A. Turing našiel veľmi jednoduchý príklad – program, ktorý vám o inom programe povie, či úspešne zbehne do konca, alebo nie. Ukončenie programu sa označuje slovom Halt a tak sa takýto program nazýva Halting program. Ako dokázal A. Turing jeho neexistenciu? Ukázal, že keby existoval, viedol by k paradoxom.

Tento výsledok má presah aj do matematiky. David Hilbert dal výzvu ukázať, či existuje algoritmus, ktorý pre dané matematické tvrdenie dokáže zistiť, či je pravdivé, alebo nie. Program zbehne do konca v konečnom počte krokov je však tiež matematické tvrdenie a A. Turing ukázal, že program, čo by takéto niečo dokázal, neexistuje.

Informatike sa tak podarilo niečo, čo máloktorej inej vednej disciplíne. Ešte ani neexistovala a už bola hlboko prepojená s matematikou – v dobrom aj zlom. Samozrejme, to nie je prekvapivé, lebo na základnej úrovni je informatika vetvou matematiky.

Autor článku: Samuel Kováčik
Fakulta matematiky, fyziky a informatiky
Univerzita Komenského v Bratislave
Viac podobných článkov nájdete na webe vedator.space. Vedátora môžete sledovať aj prostredníctvom bezplatnej mobilnej aplikácie.

---

Súťažná otázka

Ak nám do 30. novembra 2025 pošlete správnu odpoveď na otázku:

Ako sa volal šifrovací stroj používaný nemeckou armádou počas druhej svetovej vojny?

zaradíme vás do žrebovania o novú knihu Samuela Kováčika: Limity poznania z Vydavateľstva Slovart. Svoje odpovede posielajte na adresu redakcie: odpovednik@quark.sk alebo Quark, Lamačská cesta 8A, 811 04 Bratislava.