Státnice - Informatika - Vyčíslitelnost

Z ωικι.matfyz.cz
Verze z 13. 2. 2009, 10:50, kterou vytvořil 195.113.20.96 (diskuse) (Produktivní a kreativní množiny)

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

Tento souhrn slouží pro přípravu k magisterským státnicím. Stránku o předmětu vyčíslitelnost najdete pod heslem Vyčíslitelnost I.

Poznámky k rozsahu látky

Státnicové otázky z vyčíslitelnosti jsou poměrně obecné a rozsáhlé. Dle Kučery by mělo platit, že přibližně pokrývají látku předmětu Vyčíslitelnost I [1]. Kromě toho Kučera soukromě mailem potvrdil, že není třeba znát pojmy imunní množina, simple množina a úplně produktivní množina ani tvrzení s nimi související.

Algoritmicky vyčíslitelné funkce, jejich vlastnosti

see wen:Computable function

Aritmetická funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je (turingovsky) vyčíslitelná pokud existuje Turingův stroj, který ji vyčísluje (jedna z mnoha ekvivalentních definic).

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

Ekvivalence různých matematických definic

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

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

Čá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) nebo univerzalni pro PRF (sporem)
  • ČRF, ale není ORF - nedefinovaná funkce, g(x,y)=y+1 tj. M_1(S_2^1(s,I_2^2))

Ackermanova funkce

  • A(0, y) =
    • 1 pro y = 0
    • 2 pro y = 1
    • y + 2 pro y ≥ 2
  • A(x, 0) = 0
  • A(x + 1, y + 1) = A(x, A(x + 1, y))

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

see wen:Recursive set, wen:Recursively enumerable set

Množina je (obecně) rekurzivní, pokud její charakteristická funkce je ORF.

Množina je rekurzivně spočetná (CE, computably enumerable), pokud je definičním oborem nějaké ČRF.

  • (analogicky pro predikáty, u nich se používá i pojem primitivně rekurzivní, pokud je jeho charakteristická funkce PRF)

$ 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 (indexů) funkcí, co konvergují na tom svém indexu.

Věta: 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á množina 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 PRF 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 $ na $ 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 $.

Produktivní a kreativní množiny

  • Definice
  • Definice: Množina A je produktivní, pokud existuje ČRF φ tž. $ W_x\subseteq A\implies \varphi(x)\downarrow \and \varphi(x)\in A\setminus W_x $
  • Definice: Množina B je kreativní, pokud je r.s. a $ \bar{B} $ je produktivní.
  • Příklady
    • K je kreativní - je RS a $ \bar{K} $ je produktivní, za φ se zvolí identita
  • Vlastnosti (úplné množiny)
    • Ke každé produktivní množině B existuje produktivní ORF φ (dá se sestrojit z původní produktivní ČRF)
    • Ke každé produktivní množině B existuje produktivní ORF bijekce φ (dá se sestrojit z původní produktivní ČRF)
    • Každá produktivní množina B obsahuje nekonečnou ČR množinu - prázdná množina patří do B a φ nám vrátí vždy nový prvek z B, který se dá přidat k výchozí podmnožině B, atd.
  • Ekvivalence
    • B je produktivní, K je 1-převeditelná na B, K je m-převeditoelná na B
    • A je kreativní, A je 1-úplná, A je m-úplná

Algoritmicky nerozhodnutelné problémy

see wen:List of undecidable problems
  • Halting problém, Riceova věta
  • Postův korespondeční problém PKP (i s omezením na iniciální řešení IPKP).
    • Lze ukázaat IPKP <=> TS zastaví nad slovem u.
  • Pro bezkontextové gramatiky G1,G2 je algoritmicky nerozhodnutelné zda L(G1)∩L(G2)={}.
Důkaz: převedeme PKP na daný problém máme PKP [u1,v1],..., [un,vn]
zvolíme nové terminály a1,…,an pro kódy indexů
G1: S→ uiSai | uiai generuje slova ui1... uikaik... ai1
G2: S→ viSai | viai generuje slova vi1... vikaik... ai1
PKP má řešení právě když L(G1) ∩L(G2)≠{}
u-část = v-část + složky ai< zajišťují stejné pořadí
  • Je algoritmicky nerozhodnutelné, zda je bezkontextová gramatika víceznačná.
Důkaz:
S → S1 | S2
S1 → uiSai | uiai
S2 → viSai | viai
PKP má řešení právě když je gramatika víceznačná
  • 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ší bod, 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í
    Vezmu r.s. efektivně neoddělitelné A,B tž. $ x\in A\implies\vdash_T G(\bar{x}) $ a $ x\in B\implies\vdash_T \neg G(\bar{x}) $.
    Vezmeme $ A_1=\{x;\vdash_T G(\bar{x})\} $, $ B_1=\{x;\vdash_T \neg G(\bar{x})\} $ ($ A\subseteq A_1 $, $ B\subseteq B_1 $). Z bezespornosti A1 a B1 disjunktní a nejsou rekurzivní (separovaly by).
  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 $)
    Množiny A1 a B1 z bodu (1) jsou nyní r.s. a umím tedy efektivně určit bod mimo ně (číslo fle nedokazatelne ani nevyvratitelné v T).
    • v T nelze dokázat vlastní bezespornost (za o něco silnějších předpokladů o teorii T -- např. $ \Sigma_1-\mbox{indukce} $)

Materiály

  • Pohádky z vyčíslitelnosti – velmi neformální úvod do problematiky
  • Wiki skripta z vyčíslitelnosti – neúplná, ale podrobná
  • Vyčíslitelnost I – stránka předmětu na wiki, obsahuje odkazy na další materiály
  • Pavliska V., Vyčíslitelnost a Složitost 1 a 2, Ostravská Univerzita, [2] a [3]
  • Demuth O., R. Kryl R., Kučera A., Teorie algoritmů I a II, skripta MFF-UK
  • Češka M., Vojnar T., Smrčka A., Teoretická informatika, VUT Brno [4]