TIN065 Prednáška 06
| Prednášky z Vyčísliteľnosti II |
| Obsah |
|---|
|
Na minulej prednáške sme si spomenuli základný vzťah medzi limitami a skokom medzi stupňami (zatiaľ iba od $ \emptyset $ k $ \emptyset' $). Najprv špecifický prípad, kde sme mali $ \emptyset' $-rekurzívne A a platilo $ A \leq_T \emptyset'\iff C_A(x)=\lim_{s \to \infty} f(x, s) $ pre nejakú ORF f. Mali sme neefektívne orákulum, ale nám stačilo ho aproximovať na konečnej časti. A pýtali sme sa, či už je výsledok stabilný.
Všeobecnejšia veta zasa mala dve časti. Jedným smerom: ak máme ORF f, tak $ \lim_{s \to \infty} f(x, s) $ je $ \emptyset' $-ČRF. Pomocou while cyklu sme hľadali najmenšie s také, že sa nám to stabilizuje. Opačným smerom zasa $ \emptyset' $-ČRF $ \varphi $ je podmienene rovná $ \lim_{s \to \infty} f(x,s) $ pre nejakú ORF f. Mali sme teda $ \Phi_z(\emptyset')(x) $ (to je naša $ \varphi $), ktoré nemusí vždy konvergovať a my aproximujeme celý výpočet. Vytvárame si výpočet pre konečné množstvo krokov a vraciame $ <\sigma, x, y> $ ak platí: $ \Phi_{z,s}(\sigma)(x)=y $ & $ \sigma \leq \emptyset'_s $. Keď sa nám výpočet stabilizuje, tak vrátime z neho tretiu zložku a to bude výsledok našej f (ak sa výpočet nestabilizuje, tak limita f nebude existovať).
Dnes sme začali dodatkom: $ (\exists $ ORF $ h) $$ (\Phi_z(\emptyset')(x) \simeq \lim_{s \to \infty} h(z,x,s)) $.
Základná myšlienka je - ak aplikujeme limitu, prejdeme o skok vyššie. To si zhrnieme nasledujúcou ešte všeobecnejšou vetou:
Obsah
Ešte všeobecnejšia veta
Veta: (relativizácia)
- Ak f je A-ORF, tak $ \lim_{s \to \infty} f(x, s) $ je A' ČRF.
- Pre ľubovoľnú A'-ČRF $ \varphi $ existuje A-ORF g taká, že $ (\forall x)(\varphi(x) = \lim_{s \to \infty} g(x, s)) $.
- Dokonca $ (\exists a)(\forall A)(\Phi_z(A')(x) \simeq \lim_{s \to \infty} \Phi_a(A)(z, x, s)) $, kde $ g = \Phi_a(A) $ a je všade definovaná. Pekné je, že a nezávisí na A.
Dokazuje sa to relativizáciou dôkazu z minulej prenášky. Len namiesto $ \emptyset $ všade napíšeme A. Takže keď sme mali rekurzívne spočítateľnú $ \emptyset' $ a $ \emptyset' = W_{z_0, s}^\emptyset $, kde s boli kroky, tak teraz budeme mať pre každé A množinu $ W_{z_0}^A = A' $. A' je A-rekurzívne spočítateľná a vieme, že $ A' = W_{z_0}^A $ a to sa aproximuje cez $ W_{z_0, s}^{A^\prime} $. Dôkaz bude rozvnaký ako minule.
Dôsledok: $ \Phi_z(\emptyset^{(n+1)})(x) \simeq \underbrace{\lim_{t_0 \to \infty}, \lim_{t_1 \to \infty}, \ldots, \lim_{t_n \to \infty}}_{n+1 \mbox{ limit}} f(z, x, t_0, t_1, \ldots, t_n) $, kde vnútorné limity ($ t_1 \to \infty, \ldots, t_n \to \infty $) existujú a vonkajšia pre $ t_0 \to \infty $ existovať nemusí. Dokazuje sa to iteráciou predchádzajúceho dôkazu ("je to vidět") pravdepodobne s troškou indukcie. Vnútri sú ORF, preto vnútorné limity musia existovať.
Takže z tejto časti si odnesieme to, že prechod o skok niektorým smerom znamená pridať alebo odbrať limitu.
Vsuvka: O niektorých množinách a kvantifikátoroch
Označme si nasledujúce množiny takto:
- $ A = \{x: W_x = \emptyset\} $
- $ B = \{x: W_x \neq \emptyset\} $
- $ Fin = \{x: W_x \mbox{ je konečná}\} $
- $ Inf = \{x: W_x \mbox{ je nekonečná}\} $
- $ Tot = \{x: W_x = \mathbb{N}\} $
- $ Rek = \{x: W_x \mbox{ je rekurzívna}\} $
Tvrdenie: B je rekurzívne spočítateľná a $ B \equiv_1 K $.
Prvá časť je vidieť. $ B = \{x: \exists s : W_{x, s} \neq \emptyset\} = \{x:\exists y, s : y \in W_{x, s}\} $, kde na konci máme existenčný kvantifikátor na rekurzívnej podmienke, takže je to rekurzívne spočítateľné.
Prevoditeľnosť K na B vyplýva z prevoditeľnosti K na Tot, keďže Tot je podmnožina B. Chceme teda nájsť takú ORF f, pre ktorú bude platiť $ \varphi_{x}(x)\downarrow \iff W_{f(x)} = \mathbb{N} $. Opäť pomôže s-m-n veta a fiktívna premenná. Definujme ČRF $ \alpha $ takto: $ \alpha(x,w)\downarrow \iff \varphi_{x}(x)\downarrow $. Funkcia $ \alpha $ má index e, použijeme s-m-n vetu: $ \alpha(x,w) \simeq \varphi_{e}(x,w) \simeq \varphi_{s_1(e,x)}(w) $. Našu f definujme $ f(x) = s_1(e,x) $. Potom pre každé w: $ x \in K \iff \varphi_{x}(x)\downarrow \iff \alpha(x,w)\downarrow \iff \varphi_{f(x)}(w)\downarrow \iff W_{f(x)} = \mathbb{N} \iff f(x) \in Tot $. Takže K je prevediteľná na Tot a teda ja na B.
Ešte ukážeme, že $ B \leq_1 K $. Rovnakým postupom ako pri dôkaze opačného smeru si vytvoríme funkciu $ \beta(x, y, w) $ s fiktívnou premennou $ w $ a z jej indexu pomocou s-m-n vety vytvoríme ORF funkciu $ g(x) $. Pre túto funkciu $ g(x) $ bude platiť, že pre každý vstup $ x $ vráti číslo programu, ktorý ignoruje svoj vstup a skonverguje práve vtedy, ak nájde nejaký prvok, ktorý padne do $ W_x $.
Formálne: Funkciu $ \beta(x, y, w) $ definujeme takto: $ \beta(x, y, w)\downarrow $$ \iff $$ \varphi_x(y)\downarrow $ Nech $ \beta(x, y, w) $ má index $ e $. Potom platí: $ \beta(x, y, w)\downarrow $$ \iff $$ \varphi_e(x, y, w)\downarrow $$ \iff $$ \varphi_{s_2(e, x, y)}(w)\downarrow $. Zadefinujeme si: $ g(x) = s_2(e, x, y) $ pre pevné $ x $ a $ y $. Potom platí: $ x \in B $$ \iff $$ (\exists y)(\varphi_x(y)\downarrow) $$ \iff $$ (\exists y)(\beta(x, y, w)\downarrow) $$ \iff $$ (\exists y)(\varphi_e(x, y, w)\downarrow) $$ \iff $$ (\exists y)(\varphi_{s_2(e, x, y)}(w)\downarrow) $$ \iff $$ (\exists y)(\varphi_{g(x)}(w)\downarrow) $. Funkcia $ g(x) $ nezávisí na $ w $. Položme teda $ w = g(x) $ a dostávame: $ (\exists y)(\varphi_{g(x)}(w)\downarrow) $$ \Longrightarrow $$ (\exists y)(\varphi_{g(x)}(g(x))\downarrow) $$ \iff $$ (\exists y)(g(x) \in K) $. Problémy sú dva: prvým je, že sled ekvivalencií je porušený jednou implikáciou a druhým je existenčný kvantifikátor cez premennú y, ktorý sa stále objavuje pred požadovanou formulou $ g(x) \in K $.
Pre takúto funkciu $ g $ má platiť: $ x \in B $$ \iff $$ W_x\neq \emptyset $$ \iff $$ g(x) \in W_{g(x)} $$ \iff $$ g(x) \in K $. A teda $ B \leq_1 K $.
Iná možnosť dôkazu $ B \leq_1 K $ je, že si spomenieme na to, že K je 1-úplná.
Keďže $ A = \overline{B} $, tak $ A \equiv_1 B $ a preto A nie je rekurzívne spočítateľná.
Ešte je vhodné si všimnúť, že A aj B majú v definícii jeden kvantifikátor ($ \exists y $ ... alebo $ \forall y $ ...).
Množiny s dvoma kvantifikátormi
- Fin: $ \{x: (\exists s_0)(\forall s > s_0)(s \notin W_x)\} $ alebo tiež $ (\exists s_0)(\forall s > s_0)(\forall t)(s \notin W_{x, t}) $.
- Inf: podmienka: $ (\forall s)(\exists j)(j>s $ & $ j\in W_{x}) $ alebo tiež $ (\forall s)(\exists j)(\exists t)(j>s $ & $ j\in W_{x, t}) $
- Tot: $ (\forall s)(\exists t)(s \in W_{x, t}) $
Tvrdenie: Inf$ \equiv_1 $Tot.
Opäť si vytvoríme funkciu $ \alpha $: $ \varphi_{\alpha(x)}(j)\downarrow \iff \{0, 1, \ldots, j\} \subset W_x $. Pre stále väčšie j je vpravo stále väčšia množina a $ \alpha $ s rastúcim j kontorluje, či j stále náleží do $ W_x $. Ak nejaké $ y_0 $ nie je prvkom $ W_x $, tak $ (\forall y \geq y_0)(\varphi_{\alpha(x)}(y)\uparrow) $ (už sa tam nedostane).
Opačne: $ \varphi_{\beta(x)}(j)\downarrow $ práve vtedy, ak existuje aspoň j prvkov vo $ W_x $. $ x \in \mbox{Inf} \iff \beta(x) \in \mbox{Tot} $. Vezmeme si $ W_x $ a efektívne ho generujeme. Keď sme vypísali aspoň j čísel, tak $ \varphi_{\beta(x)}(j)\downarrow $.
$ \mbox{Fin} = \overline{\mbox{Inf}} $.
Platí tiež: $ \overline{\emptyset^{(2)}} \equiv \mbox{Tot} $, teda $ \emptyset^{(2)} \equiv \overline{\mbox{Tot}} \equiv \mbox{Fin} $.
Aritmetická hierarchia
Aritmetická hierarchia je klasifikácia množín podľa aritmetickej zložitosti. S hierarchiami sa stretávame vo viacerých oblastiach. Napríklad v analýze sa dá stretnúť s borelovskou hierarchiou, na zložitosti máme polynomiálnu hierarchiu. Obidve tieto hierarchie sa trochu podobajú našej. V borelovskej by namiesto kvantifikátorov mali byť zjednotenia a prieniky, v polynomiálnej budeme kvantifikátory nejako polynomiálne obmedzovať.
Pozrieme sa na hierarchiu "trochu s nadhľadom" a budeme vynechávať premenné, aby sa nám ľahšie písali a chápali definície.
Definícia: $ \Sigma_n $ prefix (respektíve $ \Pi_n $ prefix) je konečná skupina kvantifikátorov, ktorá má n podskupín, z ktorých každá je homogénna (to znamená, že v nej sú len kvantifikátory rovnakého typu: len $ \exists $ alebo len $ \forall $), skupiny sa striedajú a $ \Sigma_n $ začína existenčným a $ \Pi_n $ začína všeobecným kvantifikátorom.
Keby sme tú definíciu chceli napísať aj s premennými, tak si musíme dávať pozor na veci ako pomenovanie premenných a rozsahy ich platnosti.
Definícia: Prefix sa nazýva redukovaný, ak každá jeho podskupina je jednočlenná, takže sa v prefixe striedajú iba jednotlivé kvantifikátory.
Prečo sa to volá aritmetická hierarchia? Pretože kvantifikátory sú cez objekty najnižšieho možného rádu - základné objekty - čísla. Niekedy sa prefixy označujú aj horným indexom $ \Sigma_n^0 $, kde nula označuje úroveň kvantifikácie. V analýze sa používa aj vyššia úroveň kvantifikácie. Napríklad prvá úroveň tam predstavuje kvantifikáciu cez funkcie (pre každú funkciu), prípadná druhá úroveň predstavuje operátory (zobrazenia z funkcií do funkcií). Niekedy sa naviac ako $ \Sigma_n^p $ označujú triedy polynomiálnej hierarchie, napríklad a často v zložitosti. V značení je teda trošku zmätok.
Definícia: Predikát je prvkom triedy $ \Sigma_n $, resp. $ \Pi_n $ (presnejšie $ \Sigma_n^0 $ a $ \Pi_n^0 $), ak je vyjadriteľný v tvare $ \Sigma_n $ prefix na nejaký všeobecne rekurzívny predikát (ORP), respektíve $ \Pi_n $ prefix na ORP, pre nejaké konečné n.
Pre množinu je tá definícia veľmi podobná.
Trieda $ \Sigma_0 = \Pi_0 $ predstavuje práve všetky rekurzívne, teda algoritmicky rozhodnuteľné, množiny (definované iba samotným ORP, bez akéhokoľvek prefixu).
Trieda $ \Sigma_1 $ obsahuje práve všetky rekurzívne spočítateľné množiny (RSM), trieda $ \Pi_1 $ obsahuje práve všetky ich negácie.
Triedy môžeme tiež relativizovať. Potom trieda $ \Sigma_n^{0,A} $ predstavuje práve všetky množiny, ktorých popis je možné vyjadriť v tvare $ \Sigma_n $ prefix na A-ORP. Obdobne sa definuje $ \Pi_n^{0, A} $. Potom $ \Sigma_0^{0, A} = \Pi_0^{0, A} $ sú práve všetky A-rekurzívne množiny (A-RM).
Definícia: Predikát je aritmetický, ak je vyjadriteľný pomocou logiky prvého rádu aplikovanej na nejaký ORP. To znamená, že sa nesmie kvantifikovať cez funkcie ani cez nič iné, okrem samotných čísel.
Veta: Predikát je aritmetický práve vtedy, ak je prvkom nejakej triedy $ \Sigma_n $ alebo $ \Pi_n $. Dôkaz: Jedným smerom to ide priamo, druhým smerom je to cvičenie na prenexné operácie.
Pozorovanie: Z akéhokoľvek predikátu obsahujúceho ľubovoľný prefix aplikovaný na ORP sa vždy sa dá vyrobiť ekvivalentný predikát, obsahujúci redukovaný prefix. Ak máme napríklad $ (\exists x)(\exists y)(P(x, y)) $, tak to prevedieme na $ (\exists w)(P(w_{(2, 1)}, w_{(2, 2)})) $, kde w je kód dvojice a v predikáte používame namiesto x a y $ w_{(2,1)} $ a $ w_{(2,2)} $, teda prvú, respektíve druhú zložku z kódu dvojice. Tak isto postupujeme pre všeobecné kvantifikátory a pre podskupiny obsahujúce ľubovoľný konečný počet kvantifikátorov rovnakého typu.
Platí: Obmedzené kvantifikátory nám tiež nevadia. Majme predikát $ (\forall x \leq t)(\exists y)(R(x,y)) $, kde R je nejaký ORP. To znamená, že pre každú z konečného počtu "kvantifikovaných" hodnôt premennej x existuje y také, že platí predikát $ R(x, y) $. Vytvorme si teda najprv $ t+1 $-ticu $ (y_0 \dots y_t) $ takú, že na $ i $-tom mieste bude to $ y_i $, ktoré "existuje" pre $ i $-té $ x $ (pre $ i = 0 \dots t $). Túto $ t+1 $-ticu môžeme kódovať jediným číslom $ y_{(t+1)} $, takže dostaneme nový výraz ekvivalentný s pôvodným: $ (\exists y_{(t+1)})(\forall x \leq t)(R(x, y_{(t+1, x+1)})) $. Vyberáme $ x $-tú zložku z $ y_{(t+1)} $ (ale píšeme $ y_{(t+1, x+1)} $, pretože vydeľovanie zložky sa indexuje od jednotky a nie od nuly). V tomto príklade okrem inkriminovanej dvojice žiadne ďalšie kvantifikátory vo výraze nie sú, ale presne takto to funguje aj vtedy, keď tam ešte nejaké, pred alebo za, sú. Pri obmedzenom existenčnom kvantifikátore výraz najprv znegujeme, použijeme "posunutie obmedzeného všeobecného kvantifikátora dovnútra" a znegujeme naspäť. Pomocou popísaného postupu môžeme obmedzené kvantifikátory dostať až k všeobecne rekurzívnemu predikátu (ORP), kde ich zameníme za konečnú konjunkciu alebo disjunkciu a tak sa ich zbavíme úplne.
A ešte poznámka na záver: Ak povieme, že niečo je prvkom $ \Sigma_n $, tak to znamená, že sa to dá vyjadriť ako ORP so $ \Sigma_n $ prefixom a nás bude zaujímať, ako to vyjadriť čo najlepšie (najkrajšie). A tiež sa pokúsime zistiť, či by nešlo vyjadriť množinu/predikát ekvivalentne pomocou kratšieho prefixu (napríklad K je v $ \Sigma_1 $, ale už nie je v $ \Sigma_0 $). Súvisí to so skokmi $ \emptyset $, ktoré kopírujú triedy $ \Sigma_n $.
