TIN065 Prednáška 08
| Prednášky z Vyčísliteľnosti II |
| Obsah |
|---|
Vieme klasifikovať množiny a predikáty podľa ich aritmetického tvaru. Triedime ich do skupín $ \Sigma_n $ a $ \Pi_n $ podľa ich prefixu. Keď urobíme zjednotenie cez všetky $ n $, dostaneme aritmetickú hierarchiu.
Tiež vieme, že $ \Sigma_0=\Pi_0 $ nemajú univerzálny $ \Sigma_0 $ (ani $ \Pi_0 $) predikát, ale vyššie už univerzálny predikát máme. Tým máme výhodu oproti zložitosti a ich polynomiálnej hierarchii pretože tam nemajú univerzálny polynóm. Tiež ešte vieme, že $ \Sigma_n - \Pi_n $ je neprázdne.
Minule sme si definovali $ \Sigma_n $ úplnosť a povedali si vetu o hierarchii, tak ich tu skopírujem:
- $ \Sigma_n $úplnosť
- A je $ \Sigma_n $ úplná ak je v $ \Sigma_n $ a hocijaká B zo $ \Sigma_n $ sa dá 1-previesť na A.
Veta o hierarchii:
- $ \forall n \geq 1: \emptyset^n $ je $ \Sigma_n $ úplná.
- A je rekurzívne spočetná v $ \emptyset^n \iff A \in \Sigma_{n+1} \forall n \geq 0 $
- $ A \leq_T \emptyset^n \iff A\in \Sigma_{n+1} \cap \Pi_{n+1} $
Táto veta nám zväzuje aritmetickú hierarchiu s operáciou skoku.
Dôkaz: Časť 3 vyplýva z časti 2 a z postovej vety. Majme množinu A: $ A\leq_T \emptyset^{(n)} \iff A , \overline{A} \mbox{ sú rekurzívne spočetné v }\emptyset^{(n)} \iff A,\overline{A} \in \Sigma_{n+1} \iff A\in \Sigma_{n+1}\cap \Pi_{n+1} $. Prvá ekvivalencia je z postovej vety, druhá z časti 2 tejto vety a tretia z toho, že ak $ A\in\Sigma_n $, tak $ \overline{A}\in \Pi_n $.
Je možné sa niekedy stretnúť so značením $ \Delta_n $. To je synonymum pre $ \Sigma_n \cap \Pi_n $.
Časť 1 opäť vyplýva z časti 2. Pre $ n \geq 1 $ je $ \emptyset^{(n)} $ rekurzívne spočetné v $ \emptyset^{(n-1)} $ kvôli operácii skoku a podľa druhej časti vety je v $ \Sigma_n $. Opačným smerom ak máme niečo v $ \Sigma_n $, tak podľa časti 2 je to rekurzívne spočetné v $ \emptyset^{(n-1)} $ a podľa vlastnosti skoku je to 1-prevoditeľné na $ \emptyset^{(n)} $.
Takže nám treba dokázať druhú časť vety o hierarchii. To sa urobí indukciou podľa $ n $. Pre $ n = 0 $ to vieme. Ak je A rekurzívne spočetná, tak sa zapíše pomocou existenčného kvantifikátoru na rekurzívny predikát. A opačne.
Tak sa pozrime na indukčný krok. najprv jedným smerom.
Majme množinu $ A \in \Sigma_{n+1} $. A sa dá teda vyjadriť v tvare $ \exists \forall \ldots Q(\ldots) $. Odrežme to za prvým kvantifikátorom. To, čo dostaneme je v $ \Pi_{n} $. Negácia toho je v $ \Sigma_n $ a podľa indukčného predpokladu je rekurzívne spočetná v $ \emptyset^{(n-1)} $. z vlastnosti skoku je rekurzívna v $ \emptyset^{(n)} $. Keď je negácia rekurzívna v $ \emptyset^{(n)} $, tak aj bez negácie je to rekurzívne v $ \emptyset^{(n)} $ a po pridaní odtrhnutého kvantifikátoru späť je to rekurzívne spočetné v $ \emptyset^{(n)} $.
Opačným smerom si ukážeme dva postupy.
Predpokladajme, že A je rekurzívne spočetné v $ \emptyset^{(n)} $ A je teda definičným oborom $ \Phi_z(\emptyset^{(n)}) $ pre nejaké z. Teda $ x \in A \iff \exists \sigma \exists y,s(\Phi_{z,s}(\sigma)(x) = y \And \sigma \leq \emptyset^{(n)} $. $ \Phi_{z,s}(\sigma)(x) = y $ je rekurzíva podmienka, takže nám zostáva niečo tvaru: $ \exists(\sigma \leq \emptyset^{(n)}) $ a potrebujeme zistiť, aká zložitá je táto vec. $ \sigma $ je vlastne konečná konjunkcia dĺžky $ |\sigma| $ a hovorí nám: $ \sigma(j) = 1 \implies j \in \emptyset^{(n)} $ a $ \sigma(j) = 0 \implies j \notin \emptyset^{(n)} $ pre každé $ j < |\sigma| $. Tu použijeme indukčný predpoklad a to taký, že to, že $ j \in \emptyset^{(n)} $ je $ \Sigma_n $ a $ j \notin \emptyset^{(n)} $ je $ \Pi_n $ (pretože $ \emptyset^{(n)} $ je rekurzívne spočetná v $ \emptyset^{(n-1)} $ a z indukčného predpokladu je to $ \Sigma_n $ a preto aj $ \overline{\emptyset^{(n)}} $ je $ \Pi_n $. Takže naše $ \exists(\sigma \leq \emptyset^{(n)}) $ je vlastne $ \exists(\Sigma_n \And \Pi_n) $, kde to vnútri je konjunkcia mnohých ($ |\sigma| $) $ \Sigma_n $ a $ \Pi_n $ vecí. Prenexnými operáciami môžeme vytiahnúť zo $ \Sigma_n $ jeden kvantifikátor vonku a zvyšok $ \exists (\Pi_{n-1}\And \Pi_n) $ je $ \Sigma_{n+1} $.
Druhá možnosť je použiť vetu o limitnej vyčísliteľnosti. Ak máme $ A=\mbox{dom}(\Phi_z(\emptyset^{(n)}) $, tak podľa vety o limitnej vyčísliteľnosti: $ \Phi_z(\emptyset^{(n)}) = \lim_s h(z,x,s) $, kde $ h $ je $ \emptyset^{(n-1)} $ORF. Takže $ x \in A \iff \Phi_z(\emptyset^{(n)})\downarrow $ a to je práve vtedy, keď existuje tá limita. To je práve vtedy, keď $ \exists s_0 \forall s \geq s_0 (h(z,x,s)=h(z,x,s_0)) $. Tá vec v poslednej zátvorke je rekurzívna v $ \emptyset^{(n-1)} $ a podľa indukčného predpokladu je v prieniku $ \Sigma_n\cap\Pi_n $, čiže aj v $ \Pi_n $. Máme $ \exists s_0 \forall s \geq s_0 (\Pi_n) $. Všeobecný kvantifikátor necháme pohltiť v $ \Pi_n $ a existenčný z toho vyrobí $ \Sigma_{n+1} $.
Relativizácia funguje aj na túto vetu: $ A\leq_T B^{(n)} \iff A \in \Sigma^B_{n+1}\cup\Pi^B_{n+1} $ a $ A $ je rekurzívne spočetná v $ B $ práve vtedy, keď $ A \in \Sigma_{n+1}^B $.
Tým skončila teória prednášky a nasledovali dva príklady, kde sa ukazovalo, že Tot je $ \Pi_2 $úplná a že Rek je $ \Sigma_3 $úplná. Snáď to tu ešte dopíšem.
Príklad: Tot je $ \Pi_2 $úplná.
Vieme, že Tot je v $ \Pi_2 $ $ (\{x| \forall y \exists s (\varphi_x(y)\downarrow)\} $ za menej ako s krokov.). Ak vezmeme ľubovoľnú $ B \in \Pi_2 $, tak potrebujeme ukázať, že sa dá 1-previesť na Tot. Naša $ B $ sa dá zapísať ako $ x \in B \iff \forall y \exists s (\underbrace{Q(x,y,s)}_{\mbox{rekurzívne}}) $. Tak si vytvoríme pomocnú ČRF $ \alpha(x,y) \simeq \mu_s Q(x,y,s) $. Ak máme prvok $ x \in B $, tak pre každé $ y $ existuje $ s $, také, že platí $ Q(x,y,z) $ (tiež sa hovorí, že existuje $ \Sigma_1 $ svedok alebo že nastane $ \Pi_2 $ udalosť (tieto pojmy neznamenajú to isté, treba skontrolovať, čo to presne je). Ak $ x \notin B $, tak sa také $ s $ aby $ Q(x,y,s) $ platilo, pre nejaké $ y_0 $ nájsť nepodarí. A naše $ \alpha(x,y) $ také $ s $ hľadá. Podľa s-m-n vety je $ \alpha(x,y) \simeq \varphi_{g(x)}(y) $, kde $ g(x) $ je ORF (dokonca by to mala byť PRF), ktorá prevádza $ B $ na Tot ($ x \in B \iff g(x) \in \mbox{Tot} $). Podrobnejšie: Ak $ x \in B $, tak pre každý $ y $ nájde $ \alpha(x,y)\simeq \varphi_{g(x)}(y) $ svedka $ s $, teda sa zastaví (a $ g(x) \in \mbox{Tot} $) a pre $ x \notin B $ svedka pre nejaké $ y_0 $ nenájde, takže tam nezastaví (a preto $ g(x) \notin \mbox{Tot} $).
Nakoniec sme si povedali a zosumarizovali, že
- Fin je $ \Sigma_2 $-úplná.
- Tot, Inf sú $ \Pi_2 $-úplné/
- Rek je $ \Sigma_3 $-úplná.
Tak sa pozrime na Rek a ukážme, že je $ \Sigma_3 $úplná. $ \mbox{Rek}=\{x:W_x \mbox{ je rekurzívne }\} $.
Dôkaz: Nech $ B \in \Sigma_3 $, teda $ x \in B \Leftrightarrow \exists z \forall y \exists s Q(x,z,y,s) $, kde $ z $ je $ \Sigma_3 $-svedok.
Majme $ W_{\alpha(x)} = \{ \langle z,y\rangle: \exists s Q(x,z,y,s) \} $ $ \langle z,y \rangle $ čaká na svojho svedka $ W_{\beta(x)} = \{ \langle z,y\rangle: \forall j \leq y \exists Q(x,z,j,s)\} $ každý stĺpec je závislý počiatočný úsek, ak to platí pre $ y $, tak to platí aj pre menšie od $ y $.
Ak $ x \in B $, potom v $ W_{\beta(x)} $ existuje stĺpec $ z $, ktorý je plný, lebo potom to platí pre všetky $ y $. Ak $ x \not\in B $, potom všetky stĺpce v $ W_{\beta(x)} $ sú konečné.
$ W_{\gamma(x)} = $ stĺpce rastú smerom doprava, s bodmi $ \langle z,y \rangle $ z $ W_{\beta(x)} $ pridaj do $ W_{\gamma(x)} $ aj $ \langle i,j \rangle i \leq z \land j \leq y $.
Ak $ x \in B $, potom na začiatku niekoľko konečných stĺpcov a potom všetko nekonečné totálne stĺpce. Ak $ x \not\in B $, potom všetky stĺpce sú konečné (aj keď neklesajúce).
$ E = \{ \langle z,j\rangle: z\in K \And j \leq\mbox{ počet krokov kedy }z \mbox{ vstúpi do }K \} $
$ W_{\sigma(x)} = W_{\gamma(x)} \cup E $. $ x \in B $ je niekoľko konečných a zvyšok nekonečné až totálne - rekúrzivne. $ x \not\in B $ sú všetky stĺpce konečné v $ W_{\sigma(x)} $, ale $ W_{\sigma(x)} $ je nerekurzívna.
Ak by bola $ W_{\sigma(x)} $ rekurzívna, tak musí existovať ORF $ h(z) $, ktorá dáva min. $ y: \langle z,y \rangle \not\in W_{\sigma(x)} $. $ z \in K \Leftrightarrow z $ padne do $ K $ za menej ako $ h(z) $ krokov $ z \in K_{h(z)} $ potom $ K $ je rekurzívna, čo je spor.
$ x \in B \Leftrightarrow W_\sigma(x) $ je rekurzívna.
Dôkaz si treba pár krát sparsovať, uvedomiť si čo spraví $ E $, keď ju pridáme, atď.
