{{Template:TIN064 Skripta}}

Základní definice

*množina M⊆NM \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⊆NM \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 ∣ φx(m)↓}M = \{m\ |\ \varphi_x(m)\downarrow\}, kde xx označuje číslo ČRF jejímž je M definičním oborem, někdy se v této souvislosti říká xx-tá rekurzivně spočetná množina, značí se WxW_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⊆NkR \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:

  • ∃s:Tk(a,x⃗,s)∧∃s′:Tk(b,x⃗,s′)\exists s: T_k(a, \vec x, s) \land \exists s': T_k(b, \vec x, s')

  • ⇔∃w:(Tk(a,x⃗,l(w))∧Tk(b,x⃗,r(w)))\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)

  • ⇔∃w:Tk+2(e,a,b,x⃗,w)\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)

  • ⇔∃w:Tk(s2(e,a,b),x⃗,w)\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=s2(e,a,b)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 (∀y≤t:Q)(\forall y \le t: Q) a existenční kvantifikace (∃y:Q)(\exists y: Q) zachovávají rekurzivní spočetnost

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

  • ∀(y≤t)∃s:Tk(a,x⃗,y,s)\forall (y \le t) \exists s: T_k(a, \vec x, y, s) (x je jen k-1 prvků)

    • ∃w∀y≤t:Tk(a,x⃗,y,wy)\exists w \forall y \le t: T_k(a, \vec x, y, w_y) kde ww je t+1t+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

    • ∃s:Tk+1(e,a,x⃗,t,s)⇔∃s:Tk(s1(e,a),x⃗,t,s)\exists s: T_{k+1}(e, a, \vec x, t, s) \Leftrightarrow \exists s: T_k(s_1(e,a), \vec x, t, s)

  • ∃y∃s:Tk(a,x⃗,y,s)\exists y \exists s: T_k(a, \vec x, y, s)

    • Nudný trik odminule: ∃w:Tk(a,x⃗,l(w),r(w))\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í <=> MM a její doplněk Mˉ\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 Mˉ\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)

#Ψk(e,x1,...,xk)↓,Ψk(x1,x1,x2,...,xk)↓\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í

#¬(Ψk(e,x1,...,xk)↓),¬(Ψ1(x,x)↓)\neg(\Psi_k(e,x_1,...,x_k)\downarrow), \neg(\Psi_1(x,x)\downarrow) nejsou r.s. #Ψk\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 Ψ1(x,x)\Psi_1(x,x). Pro spor nechť Ψ1(x,x)↑\Psi_1(x,x)\uparrow je r.s. Pak existuje ČRF gg taková, že Ψ1(x,x)↑⇔g(x)↓\Psi_1(x,x)\uparrow \Leftrightarrow g(x)\downarrow ale gg má nějaký kód x0x_0, po dosazení x=x0x = 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)+1g(x)=f(x,x)+1 nesmí pro kód g konvergovat - dokonce takto lze pro libovolnou ČRF β⊃Ψ1\beta \supset \Psi_1 efektivně nalézt x0:β(x0,x0)↑x_0 : \beta(x_0,x_0)\uparrow.

Věta o selektoru

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

φ(x1,...,xk)↓⇔∃yQ(x1,...,xk,y)\varphi(x_1,...,x_k)\downarrow \Leftrightarrow \exists y Q(x_1,...,x_k,y)

φ(x1,...,xk)↓⇒Q(x1,...,xk,φ(x1,...,xk))\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 QQ umíme zkonstruovat takovou ČRF φ\varphi, která lze dosadit za poslední proměnnou QQ (respektive její výsledek y) a pokud φ\varphi konverguje, tak QQ 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 QQ 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(x1,...,xk,xk+1) ⁣Q(x_1,...,x_k,x_{k+1})\! určuje, zda bod (x1,...,xk,xk+1)(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 QQ existuje TS TT, který se zastaví v přijímacím stavu, pokud Q(x1,...,xk,y)Q(x_1,...,x_k,y).

Definujme ORF

β(x1,...,xk,y,j)=0⇔T\beta(x_1,...,x_k,y,j) = 0 \Leftrightarrow 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

kroků

Požadovaná ČRF je pak:

φ(x1,...,xk)=μ<y,j>β(x1,...,xk,y,j)\varphi(x_1,...,x_k) = \mu_{<y,j>}\beta(x_1,...,x_k,y,j)

Pokud totiž pro x1,...,xkx_1,...,x_k existuje nějaké yy takové, že platí Q(x1,...,xk,y)Q(x_1,...,x_k,y), tak se odpovídající TS zastaví nejvýše po jj krocích, a my to zjistíme v <y,j><y,j>-té iteraci minimalizační funkce μ<y,j>\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 φ\varphi je ČRF <=> má rekurzivně spočetný graf, kde graf φ\varphi je {(x,y) ∣ φ(x)↓=y}\{(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 WW. Vytvoříme množinu dvojic prvků (graf) {(a,a) ∣ a∈W}\{(a,a)\ |\ a \in W\}, která je též rekurzivně spočetná. Selektor na ní je hledaná ČRF φ\varphi, pro kterou platí dom(φ)=rng(φ)=Wdom(\varphi) = rng(\varphi) = W.

  • Každý obor hodnot ČRF je rekurzivně spočetná množina.

    • Tedy ∀f ∃g:rng(f)=dom(g)\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)↓=yQ(y,x): f(x) \downarrow= y