{{TIN064 Skripta}}
Skutečný úvod k těmto wiki-skriptům je [[TIN064 wiki-skripta|zde]], tato stránka by měla sloužit spíš jako takový náhled do problematiky, návod před studiem,... ale nevěděl jsem, jak to nazvat líp.
Některé pojmy, o kterých se píše na této stránce (zvlášť ke konci), budou podrobně (exaktně) vysvětleny v následujících kapitolách. Myslím si ale, že je užitečné mít už předem aspoň nějakou mlhavou představu, ono to pak snadněji do sebe zapadá. Představu o tom, k čemu ta vyčíslitelnost vlastně je, si můžete udělat (samozřejmě krom pravidelného navštěvování přednášek) z [http://atrey.karlin.mff.cuni.cz/~johanka/vyuka/pohadky_vycislitelnost.html Johančiny pohádky první].
Některá fakta mohou připadat některým vyučujícím (nejen vyčíslitelnosti) natolik zřejmá, že je raději ani nezmiňují, a když, tak jen jako poznámku na okraj. Člověk by na ně při učení nakonec taky přišel, ale přesto snad neuškodí, když některá zmíním předem.
== Čísla, funkce, programy ==
=== <math>0 \in \mathbb{N}</math>. Číslo = přirozené číslo ===
Ve vyčíslitelnosti (stejně jako v teorii množin a pár dalších vědách) se jako přirozená čísla označuje množina <math>\mathbb{N}=\{0,1,2,...\}</math>. Je to jednodušší, než vždy psát <math>\mathbb{N} \cup \{0\}</math>. S jinými čísly (celá, reálná, komplexní,...) se ve vyčíslitelnosti nepracuje (pokud ano, tak se zakódují do přirozeného čísla), takže dál v tomto textu se pojmem ''číslo'' rozumí vždy ''přirozené číslo'' (včetně nuly).
=== Co to je funkce ve vyčíslitelnosti? ===
Funkcí se myslí vždy tzv. aritmetická funkce, která k-tici čísel přiřazuje jedno číslo, tedy <math>f: \mathbb{N}^k \to \mathbb{N}</math>. Tato funkce navíc nemusí být totální (česky úplná), tedy může být parciální (česky částečná), což znamená, že nemusí být "všude definovaná".
V matematice se zápisem <math>f: A \to B</math> obvykle myslí, že definiční obor <math>f</math> je <math>A</math> (zapisujeme <math>dom(f)=A</math>). Ve vyčíslitelnosti, ale platí <math>dom(f) \subseteq A</math>.
Ještě jinými slovy: pro některé k-tice nemusí být hodnota <math>f</math> definována a tyto k-tice pak nepatří do definičního oboru <math>f</math>.
=== Funkce lze chápat jako programy a naopak ===
Funkci <math>f: \mathbb{N}^k \to \mathbb{N}</math> si můžeme představit jako program, který na vstupu dostane k čísel a vrátí jedno číslo. Tedy schematicky:
program_pro_f(x_1,...,x_k){
...
return(y);
}
Každý konečný matematický objekt (např. celé číslo, slovo nad nějakou abecedou, dvojice čísel,...) lze zakódovat jako jedno (přirozené) číslo. (Konkrétní metody kódování budou popsány dále). Vezmeme-li si tedy program (který nemá žádné side-efekty, jako že by něco tiskl atd., a jeho návratová hodnota závisí jen na vstupních parametrech), tak ho můžeme chápat jako funkci <math>\mathbb{N}^k \to \mathbb{N}</math>.
==== nulární funkce ====
U programů je celkem běžné, že nemusí mít vstup. U funkcí by tomu odpovídaly nulární funkce, které se občas zavádějí (např. v algebře), aby se nemuselo zvlášť ošetřovat konstanty. Mohli bychom si je zavést i ve vyčíslitelnosti, ale mám pocit, že se to na přednášce tak nedělá, protože se bez nich obejdeme. Nic nám totiž nebrání v tom, abychom si vyrobili funkci, která svůj parametr vůbec nepoužije (funkce je konstantní).
=== Co znamená, že program či funkce konverguje či diverguje? ===
Jistě znáte nějaký program, který se pro nějaký vstup zacyklí a nikdy se nezastaví (<tt>if (x_1 == 42) while (true) do {}</tt>). Pokud se program zacyklí pro všechny vstupy, říkáme, že je to ''prázdný program'', kterému odpovídá ''prázdná funkce'', což jest funkce f taková, že <math>dom(f)=\emptyset</math>.
Aby to znělo učeněji, tak místo ''program se zacyklí'' (resp. ''funkce není definována'') říkáme ''program diverguje'' (resp. ''funkce diverguje'') a píšeme <math>f(x_1,...,n_n)\uparrow</math>. Obdobně místo ''program se zastaví (po konečném počtu kroků)'' (resp. ''funkce je definována'') říkáme, že ''program konverguje'' (resp. ''funkce konverguje'') a píšeme <math>f(x_1,...,n_n)\downarrow</math>. Například pro funkci <math>f</math> jedné proměnné tedy máme <math>dom(f)=\{x|f(x)\downarrow\}</math>.
== Funkce, predikát, množina, relace ==
=== Predikát jako funkce ===
Predikát k proměnných <math>P(x_1,...,x_2)</math> je nějaké tvrzení o těchto proměnných, které může být pravdivé či nepravdivé. Např. <math>P(x_1,x_2)</math>="(<math>x_1</math> je prvočíslo) a (<math>x_2 > x_1)</math>". Ve vyčíslitelnosti budou proměnnými vždy čísla a pravdu reprezentujeme jako 1, nepravdu jako 0. Predikáty lze tedy chápat jako funkce jejichž obor hodnot je {0,1} (zapisujeme <math>rng(f)=\{0,1\}</math>).
=== Množina jako predikát ===
Množinu lze chápat jako soubor prvků, které mají nějakou vlastnost P, tedy množina <math>M = \{x | P(x) \mbox{ platí}\}</math>. Pokud nebude uvedeno jinak, bude v následujícím textu pojem ''množina'' znamenat vždy ''množina (nějakých) přirozených čísel''. Každý predikát jedné proměnné odpovídá nějaké množině a naopak. Jelikož už víme, že predikáty odpovídají funkcím, tak nás nepřekvapí, že množiny odpovídají funkcím jedné proměnné s oborem hodnot {0,1}. Takovouto funkci nazýváme ''charakteristická funkce množiny'' a pro množinu M píšeme <math>C_M: \mathbb{N} \to \{0,1\}</math> a
<math>C_M(x) =
\begin{cases}
1 & \mbox{pro }x \in M \\
0 & \mbox{pro }x \notin M
\end{cases}</math>.
Všimněme si, že charakteristická funkce je z definice totální.
=== Relace jako predikát ===
Relace na množinách <math>A_1,..., A_n</math> je podmnožina jejich kartézského součinu. Ve vyčíslitelnosti jako množiny <math>A_i</math> bereme (kupodivu opět:-)) <math>\mathbb{N}</math>. Relace na n množinách je v důsledku to samé jako predikát n proměnných. Nenechte se tedy zmást, že se občas místo predikátu používá relace. (Zajímavé, že zatímco v teorii množin se odvozuje funkce z relace, zde bereme funkci jako základní pojem a relace převádíme na funkce.)
== ČRF a další trojpísmenné zkratky ==
Jak jsem již předeslal, exaktní definice ČRF, ORF a spol. se nacházejí v následujících kapitolách, ale přijde mi šikovné, když si člověk napřed udělá nějaký rámcový přehled, případně si nové termíny propojí se znalostmi, které už má z jiných přednášek (hlavně [[Automaty a gramatiky]]).
=== ČRF = částečně rekurzivní funkce ===
Lze dokázat (viz dále), že ke každému programu (v libovolném prog. jazyce, či abstraktním modelu jakým je např. Turingův stroj — dále jen TS) jde zkonstruovat ekvivalentní ČRF. Slovem ''ekvivalentní'' se zde myslí to, že program i funkce dojdou pro libovolný vstup ke stejnému výsledku, délka výpočtu (počet kroků, ať už to znamená cokoli) ovšem může být řádově delší. To je ale ve vyčíslitelnosti běžné: zajímá nás jen co ne/jde spočítat a jakými prostředky, nikoli, jak dlouho to bude trvat, od toho tu je teorie složitosti. Obecný program se může pro nějaký vstup i zacyklit, tudíž i ČRF nemusí být totální.
Téměř jako synonymum k "částečně rekurzivní"=ČR se používá "rekurzivně spočetné"=RS, každý z těchto dvou přívlastků se ovšem pro zmatení nepřítele (jak jinak než z řad studentstva) tradičně spojuje s jinými podstatnými jmény. O funkci se říká že je to ČRF, kdežto o predikátu, že je to RSP (rekurzivně spočetný predikát), a o množině, že je to RSM (rekurzivně spočetná množina).
Možná už znáte z Automatů a gramatik rekurzivně spočetné jazyky definované jako třídu jazyků přijímaných nějakým TS. Tedy jazyk L je RS, existuje-li TS, jenž se zastaví v koncovém přijímacím stavu právě na všech slovech daného jazyka. Pokud nějaké slovo v daném jazyce není, tak se buď TS zastaví v nekoncovém stavu nebo se zacyklí (tj. nikdy se nezastaví). Chceme-li zjistit, zda nějaké slovo patří do L, pak pustíme TS a čekáme, ale dokud se stroj nezastaví, tak nic nevíme.
TS přijímající L lze jednoduše upravit tak, aby se zastavil právě na slovech z L: pokud by se mohl zastavit v nepřijímacím stavu, tak přidáme instrukce, které výpočet zacyklí. Máme-li ČRF f, která je ekvivalentní s takto upraveným TS, tak platí, že <math>L = dom(f)</math>. Vysvětlení: každému slovu lze přiřadit jeho kód, tedy číslo; f bude funkce jedné proměnné; <math>dom(f)</math> je množina kódů slov jazyka L. Množina <math>dom(f)</math> je RSM.
Z částečně rekurzivních funkcí lze odvodit rekurzivně spočetné množiny a rekurzivně spočetné predikáty.
=== ORF = obecně rekurzivní funkce ===
ORFce jsou ty ČRFce, které jsou totální. Z ORFcí lze odvodit ORP a (obecně) rekurzivní množiny — u množin se slovo ''obecně'' vynechává.
=== PRF = primitivně rekurzivní funkce ===
Jak si později ukážeme, PRFce jsou vlastní podmnožinou ORFcí. Jsou to takové hezké funkce, které vždy konvergují. Lze pomocí nich vyjádřit většina známých operací jako např.: sčítání, násobení, negace, mocnění, test na prvočíselnost... Naopak se těžko hledá úkol, který by nezvládly (tím je např. [[Ackermannova funkce]]). Zatím naprosto neformálně můžeme říct, že PRF odpovídají programům, které mohou používat jen for-cykly (to jest <tt>for i := 1 to x do...</tt>, nikoli takové ty céčkovské, co simulují while-cyklus), ale nikoli while-cykly. Programy odpovídající ČRF mohou navíc používat právě onen while-cyklus (který ale může běžet do nekonečna a tak vznikne divergence).
=== Přehled ===
{| class="wikitable" border="1"
|+ Přehled zkratek
! !! funkce !! predikát !! množina
|-
|primitivně rekurzivní || PRF || PRP || nezavádí se
|-
|obecně rekurzivní || ORF || ORP || rekurzivní množina
|-
|částečně rekurzivní /<br> rekurzivně spočetný || ČRF || RSP || RSM
|}
== Efektivní vyčíslitelnost ==
Efektivní vyčíslitelnost se definuje jako to, co je vyčíslitelné (řešitelné) pomocí ČRF. Vzhledem k již zmíněné ekvivalenci TS a ČRF (kterou ale dokážeme až [[TIN064 ČRF=TS|později]]), jsou následující výrazy synonyma:
''efektivně vyčíslitelné = turingovsky vyčíslitelné = algoritmicky vyčíslitelné = algoritmicky řešitelné'' atd.
Když jsem poprvé slyšel o efektivní vyčíslitelnosti, tak jsem si vzpomněl na různé efektivní algoritmy s <math>n \log n</math> složitostí a podobně. Ne, ne, to je něco kapku jiného. Ve vyčíslitelnosti slovem ''efektivní'' myslíme, že to vůbec jde. (Jestli někomu přijde efektivní způsob, kterým pracuje univerzální TS, když pobíhá po pásce sem tam a přenáší čárky... no, já nevím.)
