Státnice - Informatika - Vyčíslitelnost

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á 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

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á, 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

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} $)