{{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|{\phi }_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í; φ_x(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,x,s)\wedge \exists s^{\prime }:T_k(b,x,s^{\prime })$

• $\iff \exists w:(T_k(a,x,l(w))\wedge T_k(b,x,r(w)))$ (vyrobili jsme "ze souřadnic" s, s' číslo w - viz předchozí kapitolka)

• $\iff \exists w:T_{k+2}(e,a,b,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)

• $\iff \exists w:T_k(s_2(e,a,b),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,x,y,s)$ (x je jen k-1 prvků)

  • $\exists w\forall y\le t:T_k(a,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,x,t,s)\iff \exists s:T_k(s_1(e,a),x,t,s)$

• $\exists y\exists s:T_k(a,x,y,s)$

  • Nudný trik odminule: $\exists w:T_k(a,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 \iff 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. 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 $\phi$ k proměnných, pro kterou platí

$\phi (x_1,...,x_k)\downarrow \iff \exists yQ(x_1,...,x_k,y)$

$\phi (x_1,...,x_k)\downarrow \Rightarrow Q(x_1,...,x_k,\phi (x_1,...,x_k))$.

Druhá řádka říká, že pro každý RSP $Q$ umíme zkonstruovat takovou ČRF $\phi$, která lze dosadit za poslední proměnnou $Q$ (respektive její výsledek y) a pokud $\phi$ konverguje, tak $Q$ platí. První řádka říká, že $\phi$ "se snaží seč může", tedy pokud nějaké y existuje, tak ho najde. (Nebýt této podmínky, šlo by za $\phi$ 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. $\phi$ 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\iff T$ přijme vstup

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 14: x_1,...,x_k,y\̲m̲b̲o̲x̲{ za }j

Požadovaná ČRF je pak:

$\phi (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í) a procházíme tedy možnosti pro y a j pěkně postupně.

Důsledky

• Funkce $\phi$ je ČRF <=> má rekurzivně spočetný graf, kde graf $\phi$ je $\{(x,y)|\phi (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 $\phi$, pro kterou platí $dom(\phi )=rng(\phi )=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$