{{TIN064 Skripta}}
Skutečný úvod k těmto wiki-skriptům je [zde](TIN064%20wiki-skripta), 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 [Johančiny pohádky první](http://web.archive.org/web/20100626015101/http://atrey.karlin.mff.cuni.cz/%7Ejohanka/vyuka/pohadky_vycislitelnost.html).

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 ##

### $0 \in \mathbb{N}$. Čí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 $\mathbb{N}=\{0,1,2,...\}$. Je to jednodušší, než vždy psát $\mathbb{N} \cup \{0\}$. 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 $f: \mathbb{N}^k \to \mathbb{N}$. 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 $f: A \to B$ obvykle myslí, že definiční obor $f$ je $A$ (zapisujeme $dom(f)=A$). Ve vyčíslitelnosti, ale platí $dom(f) \subseteq A$.

Ještě jinými slovy: pro některé k-tice nemusí být hodnota $f$ definována a tyto k-tice pak nepatří do definičního oboru $f$.

### Funkce lze chápat jako programy a naopak ###

Funkci $f: \mathbb{N}^k \to \mathbb{N}$ si můžeme představit jako program, který na vstupu dostane $k$ čísel a vrátí jedno číslo. Tedy schematicky:

 program_pro_f(x<sub>1</sub>,...,x<sub>k</sub>){
   ...

   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 $\mathbb{N}^k \to \mathbb{N}$.

#### 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í (`if (x == 42) while (true) do {}`). 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 $dom(f)=\emptyset$. 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 $f(x_1,...,x_n)\uparrow$. 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 $f(x_1,...,x_n)\downarrow$. Například pro funkci $f$ jedné proměnné tedy máme $dom(f)=\{x|f(x)\downarrow\}$.

#### Co znamená $\downarrow=$? ####

Zápis $f(x)\downarrow=y$ je zkratkou za $f(x)\!\downarrow \; \And \; f(x)=y$, tedy $f(x)$ konverguje a rovná se $y$. Exaktně vzato by stačilo psát $f(x)=y$, protože z toho už vyplývá, že funkce konverguje. Zápis $f(x)\downarrow=y$ se ale používá v situacích, kdy nás chce jeho autor upozornit, že to není tak samozřejmé, že $f(x)$ konverguje. Případně to může znamenat, že se v důkazu nejprve musí dokázat ta konvergence a až poté výsledná hodnota.

## Funkce, predikát, množina, relace, problém ##

Je dobré si uvědomit, že tyto pojmy jsou na sebe jednoduše převeditelné, jde jen o úhel pohledu. V důkazech se obvykle tyto převody ani nezmiňují.

### Predikát jako funkce ###

Predikát k proměnných $P(x_1,...,x_k)$ je nějaké tvrzení o těchto proměnných, které může být pravdivé či nepravdivé. Např. $P(x_1,x_2)$="($x_1$ je prvočíslo) a ($x_2 > x_1)$". 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 $rng(f)=\{0,1\}$).

### Množina jako predikát ###

Množinu lze chápat jako soubor prvků, které mají nějakou vlastnost P, tedy množina $M = \{x | P(x) \mbox{ platí}\}$. 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 $C_M: \mathbb{N} \to \{0,1\}$ a 

$C_M(x) = 
\begin{cases} 

  1 & \mbox{pro }x \in    M \\
  0 & \mbox{pro }x \notin M

\end{cases}$.

Všimněme si, že charakteristická funkce je z definice totální.

### Relace jako predikát ###

Relace na množinách $A_1,..., A_n$ je podmnožina jejich kartézského součinu. Ve vyčíslitelnosti jako množiny $A_i$ bereme (kupodivu opět:-)) podmnožiny $\mathbb{N}$. Relace na n množinách je v důsledku totéž co 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.)

### Problém jako množina ###

V teorii složitosti se *instance problému* definuje jako slovo nad abecedou {0,1} (tedy pro nás číslo) a *problém Q* je pak definován jako úloha rozhodnout, zda daná instance problému patří do jazyka $L(Q)_Y$, tedy do množiny kladných instancí.
Zjednodušeně řečeno: problémy jsou zase jen množiny.

* Problém je **rozhodnutelný** (též se říká **vyčíslitelný** či **rekurzivní**), jestliže existuje TS, který se zastaví na libovolném vstupu a skončí v přijímacím stavu právě pro ty vstupy, které jsou řešením daného problému. O množině kladných instancí pak říkáme, že je to **rekurzivní množina**, případně že je efektivně rozhodnutelná (o každém prvku můžeme efektivně zjistit, zda do ní patří, nebo nepatří).

* Problém je  **částečně rozhodnutelný** (též se říká **vyčíslitelně spočetný** či **rekurzivně spočetný**), jestliže existuje TS, který se zastaví (v přijímacím stavu) na vstupech, pro které je odpověď ANO (na vstupech, pro které je odpověď NE, se zastavit nemusí). O množině kladných instancí pak říkáme, že je to **rekurzivně spočetná množina** - existuje pro ni program, který se na vstupu *x* zastaví, pokud prvek *x* patří do té množiny. Dokud se nezastaví, nevíme nic. *Příklad ze života: když se hraje hokej, prodloužení, je to nerozhodně, vy to nesledujete a jen slyšíte případný řev zvenku, tak pokud se tento řev ozve, víte, že jsme vyhráli, ale pokud je ticho, nevíte nic. Takže hokejový řev je rekurzivně spočetný.*

* Problém je **nerozhodnutelný**, jestliže není rozhodnutelný. Existují nerozhodnutelné problémy, které jsou částečně rozhodnutelné ([Halting problem](TIN064_Prerekvizity#Halting%20problem)), ale existují také problémy, které nejsou ani částečně rozhodnutelné.

## Č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](Automaty%20a%20gramatiky)).

### Č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 $L = dom(f)$. Vysvětlení: každému slovu lze přiřadit jeho kód, tedy číslo; $f$ bude funkce jedné proměnné; $dom(f)$ je množina kódů slov jazyka L. Množina $dom(f)$ 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 ###

ORF jsou ty ČRF, které jsou totální. Z ORF lze odvodit ORP=Obecně rekurzivní predikáty 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](Ackermannova%20funkce)). Zatím naprosto neformálně můžeme říct, že PRF odpovídají programům, které mohou používat jen for-cykly (to jest `for i := 1 to x do...`, 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 zkratek a terminologie ###

|                      !! funkce !! predikát !! množina             !! problém|
|----|
|částečně rekurzivní /|||||
||||||
||||||

## 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%20ČRF%2C%20ORF%2C%20PRF#Výpočetní%20síla%20TS%20a%20ČRF%20je%20ekvivalentní>), 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 $n\,\log n$ 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.) Zdrojem tohoto nedorozumění je překlad dvou různých anglických přídavných jmen, *efficient* a *effective*, pomocí jednoho českého *efektivní*.