1    Cvičenie 2
Na predchádzajúcom cvičení sme definovali náš výpočetný model (while programy) a skúmali jeho sémantiku. Na to aby sme mohli kombinovat rôzne programy sme používali syntaktické operácie. Jedna nevýhoda tohoto prístupu je, že nás obmedzuje iba na programy ktoré sme už napísali. Druhá nevýhoda je, že takýto prístup vždy viaže implicitne dohromady program a sémantickú funkciu. Z hladiska vyčíslitelnosti nás často krát nezaujíma ako vyzerá konkrétny program ktorý nejakú funkciu počíta, len to, že existuje.
Prvým krokom k tomu, aby sme tieto beriéry odstránili je zavedenie pojmu vyčíslitelná funkcia. Vyčíslitelná funkcia je taká funkcia, ktorá je sémantickou funkciou nejakého programu. Inak povedané, ak je funkcia vyčíslitelná, existuje nejaký program ktorý ju počíta. Môžeme si dokonca všimnut že takýchto programov bude nekonečne vela (stačí přidávat rôzne množstvo nič nerobiacich inštrukcií). Je dôležité mat na pamäti že stále ide obecne o parciálne funkcie, keďže programy môžu cykliť.
Príklad: Uvažujme funkciu a ktorá pre vstup k vracia 1 ak desatinný rozvoj čísla tt obsahuje aspoň k po sebe idúcich číslic 5 a 0 inak. Teda napr. ak by sa v rozvoji tt niekde nachádzala postupnost 3.14 ... 42555502 ..., tak a(4) = 1. Je takáto funkcia vyčíslitelná?
Áno, takáto funkcia je vyčíslitelná. Bud existuje nejaká konštanta l taká že desatinný rozvoj tt obsahuje postupnost číslic 5 dlžký l, ale už neobsahuje žiadnu dlhšiu postupnost, alebo takáto konštanta neexistuje (teda desatinný rozvoj obsahuje postupnosti stále väčšej a väčšej dĺžky, bez obmedzenia). Pokial l neexistuje, a je konštantná funkcia ktorá vždy vracia 1 a teda je vyčíslitelná. Pokial l existuje, a je tiež vyčíslitelná bez ohladu na hodnotu l, keďže vracia 1 pre k < l a 0 pre k > l.
Samozrejme, zistiť či l existuje alebo nieje ťažký problém ktorý pre tt nemusí byť nutne riešiteľný. Nevieme teda ktorý program je korektnou implementáciou funkcie a. Vieme ale že jeden z hore uvedených programov určite a implementuje korektne, teda a je vyčíslitelná.
1.1 Numerácie
Aby sme sa mohli odvolávať na vyčíslitelné funkcie v našich while programoch, potrebujeme nej ak zakódovať vyčíslitelnú funkciu do číslenej hodnoty s ktorou môžeme ďalej pracovať vo while programe. Za týmto účelom bude slúžiť tzv. numerácia.
Numerácia nejakej množiny A je (väčšinou totálna) surjektívna funkcia nuniA '■ N —> A. Teda pre každý prvok a € A existuje aspoň jeden index i € N t.ž. numA(i) = a. Potom hovoríme že i je indexom a (index nie je jednoznačný, každé a môže mať viacero indexov, ale vždy musí mať aspoň jeden). Obecne nie je nutné aby bola numerácia vyčíslitelná, ale väčšinou je to nutné aby sa dala na niečo ďalej aj použiť.
Príklad Označme P ako množinu všetkých prvočísel. Funkcia
1
I i   2 je prvočíslo numr(t) = < .
I á mak
je numeráciou množiny P. Každé prvočíslo má aspoň jeden index (seba samého), pričom prvočíslo 3 ich má dokonca nekončené vela (seba samého a všetky neprvočísla). Takáto numerácia je aj vyčíslitelná, keďže test na prvočíslenost nie je problém implementovat ako while program.
Na prednáške bola potom zavedená numerácia všetkých while programov pomocou prvočísleného kódovania. Tá je z technického hladiska o niečo zložitejšia ako hore uvedený triviálny príklad, z intuitívneho hladiska ale nejde o nič prevratné. Každý program ktorý dnes napíšete v nejakom programovacom jazyku na počítači sa ukladá vo forme binárneho retazca ktorý môžete interpretovat ako jedno (velké) číslo. Na základe takéhoto kódovania je potom tiež možné definovat numeráciu programov. Takáto numerujúca funkcia bude parsovat číslo na vstupe ako retazec, pričom pokial tento retazec reprezentuje validný program v danom jazyku, výsledkom bude tento program. Ak parsovanie zlyhá (retazec nie je platný program), funkcia vráti nejaký dopredu definovaný program.
Takýmto spôsobom dokážeme intuitívne definovat numeráciu programov pre lubovolný jazyk pre ktorý existuje ASCII (alebo Unicode) zápis a vhodný parser, pričom identifikátorom každého programuje práve číslo dané jeho ASCII reprezentáciou. Numerácia z prednášky potom robí velmi podobnú vec, akurát miesto zretazovania ASCII znakov využíva prvočíslené kódovanie.
Numeráciu (unárnych) vyčíslitelných funkcií potom definujeme tak, že index i sa mapuje na unárnu sémantickú funkciu programu s indexom i. Takúto vyčíslitelnú funkciu s indexom i budeme potom označovat Lpi a odpovedajúci program bude Pi. Teda každá vyčíslitelná funkcia má aspoň jeden index (keďže existuje program ktorý ju počíta a ten má index), ale zároveň má nekonečne vela indexov, keďže existuje nekonečne vela programov ktoré ju počítajú (Táto definícia je samozrejme platná len pre unárne funkcie, nie je ale problém ju zobecnit pre lubovolný počet argumentov).
Všimnime si, že otázka či Lpi = ipj bude zjavne velmi tažká (ale Pi = Pj je jednoduchá), keďže musíme rozhodnut či dva rôzne programy dané indexami i a j počítajú tú istú funkciu. Teda pri tejto reprezentácií môžeme použit klasickú číslenú rovnost na rozhodnutie otázky "sú i a j rovnaké implementácie tej istej funkcie?", rovnako ako môžeme použit synatktickú rovnost programov. Nijak to ale neulahčuje otázku "sú i a j dve rôzne implementácie tej istej funkcie?". Toto je taktiež primárny dôvod prečo definujeme "len" numeráciu a nie kompletnú bijekciu. Určite by bolo krajšie keby sme mali pre každú funkciu práve jeden unikátny identifikátor, na to by sme ale museli vediet rozhodnut "tažký" problém rovnosti funkcií.
Všimnime si taktiež, že z existencie takejto numerácie vyplýva, že funkcia a z prvého príkladu má aspoň jeden index v našej štandardnej numerácií. Teda formálne povedané, existuje a € N t.ž. a = ipa (aj keď stále nevieme aká je presná hodnota a keďže nevieme ktorý program skutočne počíta a).
2
Príklad: Uvažujme funkciu /3(k) = 1 — j(k) kde 7 je nejaká nešpecifikovaná vyčíslitelná funkcia. Je /3 vyčíslitelná funkcia? Keďže 7 je vyčíslitelná, existuje index g t.ž. 7 = ipg. Potom program pre /3 môžeme skonštruovat ako Pg; xi = 1 — xi kde Pg je program počítajúci ipg. /3 je teda vyčíslitelná.
1.2   Univerzálna funkcia
V predchádzajúcom príklade sme využil fakt že 7 je dopredu známa. Čo ak by sme ale chceli napr. umožnit vložit funkciu 7 ako vstup funkcií /3? /3 môže samozrejme ako vstupný parameter brat index nejakej vyčíslitelnej funkcie, so súčasnými znalostami ale nemôžeme skonštruovat program pre /3 bez znalosti programu pre túto funkciu. Každý index funkcie ale v sebe kóduje zároveň aj jej program. Teda čo by sme potrebovali je nejaký "interpet" ktorý by dokázal "spustit" funkciu danú jej indexom.
Tento interpret sa nazýva univerzálna funkcia: Q(i,x) = tpi(x) (univerzálna funkcia teda berie index funkcie ktorá sa má spočítat a vstup s ktorým sa má táto funkcia spustit). Samotný dôkaz jej vyčíslitelnosti je opat pomerne technický, ale že takáto funkcia existuje a je vyčíslitelná (nie však totálna, ak Lpi cyklí, bude cyklit aj univerzálna funkcia) opat asi nie je velmi prekvapivý (napísat v pythone interpet pythonu je asi pomerne pracné, ale určite sa to dá).
Aby sme mohli použit univerzálnu funkciu vo while programoch, definujeme si makro vari = ^(varg, var3) kde sa univerzálna funkcia nahradí programom ktorý ju počíta. Môžeme si rovno definovat aj makro pre zápis vari = 9?var2 (var3) ktoré opát len zavolá univerzálnu funkciu.
Príklad: Je funkcia fi(x,y) vyčíslitelná?
Samozrejme. Uvažujme program $(x, x);xi = y. Najskôr sa spustí funkcia s indexom x a vstupom x. Pokial tento výpočet skončí, vrátime y, inak samozrejme celý program cyklí.
Príklad: Dokážte že $(2, x) = ipi(x,Q): Q(i,x) = tpi(x) = [P]í({^i <— a;})(xi) = [P]i({xi <— a;,X2 <— 0})(xi) = ipi{x, 0) (použili sme definíciu univerzálnej funkcie, definíciu sémantickej funkcie while programu a fakt, že nedefinované premenné sú v každej valuácií nastavené na nulu).
1.3   Veta o parametrizácií
Keď už vieme že môžeme funkcie "spúštat", asi by sme chceli ešte ukázat že ich vieme aj kombinovat. Inak povedané, že existuje spôsob ako nejaké existujúce funkcie/programy spojit do jednoho pomocou iného programu. Teda že existuje "kompilátor" ktorý dokáže pracovat s programami, modifikovat ich a t vo rit nové.
3
Za týmto účelom existuje veta o parametrizácií (ktorej dôkaz je opát primárne o práci s kódovaním programov): Existujú totálne vyčíslitelné funkcie s™ také že:
)(ž/l,---
X n) = tPi(xi, ■ ■ ■ ,Xm,ÍJl, ■ ■ ■ ,ÍJm)
Intuitívne môžeme túto vetu chápat tak, že funkcia Lpi predstavuje istú formu vzoru/predlohy/šablóny do ktorej "kompilátor" s dosadzuje hodnoty x\,..., xn a vyrába z nej nový program. Teda transformácia/kombinácia programov ktorú sme schopní popísat v šablóne Lpi sa dá vykonat programovo pomocou s.
Príklad: Ukážte že funkcia g(i,j) kde Lpg^j^(x,y) = ipi(x,y) + ipj(x,y) je totálne vyčíslitelná. Ako vidíme, funkcia g berie dve funkcie a vracia novú funkciu, ktorá počíta ich súčet. Teda g nepočíta samotný súčet, ale vracia program ktorý po stupstení (s ďalšími parametrami) spočíta tento súčet.
Uvažujme nasledujúci program Pc ako našu šablónu:
a <- $(i, x, y); b <- $(j, x, y); xx <- a + b;
Potom zjavne tpc(i, j, x, y) = ipi{x, y)+ifj (x, y). Použitím vety o parametrizácií teda môžeme definovat g(i,j) = s'^c, i, j) (tu je c známa konštanta - identifikátor našej šablóny).   Keďže s je totálne vyčíslitelná, bude aj g totálne vyčíslitelná (spustíme s s vstupnými argumentami a konštantou c).
Pozn.: Takýto dôkaz by sa samozrejme dal vykonat aj bez vety o parametrizácií. V konečnom dôsledku by sa ale človek musel odvolávat na pomerne netriviálne tvrdenia o tom čo a ako by dokázal kódovat.
1.4   Nevyčíslitelné funkcie
Zatial sme sa primárne zaoberali tým ako ukázat že niečo je vyčíslitelné. Samozrejme ale existuje vela funkcií ktoré vyčíslitelné nie sú: Príklad: Ukážte že funkcia halt(i) nie je vyčíslitelná:
Dôkaz povedieme sporom. Pre spor predpokladajme že funkcia halt je vyčíslitelná. Teda existuje index h t.ž. ip^ = halt. Uvažujme potom funkciu
flip(i):
Funkcia flip je zjavne tiež vyčíslitelná (spustí sa funkcia halt a podlá výsledku program buď cyklí alebo skončí), teda existuje / t.ž. iff = flip. Co sa ale stane ak funkcií flip dáme na vstup samú seba?
Máme len dve možnosti, buď sa flip zacyklí alebo nie.
4
. flip(f) = JL => halt(f) = 1 => w(f) ± JL => /%>(/) ^ _L
• //ip(/) = 1 => halt(f) = O => <pf(f) = _L => //ip(/) = JL
Teda ak sa /Zip zacyklí, tak sa nezacyklí a ak sa nezacyklí, tak sa zacyklí. To je zjavne spor (neexistuje funkcia ktorá zároveň cyklí a zastavuje) a náš predpoklad že halt je vyčíslitelný bol teda nesprávny. Teda halt nie je vyčíslitelná.
Príklad: Ukážte že funkcia f2 (x, y) nieje vyčíslitelná.
f2(x,y)=\y ^{X)^L J V ,y;     [0 inak
f'2 je určite velmi podobná funkcií halt, mohli by sme teda dôkaz viest podobným spôsobom ako v prípade funkcie halt. Keďže ale už máme dokázané že halt nie je vyčíslitelná, môžeme to využit a postup si trochu zjednodušit:
Pre spor predpokladajme že f2 je vyčíslitelná. Potom ale platí že halt (i) = /2(i, 1). Teda ak existuje program pre /g, existuje aj program pre halt. To sme ale v predchádzajúcom príklade vyvrátili, teda /g tiež nemôže byt vyčíslitelná.
Inak povedané, práve sme dokázali že pre while programy neexistuje algoritmus ktorý by vždy presne v konečnom čase určil či program zastaví alebo nie. Takéto tvrdenie sa dá potom dokázat aj pre iné dostatočne silné programovacie jazyky. Vela užitočných programov samozrejme tento problém nemá: pokial sa obmedzíme napr. len na for-cykly so známym počtom opakovaní, naše programy vždy zastavia a stále budeme schopní zoradovat čísla alebo prehladávat grafy, ale nebudeme môct naimplementovat Collatzovu domnienku z prvého cvičenia.
To samozrejme vyvoláva otázku: Prečo sa teda nezaoberáme len totálnymi funkciami? Z praktického hladiska by určite bolo skvelé keby sme mali programovací jazyk v ktorom by sme mohli napísat programy pre všetky totálne funkcie. Bohužial, (vyčíslitelný) jazyk ktorý by dokázal popísat všetky totálne funkcie tiež existovat nebude:
Príklad: Dokážte, že neexistuje efektívna numerácia totálnych vyčíslitelných funkcií s univerzálnou funkciou. Teda že neexistuje numerácia ipi s vyčíslitelnou univerzálnou funkciou ty (i, x) = tpi(x) kde tpi sú všetky totálne vyčíslitelné funkcie.
Dôkaz sporom. Predpokladajme že existuje táto numerácia ipi a univerzálna funkcia ty. Potom uvažujme funkciu ui(x) = ty{x,x) + 1. Funkcia ui je určite totálna (ty je totálna, keďže počíta totálne funkcie) a je tiež vyčíslitelná (keďže ty je vyčíslitelná). Teda funkcia ui musí byt súčastou takejto numerácie, keďže je totálna a vyčíslitelná, teda ui = ipa pre nejaký index o. Potom ale platí že ui(o) = ty(o, o) + 1 = ipo(o) + 1 = w(o) + 1. Z tohoto sporu potom vyplívá že náš predpoklad bol nesprávny a takáto univerzálna funkcia ty existovat nemôže.
Pozn.: Takýto dôkaz nutne nehovorí že numerácia totálnych funkcií neexistuje. Dôležitá vlastnost je tu vyčíslitelnost. Ak by sme nepožadovali vyčíslitelnost, tak funkciu ako ui skonštruovat nemôžeme, lebo nemáme k dispozícií ty. Z praktického hladiska by nám bol ale takýto výsledok dost zbytočný, keďže pomocou neho nič "nenaprogramujeme".
5