V 80. rokoch, za železnou oponou, krajiny východného bloku organizovali svoje ekonomiky prostredníctvom Rady vzájomnej hospodárskej pomoci (RVHP), rozdeľujúc výrobné úlohy medzi členské štáty. Počítače a ich súčasti neboli výnimkou. Bulharsko dostalo za úlohu vyrábať počítačové pevné disky—čo viedlo k výstavbe úplne novej továrne na zelenej lúke. Továreň si rýchlo vybudovala povesť naprieč východnou Európou: jej pevné disky boli notoricky nepredvídateľné, citlivé dokonca na zmeny teploty v miestnosti.

V tom čase na Matfyze v Bratislave dostal mladý slovenský študent menom Róbert Szelepcsényi za úlohu napísať softvérové ovládače práve pre tieto bulharské disky. Zakaždým, keď sa pokúsil čítať prvý sektor dát, chybný hardvér mohol umiestniť magnetickú hlavu nepredvídateľne—na správny sektor, alebo možno o jeden či dva sektory vedľa. Szelepcsényi vymyslel elegantné riešenie: vždy keď sa jeho softvér spustil, najprv prečítal špeciálny marker z miesta, kde pristála hlavička disku, čím určil jej skutočnú pozíciu. Potom zodpovedajúcim spôsobom opravil posun, čo umožnilo zvyšku systému správať sa, akoby bol disk celý čas spoľahlivý.

O roky neskôr táto praktická skúsenosť poskytla Szelepcsényimu pohľad, ktorý priniesol do teoretickej informatiky, inšpirujúc prelomový dôkaz známy dnes ako Immerman–Szelepcsényiho teorém. Tento dôkaz vyriešil dlhodobú hádanku: či problémy riešiteľné nedeterministicky (uhádnutím riešení a ich overením pomocou obmedzenej pamäte) mohli tiež riešiť svoje komplementárne problémy—problémy, kde sú odpovede "áno" a "nie" vymenené—v rovnakom (lineárne) obmedzenom pamäťovom priestore. Szelepcsényiho pohľad odrážal jeho techniku ovládača: aj keď výpočet okamžite nepoznal svoju presnú situáciu, mohol nedeterministicky "uhádnuť" stav a potom metodicky overovať správnosť systematickou kontrolou a počítaním. Rovnako ako kedysi premenil chybný hardvér na niečo spoľahlivé, demonštroval, ako zdanlivo obmedzené výpočtové modely mohli systematicky overovať svoje komplementy.

Je to trochu "don't trust" (bulharskému* pevnému disku), "verify" (že som na sektore, kde chcem byť).

Aj keď sú produkty nekvalitné, existujú šikovné spôsoby, ako využiť túto myšlienku.

Používam to často pri programovaní, bola to jedna z najviac inšpirujúcich lekcií a je mimoriadne užitočná v oblasti umelej inteligencie. Nechajte AI vygenerovať odpoveď, overte, či to správne pochopila. Robím to často. Napríklad môj projekt rss2podcasts prevádza článok do formy vhodnej na prečítanie, potom overuje, či LLM nezmenila význam, potom vykoná prevod textu na reč pre daný úsek a následne spätný prevod reči na text, aby overil, či bol správne vygenerovaný (čo je zvláštne, často nie je!).

(*) Bulharsko prešlo dlhú cestu od sovietskych čias, produkty boli v tom čase nekvalitné v celom sovietskom bloku.

https://en.wikipedia.org/wiki/Immerman%E2%80%93Szelepcs%C3%A9nyi_theorem