TIN064 Rekurzivní spočetnost

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

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í; φ_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, \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 $)

1. $ \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í
2. $ \neg(\Psi_k(e,x_1,...,x_k)\downarrow), \neg(\Psi_1(x,x)\downarrow) $ nejsou r.s.
3. $ \Psi_k $ nelze rozšířit do ORF

Důkaz

1. R.s. přímo z definice, kdyby byly rekurzivní, pak jejich negace je r.s., takže stačí ukázat 2)
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.
3. 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 $ \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í) 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 $