Státnice - Informatika - Vyčíslitelnost

Z ωικι.matfyz.cz
Verze z 28. 5. 2008, 02:50, kterou vytvořil Che (diskuse | příspěvky) (Věta o rekurzi: čeština)

Přejít na: navigace, hledání

Algoritmicky vyčíslitelné funkce, jejich vlastnosti

see wen:Computable function

Postova věta (wen:Post's theorem, WTF?), a uzavřenost PRF, ORF a ČRF na doplněk (ČRF ne), sjednocení, průnik, omezená kvantifikace, kvantifikace

Částečně rekurzivní funkce

Tři základní funkce:

  1. nula - o(x) = 0
  2. následník - s(x) = x+1
  3. projekce - I_n^j; 1<=j<=n (z n cisel vydelim j-té cislo)

Tři základní operátory (odvozovací pravidla):

  1. S_n^m - substituce (volani podprogramu) - vstup vice fci, vystup jedna funkce
  2. R_n - primitivni rekurze - odpovida forcyklu
  3. M_n - minimalizace - odpovida while cyklu
Def Odvozeni funkce
posloupnost funkcí f0 .. fn = f, kde kazda funkce je bud základní funkce nebo vznikne použitím operátoru na predchozi funkce
Def Totální funkce
funkce je totální, pokud funkce (program) skončí na každem vstupu
Def Částečne rekurzivní funkce
funkce je částečně rekurzivní (ČRF), pokud ma odvození, obecně rekurzivní (ORF), pokud je ČRF a je totální, primitivně rekurzivní (PRF), pokud ma odvození pouze s použitím operatorů S_n^m a R_n (bez while)

$ PRF \subset ORF \subset CRF $

  • ORF, ale není PRF - ackermanova funkce (potřebuje while)
  • ČRF, ale není ORF - nedefinovaná funkce

Ekvivalence různých matematických definic

  • TS (Turing)
  • ČRF (Kleene)
  • Postovy systémy (wen:Tag system)
  • lambda funkce

Primitivně a částečně rekurzivní funkce

see wen:Primitive recursive function, wen:μ-recursive function

Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti

see wen:Recursive set, wen:Recursively enumerable set
  • $ W_x \mbox{ (x-tá rekurzivně spočetná množina) } = dom(\varphi_x) = \{ y:\varphi_x(y) \} \downarrow $
  • $ K = \{ x:x \in W_x \} = \{x:\varphi_x(x) \downarrow \} = \{ x:\Psi_1(x,x) \downarrow \} $
    $ K $ je množina funkcí, co konvergují na svém indexu.

Množina $ K $ je rekurzivně spočetná, není rekurzivní, $ \overline K $ není rekurzivně spočetná.

Kdyby $ \overline K $ byla rekurzivně spočetná, měla by index $ x_0 $ ($ \overline K = W_{x_0} $), což vede ke sporu: $ x_0 \notin W_{x_0} \Leftrightarrow^* x_0 \in \overline K \Leftrightarrow^{**} x_0 \in W_{x_0} $
* - z definice $ \overline K $
** - předpoklad pro spor $ \overline K $ má index ($ \overline K = W_{x_0} $)

1-převeditelnost, m-převeditelnost

  • Množina $ A $ je 1-převeditelná na $ B $ (značíme $ A \leq_1 B $), jestliže existuje prostá ORF taková, že $ x \in A \Leftrightarrow f(x) \in B $.
    • Množina M je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná funkce je na ni 1-převeditelná.
  • Množina $ A $ je m-převeditelná na $ B $ (značíme $ A \leq_m B $), jestliže existuje (ne nutně prostá) ORF taková, že $ x \in A \Leftrightarrow f(x) \in B $.
    • Množina M je m-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina na ni je m-převeditelná.

1-úplnost K

K je 1-úplná.

Mějme libovolnou rekurzivně spočetnou množinu $ W_x $ a ČRF $ \alpha(y,x,w) $, která ji popisuje.
Tedy $ \alpha(y,x,w)\downarrow \Leftrightarrow^* y \in W_x \Leftrightarrow \Psi_1(x,y)\downarrow \Leftrightarrow \varphi_x(y)\downarrow $ (na $ w $ hodnota $ \alpha $ nezávisí)
Ze s-m-n dostáváme $ \alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w) $ (**)
Označíme-li $ h(y,x) = s_2(a,y,x) $ ($ s_2 $ je ČRF a tedy i ORF), máme $ y \in W_x \Leftrightarrow^* \alpha(y,x,w)\downarrow \Leftrightarrow^{**} \varphi_{h(y,x)}(w)\downarrow \Leftrightarrow^{***} \varphi_{h(y,x)}(h(y,x))\downarrow \Leftrightarrow h(y,x) \in K $
  • *** -- můžeme předpokládat $ h(y,x) = w $, hodnota $ \alpha $ a tudíž ani $ h $ n $ w $ nezáleží.
Tedy $ W_x \leq_1 K $ pomocí funkce $ \lambda y.h(y,x) $.

$ K_0 = \{ \langle y,x \rangle : y \in W_x \} $ je 1-úplná.

$ K \leq_1 K_0 $ a $ K $ je 1-úplná.

Další vztahy

  1. Relace $ \leq_1 $ a $ \leq_m $ jsou tranzitivní a reflexivní.
  2. $ A \leq_1 B \Rightarrow A \leq_m B $
  3. $ B \mbox{ rekurzivní}, A \leq_m B \Rightarrow A \mbox{ rekurzivní} $
    • Složením funkce dokazující $ \leq_m $ s procedurou, která rozhoduje o $ x \in B $ dostaneme proceduru rozhodující o $ A $. ($ c_A(x) = c_B(f(x)) $
  4. $ B \mbox{ rekurzivně spočetná}, A \leq_m B \Rightarrow A \mbox{ rekurzivně spočetná} $
    Důsledek: $ K $ a $ \overline K $ jsou m-nesrovnatelné.

Rekurzivní permutace

  • Rekurzivní permutace je permutace na $ \mathbb{N} $, která je ORF.
  • Množiny $ A $ a $ B $ jsou rekurzivně izomorfní, jestliže existuje rekurzivní permutace p taková, že $ p(A) = B $. Značíme $ A \equiv B $.
  • $ A \equiv_1 B $, jestliže $ A \leq_1 B \And B \leq_1 A $
  • $ A \equiv_m B $, jestliže $ A \leq_m B \And B \leq_m A $

Myhillova věta

$ A \equiv B \Leftrightarrow A \equiv_1 B $

Důkaz je ve Strojilovi na straně 5, zprava doleva spočívá v postupném generování grafu $ h $ tak, aby v kroku $ n $ platilo $ \{0, ..., n\} \subseteq dom(h) $ a $ \{0,...,n\} \subseteq rng(h) $.

Rekurzivně spočetné predikáty

  • Je-li $ Q $ ORF, pak $ \exists y Q $ je rekurzivně spočetný predikát.
    $ \mu_y Q $ je ČRF, její definiční obor je $ \exists y Q $.
  • Predikát $ \exists y T_k(e,x_1,... ,x_k,y) $ je univerzální RSP pro třídu RSP $ k $ proměnných.
    $ T_k $ je predikát z Kleeneho věty o normální formě, co říká že funkce $ e $ má při $ y_0 $ krocích od konce mezivýsledek $ y_1 $. ($ y=\langle y_0, y_1 \rangle $) Důkaz tvrzení je taky z Kleeneho věty.
  • Konjunkce a disjunkce zachovávají rekurzivní spočetnost. (Průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.)
    Pro průnik spustíme oba programy současně a čekáme až se jeden zastaví.
  • Omezená kvantifikace $ (\forall y)_{y \leq t} $ a existenční kvantifikace (pro $ k \geq 2 $) zachovávají rekurzivní spočetnost.
    Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem, existenční kvantifikátor je rozveden ve Strojilovi na straně 6.

Postova věta

Množina $ M $ je rekurzivní právě když $ M $ i $ \overline M $ jsou rekurzivně spočetné. Predikát $ Q $ je ORP právě když $ Q $ i $ \neg Q $ jsou RSP.

Důkaz: Zleva doprava triviální, zprava doleva intuitivně: $ M = dom(P_1), \overline M = dom(P_2) $. Pustíme oba programy současně a čekáme, který se zastaví.

Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.

Důkaz: Vytvoříme množinu dvojic $ R = \{ \langle z,y \rangle : z \in W_x \And y = z \} $. Množina R je rekurzivně spočetná, tedy má ČRF selektor $ \varphi $, platí $ dom(\varphi) = rng(\varphi) = W_x $. Myšlenka důkazu je, že body, kde $ \varphi_x $ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude současně oborem hodnot.

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

Důkaz: Zkonstruujeme pseudoinverzní funkci $ h $ k ČRF $ \varphi $.

Algoritmicky nerozhodnutelné problémy

see wen:List of undecidable problems

Halting problém, přičinlivý bobr a tak.

Věty o rekurzi a jejich aplikace

  • Ladova skripta str.11, o pevnem bode,
  • pouziti v logice, godelovy vety?
  • paradox lhare
  • riceova veeta je aplikaci v. o rekurzi
  • veta o rekurzi (o \E pevneho bodu) s dukazem
  • Veto o \Inf pevnych bodu

Věta o rekurzi

Jestliže $ f $ je ČRF jedné proměnné, potom existuje $ a $ takové, ze $ \varphi_{f(a)}(x) \simeq \varphi_a (x) $ pro každé $ x $.

Říká, že existuje pevný bod zobrazení $ f $. ($ \varphi $ je zřejmě univerzální funkce jedné proměnné)

Důkaz:

$ \varphi_{f(s_1(z,z))}(x) \simeq \Psi_2(e,z,x) \simeq^{smn} \Psi_1(s_1(e,z), x) \simeq \varphi_{s_1(e,z)}(x) $
  • $ s_1(z,z) $ je funkce se s-m-n věty, která dělá totéž co z, ale má první parametr fixovaný na hodnotu z
  • e je index programu, který počítá výraz vlevo (tj. $ s_1(z,z) $, pak $ f(s_1(z,z)) $, a vzniklou funkci aplikuje na x)
Pak položíme $ z=e $ a $ a=s_1(e,e) $ a máme to.

Riceova věta

Jestliže $ \mathcal{A} $ je třída ČRF (jedné proměnné), ktera je netriviální, potom $ A_{\mathcal{A}} = \{ x : \varphi_x \in \mathcal{A} \} $ je nerekurzivní.

Dokazuje se sporem. Nechť $ A $ je rekurzivní. Potom lze vytvořit ORF $ f $ takovou, že všechny prvky z $ A $ zobrazí na nějaký prvek $ b \notin A $ a všechny prvky mimo a zobrazí na nějaký prvek $ a \in A $. Podle věty o rekurzi existuje nějaký pevný bod $ f $ $ u_0 $, že platí $ \varphi_{u_0} = \varphi_{f(u_0)} $.
Tedy $ u_0 \in A \Rightarrow f(u_0) = b \notin A $ a $ u_0 \notin A \Rightarrow f(u_0) = a \in A $. Což je ovšem spor, protože $ u_0 $ a $ f(u_0) $ jsou indexy stejné funkce, takže obě čísla buď v $ A $ leží nebo neleží.

Nejedná se o třídu programů, ale funkcí. Tedy i pro jednoprvkovou $ \mathcal{A} $ bude $ A_{\mathcal{A}} $ nekonečná a nerekurzivní. (Každá funkce je vyčíslována nekonečně mnoha programy a rozhodnout o jejich ekvivalenci efektivně nelze.)

Věta o generování pevných bodů

Pro každou částečně rekurzivní funkci $ f $ existuje prostá rostoucí PRF $ g $ taková, že platí $ \varphi_{f(g(j))}(x) \simeq \varphi_{g(j)}(x) $.

Tedy $ g $ rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce $ f $.

Důkaz:

$ \varphi_{f(s_2(z,z,j))}(x) \simeq \Psi_3(e,z,j,x) \simeq \Psi_1(s_2(e,z,j), x) \simeq \varphi_{s_2(e,z,j)}(x) $
  • $ e $ podobně jako u věty o rekurzi schválně počítá levou stranu
Zvolíme $ g(j) = s_2(e,e,j) $.

Gödelovy věty

rekurzivní neoddělitelnost
Dvojice množin A, B ($ A \cap B = \emptyset $) je rekurzivně neoddělitelná, jestliže neexistuje rekurzivní množina M taková, že $ A \subseteq M, M \cap B = \emptyset $ (tj. $ B \subseteq \overline{M} $)
efektivní neoddělitelnost
Dvojice množin A, B ($ A \cap B = \emptyset $) je efektivně neoddělitelná, jestliže existuje ČRF $ \varphi $ taková, že
$ \begin{matrix} A \subseteq W_x \\ B \subseteq W_y \\ W_x \cap W_y = \emptyset \end{matrix} \Bigg \} \Rightarrow \varphi(x,y)\downarrow \and \varphi(x,y)\notin W_x \cup W_y $
Tj. z indexů aproximace A a B se dá efektivně najít další box, který leží mimo tu aproximaci.
Gödelova věta o neúplnosti (1. část)
V rozumných teoriích je množina dokazatelných a vyvratitelných formulí efektivně neoddělitelná dvojice.

Gödelova věta o neúplnosti

Základní aritmerická síla: Jazyk prvního řádu

  • numerály pro nulu a jedničku
  • funkční symboly + a ×
  • konečně mnoho axiomů

Teorie T je axiomatizovatelná, jestliže množina dokazatelných formulí v T je rekurzivně spočetná.

Věta: Jestliže teorie T 1. řádu má základní aritmetickou sílu a je bezesporná, pak

  1. množina formulí dokazatelných v T není rekurzivní
  2. je-li T navíc axiomatizovatelná, pak
    • existuje uzavřená formule v F taková, že F je nerozhodnutelná v T (tj. z T nevyplývá ani F, ani $ \neg F $)
    • v T nelze dokázat vlastní bezespornost (za o něco silnějších předpokladů o teorii T -- např. $ \Sigma_1-\mbox{indukce} $)