Státnice - Informatika - Vyčíslitelnost
Obsah
Algoritmicky vyčíslitelné funkce, jejich vlastnosti
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:
- nula - o(x) = 0
- následník - s(x) = x+1
- projekce - I_n^j; 1<=j<=n (z n cisel vydelim j-té cislo)
Tři základní operátory (odvozovací pravidla):
- S_n^m - substituce (volani podprogramu) - vstup vice fci, vystup jedna funkce
- R_n - primitivni rekurze - odpovida forcyklu
- 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
Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti
- $ 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á a 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 \Phi_3(a,y,x,w) \simeq \Phi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w) $
Algoritmicky nerozhodnutelné problémy
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á, ze existuje pevny bod zobrazeni f. ($ \varphi $ je asi 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
- množina formulí dokazatelných v T není rekurzivní
- 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} $)