{{Template:TIN064 Skripta}}

## Základní definice ##

*množina $M \subseteq \mathbb{N}$ je **rekurzivní**, jestliže její charakteristická fce je ORF

**rekurzivní množina je taková, že o každém prvku dokážeme efektivně zjistit, zda do množiny patří či nikoliv
**Rekurzivní množina je právě efektivně (algoritmicky) rozhodnutelná

*množina $M \subseteq \mathbb{N}$ je **rekurzivně spočetná**, jestliže je definičním oborem nějaké ČRF
**rekurzivně spočetné množiny se nějaký program pouze zastaví, když prvek do množiny patří, jinak nic nevíme

**tzn. $M = \{m\ |\ \varphi_x(m)\downarrow\}$, kde $x$ označuje číslo ČRF jejímž je M definičním oborem, někdy se v této souvislosti říká $x$-tá rekurzivně spočetná množina, značí se $W_x$.
**jistý náhled dává anglické pojmenování "recursively enumerable" - rekurzivně spočetné množiny jsou takové, kde máme k dispozici program, který postupně generuje prvky do množiny patřící; φ<sub>x</sub>(m) pak čeká, jestli program vyrobí i m; pokud ne, čeká stále dál a neví, jestli už už přijde, nebo bude čekat pořád...

*dle stejných pravidel pojmenováváme i relace ("predikáty") $R \subseteq \mathbb{N}^k$, množiny výše odpovídají unárním relacím.

## Některé z vlastností ##

**Věta:** Konjunkce a disjunkce (průnik a sjednocení) zachovávají rekurzivní spočetnost (pro množiny i pro predikáty)

**Důkaz:** Tvrzení je "od oka" vidět - co by se tak mohlo rozbít? Formálně na to můžeme jít přes s-m-n větu:

* $\exists s: T_k(a, \vec x, s) \land \exists s': T_k(b, \vec x, s')$
* $\Leftrightarrow \exists w: (T_k(a, \vec x, l(w)) \land T_k(b, \vec x, r(w)))$ (vyrobili jsme "ze souřadnic" s, s' číslo w - viz předchozí kapitolka)
* $\Leftrightarrow \exists w: T_{k+2}(e, a, b, \vec x, w)$ (e je snadno vyrobitelná ČRF, která spustí paralelně a, b se správnými parametry - a ještě dobře zasubstituujeme l a r)
* $\Leftrightarrow \exists w: T_k(s_2(e, a, b), \vec x, w)$
* s-m-n věta nám vyrobila hledaný kód konjunkce - $c=s_2(e, a, b)$!
* Disjunkce pravděpodobně jen mírným zesložitěním kódu e.

**Pozn.:** Negace resp. doplněk samozřejmě RS nezachovává.

**Věta:** Omezená obecná kvantifikace $(\forall y \le t: Q)$ a existenční kvantifikace $(\exists y: Q)$ zachovávají rekurzivní spočetnost

**Důkaz:** Opět to vypadá zřejmě. Formálně:

* $\forall (y \le t) \exists s: T_k(a, \vec x, y, s)$ (x je jen k-1 prvků)
    * $\exists w \forall y \le t: T_k(a, \vec x, y, w_y)$ kde $w$ je $t+1$-tice prvků - pro každou hodnotu y jeden
    * y můžeme zkoušet primitivní rekurzí, w minimalizací, tzn. vyrobíme nový RS program e
    * $\exists s: T_{k+1}(e, a, \vec x, t, s) \Leftrightarrow \exists s: T_k(s_1(e,a), \vec x, t, s)$
* $\exists y \exists s: T_k(a, \vec x, y, s)$
    * Nudný trik odminule: $\exists w: T_k(a, \vec x, l(w), r(w))$, zbytek jako obvykle.

**Pozn.:** Neomezená obecná kvantifikace je strašná věc, která nezachovává vůbec nic.

**Věta (Postova):** Množina M je rekurzivní <=> $M$ a její doplněk $\bar M$ jsou rekurzivně spočetné. Predikát P je ORP <=> P a jeho doplněk P' jsou RSP.

**Důkaz:** Pro množiny dvě implikace. Predikát se dokáže snadno, ale až po přečtení věty o selektoru o trochu níže.

* M rekurzivní. Pak M je jistě RS, a její doplněk je také dokonce rekurzivní (triv. - v konečném čase jsme se dozvěděli, že prvek do M patří nebo ne, to jen znegujeme - kdyby M byla RS, je situace tíživější). 
* M a $\bar M$ jsou RS. Jednoduše spustíme hledání paralelně v obou a v konečném čase se alespoň jedno hledání zastaví.

### Věta (Rekurzivní spočetnost $\Psi$) ###

#$\Psi_k(e,x_1,...,x_k)\downarrow, \Psi_k(x_1,x_1,x_2,...,x_k)\downarrow$ jsou rekurzivně spočetné predikáty, ale nejsou rekurzivní

#$\neg(\Psi_k(e,x_1,...,x_k)\downarrow), \neg(\Psi_1(x,x)\downarrow)$ nejsou r.s.
#$\Psi_k$ nelze rozšířit do ORF

#### Důkaz ####

#R.s. přímo z definice, kdyby byly rekurzivní, pak jejich negace je r.s., takže stačí ukázat 2)
#Stačí ukázat pro $\Psi_1(x,x)$. Pro spor nechť $\Psi_1(x,x)\uparrow$ je r.s. Pak existuje ČRF $g$ taková, že $\Psi_1(x,x)\uparrow \Leftrightarrow g(x)\downarrow$ ale $g$ má nějaký kód $x_0$, po dosazení $x = x_0$ dostáváme klasický spor.

#Měli jste si rozmyslet za domácí úkol z minulé stránky! Je to jednoduše varianta [důkazu neexistence univerzální PRF](TIN064_ČRF%2C%20ORF%2C%20PRF#Univerzální_PRF_a_ORF). A jak tedy zachránit ČRF od stejného osudu? $g(x)=f(x,x)+1$ nesmí pro kód g konvergovat - dokonce takto lze pro libovolnou ČRF $\beta \supset \Psi_1$ efektivně nalézt $x_0 : \beta(x_0,x_0)\uparrow$.

### Věta o selektoru ###

Pro každý RSP $Q$ k+1 proměnných existuje ČRF $\varphi$ k proměnných, pro kterou platí

$\varphi(x_1,...,x_k)\downarrow \Leftrightarrow \exists y Q(x_1,...,x_k,y)$

$\varphi(x_1,...,x_k)\downarrow \Rightarrow Q\Big(x_1,...,x_k,\varphi(x_1,...,x_k)\Big)$.

Druhá řádka říká, že pro každý RSP $Q$ umíme zkonstruovat takovou ČRF $\varphi$, která lze dosadit za poslední proměnnou $Q$ (respektive její výsledek y) a pokud $\varphi$ konverguje, tak $Q$ platí. První řádka říká, že $\varphi$ "se snaží seč může", tedy pokud nějaké y existuje, tak ho najde. (Nebýt této podmínky, šlo by za $\varphi$ zvolit třeba prázdnou funkci.)

#### Graf rekurzivní funkce ####

Predikát $Q$ k+1 proměnných si můžeme představit jako relaci či graf (grafem se zde rozumí množina bodů čili *diagram průběhu*, žádné kombinatorické hrany a vrcholy) v k+1 rozměrném prostoru (přirozených čísel ovšem, jak jinak). Predikát $Q(x_1,...,x_k,x_{k+1})\!$ určuje, zda bod $(x_1,...,x_k,x_{k+1})$ je v grafu, či nikoli. $\varphi$ můžeme chápat jako funkci na k rozměrném prostoru takovou, že v grafu *vybere* v poslední proměnné právě jeden bod (pokud existuje).

Proto se jmenujeme *věta (či lemma) o selektoru* a říká se, že ČRF mají RS graf. Nemusí být moc jasné, proč jsme se tímhle směrem vůbec pustili. Zdá se, že tyto úvahy vedou k alternativní interpretaci efektivní vyčíslitelnosti, aritmetickým hierarchiím a dalším děsivě znějícím věcem. Každopádně v rámci Vyčíslitelnosti I se ke grafům již nevrátíme, takže na tohle můžete prozatím opět zapomenout.

#### Důkaz ####

Pro RSP $Q$ existuje TS $T$, který se zastaví v přijímacím stavu, pokud $Q(x_1,...,x_k,y)$.

Definujme ORF

$\beta(x_1,...,x_k,y,j) = 0 \Leftrightarrow T$ přijme vstup $x_1,...,x_k,y\mbox{ za }j$ kroků

Požadovaná ČRF je pak:

$\varphi(x_1,...,x_k) = \mu_{<y,j>}\beta(x_1,...,x_k,y,j)$

Pokud totiž pro $x_1,...,x_k$ existuje nějaké $y$ takové, že platí $Q(x_1,...,x_k,y)$, tak se odpovídající TS zastaví nejvýše po $j$ krocích, a my to zjistíme v $<y,j>$-té iteraci minimalizační funkce $\mu_{<y,j>}$.

**Poznámka:** Může to být zřejmé, ale stejně je dobré si uvědomit, že dvojici <y,j> máme zakódovánu jako přirozené číslo (např. pomocí [Cantorova diagonálního uspořádání](http://wiki.matfyz.cz/index.php?title=TIN064_Prerekvizity#Cantorovo_diagon.C3.A1ln.C3.AD_uspo.C5.99.C3.A1d.C3.A1n.C3.AD)) a procházíme tedy možnosti pro *y* a *j* pěkně postupně.

#### Důsledky ####

* Funkce $\varphi$ je ČRF <=> má rekurzivně spočetný graf, kde graf $\varphi$ je $\{(x,y)\ |\ \varphi(x) \downarrow = y\}$.
    * **Důkaz:** Z predikátu grafu si selektorem vytáhneme ČRF funkci. Dopředná implikace ještě triviálněji z definice.

* Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.
    * **Důkaz:** Máme rekurzivně spočetnou množinu $W$. Vytvoříme množinu dvojic prvků (graf) $\{(a,a)\ |\ a \in W\}$, která je též rekurzivně spočetná. Selektor na ní je hledaná ČRF $\varphi$, pro kterou platí $dom(\varphi) = rng(\varphi) = W$.

* Každý obor hodnot ČRF je rekurzivně spočetná množina.
    * Tedy $\forall f\ \exists g: rng(f) = dom(g)$.
    * **Důkaz:** Buď minimalizací a univerzální funkcí, nebo vytáhneme selektor z $Q(y,x): f(x) \downarrow= y$