TIN065 Zhrnutie

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

Toto je zhrnutie poznatkov potrebných na skúšku. Skúška z Vyčísliteľnosti II obsahuje dve otázky. Prvá otázka sa týka jednej zo základných tém. V druhej otázke je možné si vybrať z jednej z ponúknutých tém a vypracovať len tú (nikto nebráni vybrať si všetky).

Základné témy (prvá otázka):

  1. Operácia skoku a jej vlastnosti
  2. Limitná vyčísliteľnosť
  3. Aritmetická hierarchia

Rozširujúce témy (druhá otázka)

  1. 1-generickosť
  2. rekurzívne stromy
  3. $ \Sigma_n $ alebo $ \Pi_n $ úplnosť

Základy[editovat | editovat zdroj]

ČRFál $ \Phi_z(A)(x) $ je program s číslom $ z $, ktorý má na vstupe $ x $ a množinu $ A $, ktorú používa ako orákulum. $ \Phi_{z,s} $ je ČRFál za $ s $ krokov. Je to tiež rekurzívna množina nekolidujúcich trojíc $ <\sigma, x, y> $ takých, že z $ x $ pomocou časti orákula $ \sigma $ vypočítame $ y $. To, že sú trojice $ <\sigma, x, y> $ nekolidujúce znamená, že z dlhšieho $ \sigma $ nemôžeme dostať iné $ y $ ako z kratšieho. Nie každá rekurzívne spočetná množina $ W_z $ je ČRFál, ale z každej môžeme ČRFál vyrobiť regularizačnou funkciou $ \rho $, ktorá konfliktné dvojice oreže.

$ (\forall W_z)(\exists \Phi_{\rho(z)}) $

$ A \leq_T B $ znamená, že existuje ČRFál $ \Phi $ taký, že $ C_A(x) = \Phi(B)(x) $. Tým pádom funkcia $ \Phi(B)(x) $ je totálna. Hovoríme, že $ A $ je $ B $-rekurzívna (rekurzívna v $ B $).

$ W_z^A=\{x: \Phi_z(A)(x)\downarrow\} $$ A $ rekurzívne spočetné množiny.

Operácia skoku a jej vlastnosti[editovat | editovat zdroj]

Pre množinu $ A $ definujeme množinu $ A^\prime = \{x:\Phi_x(A)(x)\downarrow\} = \{x: x\in W_x^A\} $ ako skok množiny $ A $.

Veta (vlastnosti skoku):

  1. A' je A-rekurzívne spočetná
  2. A' nie je A rekurzívna
  3. B je A-rekurzívne spočetná práve vtedy, keď B je 1-prevoditeľná na A'
  4. Ak A je rekurzívne spočetná v B a zároveň B je turingovsky prevoditeľná na C $ (B \leq_T C) $, tak A je rekurzívne spočetná v C
  5. $ A\leq_T B \iff A' \leq_1 B' $
  6. $ A\equiv_T B \iff A' \equiv_1 B' $

Dôkaz:

  1. Z definície.
  2. Podľa Postovej vety. Sporom ukážeme, že $ \overline{A^\prime} $ nie je $ A $ rekurzívne spočetná. Nech teda je a je to množina $ W_{x_0} $. Ak $ x_0 \in \overline{A^\prime} = W_{x_0} $, tak z definície $ A^\prime $ platí $ x_0 \in A^\prime $, čo je spor. Ak $ x_0 \notin \overline{A^\prime} = W_{x_0} $, tak $ x_0 \notin A^\prime $, teda $ x_0 \in \overline{A^\prime} $, čo je zasa spor. Teda $ \overline{A^\prime} $ nie je $ A $ rekurzívne spočetná.
  3. Najťažšia a najdôležitejšia časť tejto vety.
    • $ B\leq_1 A^\prime $ $ \iff $ $ (\exists \mathrm{ORF} f)(x \in B \iff f(x) \in A^\prime) $ $ \iff $ $ (\exists \mathrm{ORF} f)(x \in B \iff \Phi_{f(x)}(A)(f(x))\downarrow) $. Definícia množiny $ B $ je teda rekurzívne spočetná v $ A $.
    • $ B $ je $ A $ rekurzívne spočetná, teda $ (\exists z_0)(B = \{x : \Phi_{z_0}(A)(x)\downarrow) $. Vyrobíme si funkciu $ \alpha(z, x, w) \simeq \Phi_z(A)(x) $ s jedným parametrom naviac ($ w $). Funkcia $ \alpha $ je $ A $ rekurzívne spočetná, a teda má index, ktorý si označme $ a $. Teda platí: $ \alpha(z, x, w) = \Phi_a(A)(z, x, w) $. Použijeme s-m-n vetu: $ (\exists PRF g)(\alpha(z, x, w) = \Phi_a(A)(z, x, w) = \Phi_{g(a, z, x)}(A)(w)) $. Zadefinujeme si $ f(x) = g(a, z_0, x) $. $ f $ je definovaná pomocou $ g $, takže je PRF, a teda aj ORF. Potom bude platiť: $ f(x) \in A^\prime \iff \Phi_{f(x)}(A)(f(x))\downarrow \iff \Phi_{g(a, z_0, x)}(A)(g(a, z_0, x))\downarrow \iff \alpha(z_0, x, g(a, z_0, x))\downarrow \iff \Phi_{z_0}(A)(x)\downarrow \iff x \in B $. Teda dokázali sme ekvivalenciu: $ x \in B \iff f(x) \in A^\prime $, čo je presná definícia $ B\leq_1 A^\prime $.
  4. Intuitívne: Vezmeme si ČRFál $ \Phi_z $, ktorý pomocou $ B $ zisťuje, či je niečo prvkom $ A $. Zisťuje to rekurzívne spočetne: ak $ x \in A $, tak to časom zistí, ak $ x \notin A $ tak nezastaví. Tento ČRFál sa raz za čas pýta na $ B $. A každú otázku na $ B $ nahradíme spočítaním $ B $ z $ C $ (tentokrát už rekurzívnym), čiže nejakými otázkami na $ C $. Takže $ A $ je rekurzívne spočetná v $ C $.
  5. Dôkaz poskladáme z predchádzajúcich tvrdení.
    • Nech $ A' \leq_1 B' $. $ A $ aj $ \overline{A} $ sú obe $ A $ rekurzívne, a teda sú aj $ A $ rekurzívne spočetné. Z (3) sú obe 1-prevoditeľné na $ A^\prime $. Z tranzitívnosti sú 1-prevoditeľné aj na $ B^\prime $ a zase z (3) sú obe $ B $ rekurzívne spočetné. Z Postovej vety potom vyplynie, že $ A $ je rekurzívne v $ B $, čo je len iné pomenovanie pre vzťah $ A \leq_T B $.
    • Nech $ A \leq_T B $. Z (1) vieme, že $ A^\prime $ je $ A $ rekurzívne spočetná. Podľa (4) platí, že $ A^\prime $ je tiež $ B $ rekurzívne spočetná. No a potom podľa (3) je $ A^\prime $ 1-prevoditeľná na $ B^\prime $, teda $ A' \leq_1 B' $.
  6. Triviálny dôsledok predchádzajúceho.

Uniformnosť skoku[editovat | editovat zdroj]

Veta: Existuje $ z_0 $ také, že pre každé $ A $ platí $ A^\prime = W_{z_0}^A $.

Dôkaz: Vytvoríme $ W_{z_0} = \{<\sigma, x, y> : <\sigma, x, y> \in W_{\rho(x)}\} $. Táto množina je regulárna, lebo $ \rho $ orezáva konflikty a konflikty môžu nastať len pri rovnakom $ x $. $ W_{\rho(z_0)} = W_{z_0} $. $ x \in A^\prime $ $ \iff $ $ \Phi_x(A)(x)\downarrow $ $ \iff $ $ \exists \sigma, y (<\sigma, x, y> \in W_{\rho(x)} \And (\sigma \leq A)) $ $ \iff $ $ \exists \sigma, y (<\sigma, x, y> \in W_{z_0} \And (\sigma \leq A)) $ $ \iff $ $ \exists \sigma, y (<\sigma, x, y> \in W_{\rho(z_0)} \And (\sigma \leq A)) $ $ \iff $ $ (\Phi_{z_0}(\sigma)(x) = y) \And (\sigma \leq A) $ $ \iff $ $ x \in W_{z_0}^A $.

Limitná vyčísliteľnosť[editovat | editovat zdroj]

Definícia: A je limitne vyčísliteľná práve keď existuje ORF $ f $ taká, že $ \forall x (A(x) = \lim_s f(x, s)) $.

Veta: $ A \leq_T \emptyset^\prime $ $ \iff $ $ A $ je limitne vyčísliteľná.

Dôkaz: $ A \leq_T \emptyset^\prime $ znamená, že $ \exists z (A(x) = \Phi_z(\emptyset^\prime)(x)) $. Vytvoríme si funkciu $ f(x, s) $: $ f(x,s) = \begin{cases} \Phi_{z,s}(\emptyset^\prime_s)(x),&\mbox{ak} \Phi_{z,s}(\emptyset^\prime_s)(x)\downarrow\\ s+1&\mbox{inak}\\ \end{cases} $

$ \emptyset^\prime_s $ je aproximácia $ \emptyset^\prime $ za $ s $ krokov. Keďže potrebujeme len konečný úsek na to, aby $ \Phi_z $ začalo konvergovať (a keďže $ A $ je totálna, tak to konvergovať začne), tak existuje $ s_1 $ krokov, v ktorých už počiatočný úsek $ \emptyset^\prime $ je hotový (všetko, čo patrí do tohto úseku už zastavilo - len nevieme, že to, čo tam nepatrí už nezastane, ale to nás netrápi). Tiež existuje $ s_2 $, kedy $ \Phi_z $ zastaví (keďže A je totálna). Pre $ s=\max(\{s_1, s_2\}) $ bude $ f $ vraciať prvú hodnotu a pre väčšie $ s $ sa táto hodnota nebude meniť, takže $ f $ bude mať správnu limitu (a to $ A $).

Ak $ A = \lim_s f(x, s) $. Pýtame sa: $ \exists j\geq 1 (f(x,s) \neq f(x, s+j))? $. To je rekurzívne v $ \emptyset^\prime $, takže aj negácia toho $ \forall j\geq 1 (f(x,s) = f(x, s+j)) $ je rekurzívna. Na tú pustím $ \mu_s $, čo je síce $ \emptyset^\prime $ ČRF, ale keďže $ A $ je totálne, tak je to $ \emptyset^\prime $ ORF, teda rekurzívne v $ \emptyset^\prime $.

Veta: $ f $ je ORF $ \implies $ $ \lim_s f(x, s) $ je $ \emptyset^\prime $ ČRF. $ \varphi $ je $ \emptyset^\prime $ČRF $ \implies $ $ \exists \mathrm{ ORF } f \forall x (\varphi(x) \simeq \lim_s f(x, s)) $

Dôkaz
Tato část je neúplná a potřebuje rozšířit. {{{1}}}
.

Relativizovaná veta (takmer rovnaké znenie): $ f $ je $ A $ORF $ \implies $ $ \lim_s f(x, s) $ je $ A^\prime $ ČRF. $ \varphi $ je $ A^\prime $ČRF $ \implies $ $ \exists A\mathrm{ ORF } f \forall x (\varphi(x) \simeq \lim_s f(x, s)) $

Aritmetická hierarchia[editovat | editovat zdroj]

$ \Sigma_n $ a $ \Pi_n $ sú prefixy kvantifikátorov pred nejakým ORP. V každom je $ n $ skupín, každá skupina je homogénna a $ \Sigma $ začína $ \exists $.

Obmedzené kvantifikátory ignorujeme ($ \forall x\leq j (Q(x)) $ môžeme nahradiť $ Q(1)\And Q(2) \And \ldots \And Q(j) $).

$ \Sigma_n $ predikát je ORP s $ \Sigma_n $ prefixom. Podobne pre $ \Pi_n $. Predikát nám definuje aj množinu. Takže máme $ \Sigma_n $ aj $ \Pi_n $ množiny.

Vetička o hierarchii:

  1. $ B \in \Sigma_n \iff \overline{B} \in \Pi_n $
  2. $ B \in \Sigma_n \implies B \in \Sigma_m \cap \Pi_m (\forall m > n) $
  3. $ A\leq_1 B \And B\in \Sigma_n \implies A \in \Sigma_n $

Dôkaz triviálny

Veta: Existuje univerzálny $ \Sigma_n $ aj $ \Pi_n $ predikát pre $ n \geq 1 $ (pozor, nie pre nulu).

Dôkaz: Indukciou. Pre $ \Sigma_1 $ vieme z prvého semestra, že existuje ($ \exists s T_1(e, x, s) $). Pre $ \Pi_1 $ je to $ \forall s \neg T_1(e, x, s) $.

Pre väčšie $ n $: Ak $ n $ je nepárne, tak $ \Sigma_n $ vyzerá ako $ \exists \forall \ldots \exists Q(x, y_1, \ldots, y_1) $. Odrežeme pred posledným kvantifikátorom, dostaneme $ \exists y_n Q(x, y_1, \ldots, y_n) $, to nahrádime univerzálnym predikátom a vrátime kvantifikátory späť: $ \exists y_1 \forall y_2 \ldots \exists y_n T_n(e, x, y_1, \ldots, y_n) $. Pre párne $ n $ podobne, len po odtrhnutí z $ \forall Q() $ vyrobím $ \exists \neg Q() $, nahradím univerzálnym $ \exists T_n() $, vrátim na $ \forall \neg T_n() $ a pridám kvantifikátory späť.

Pre $ \Pi_n $ rovnako.

Veta: $ \forall n \geq 1 \Sigma_n - \Pi_n \neq \emptyset $.

Dôkaz: Nech $ Univ^{(n)}(e, x) $ je univerzálny predikát pre $ \Sigma_n $. Vezmem $ P(x) = Univ^{(n)}(x.x) $. To, že je v $ \Sigma_n $ je vidieť a keby bol v $ \Pi_n $, tak jeho negácia by musela byť v $ \Sigma_n $. Tá má svoje číslo $ e_0 $ a je teda $ Univ^{(n)}(e_0, x) $. Teda $ \neg Univ^{(n)}(x, x) = Univ^{(n)}(e_0, x) $, čo pre $ x=e_0 $ dá spor. Takže $ P(x) $ je v $ \Sigma_n $ ale nie v $ \Pi_n $.

Veta o hierarchii:

  1. $ \forall n \geq 1: \emptyset^n $ je $ \Sigma_n $ úplná.
  2. A je rekurzívne spočetná v $ \emptyset^n \iff A \in \Sigma_{n+1} \forall n \geq 0 $
  3. $ A \leq_T \emptyset^n \iff A\in \Sigma_{n+1} \cap \Pi_{n+1} $

Dôkaz Časti 3 a 1 vyplývajú z časti 2.

$ 2 \implies 3 $: $ A $ je rekurzívne v $ \emptyset^n $ znamená, že $ A $ aj $ \overline{A} $ sú rekurzívne spočetné v $ \emptyset^n $, takže sú (podľa 2) v $ \Sigma_{n+1} $ a podľa vetičky ak $ \overline{A} \in \Sigma_{n+1} $, tak $ A \in \Pi_{n+1} $.

$ 2 \implies 1 $:

$ \emptyset^n $ je rekurzívne spočetná v $ \emptyset^{n-1} $ a preto z (2) patrí do $ \Sigma_n $.

Ak $ B \in \Sigma_n $, tak z (2) je $ B $ rekurzívna v $ \emptyset^{(n-1)} $ a z vlastností skoku $ B \leq_1 \emptyset^n $

2. Indukciou. Pre nulu je to zrejmé.

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:

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 (3) 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} $.

1-generickosť[editovat | editovat zdroj]

Def.: $ A $ je 1-generická ak $ (\forall e) (\exists \alpha_e \leq A) [(\Phi_e(\alpha_e)(e)\!\!\downarrow) \lor ((\forall \gamma \geq \alpha_e) \Phi_e(\gamma)(e)\!\!\uparrow)] $

Veta: Existuje 1-generická $ A \leq_T \emptyset' $

Dôkaz: Indukciou, prvý krok $ \alpha_0 = \emptyset $. Následne budeme generovať $ \alpha_0 \leq \alpha_1 \leq \alpha_2 \leq \cdots $, pre $ \Phi_1, \Phi_2, \cdots $

Máme $ \alpha_e \in 2^{\leq \omega} $ konečný retiazok, pre $ \Phi_e $. Hľadáme pre $ \Phi_{e+1} $, otázkou

$ (\exists \gamma \geq \alpha_e) (\Phi_{e+1}(\gamma)(e+1)\!\!\downarrow) $

čo je ekvivalentné s $ (\exists \gamma \geq \alpha_e) (\exists s) (\Phi_{e+1,s}(\gamma)(e+1)\!\!\downarrow) $, vnútri máme rekurzívny predikát, preto táto otázka je $ \Sigma_1^0 $, čo je $ \leq_T \emptyset' $

Halting problém nám odpovie. Ak odpovie áno, tak dosadíme prvý taký retiazok $ \alpha_{e+1} = \gamma $, za ním už všetky budú konvergovať. Ak nie, tak $ \alpha_{e+1} = \alpha_e $ a vieme, že forcuje silnú divergenciu.

Takto si vygenerujeme postupne celé $ A $, pomocou $ \emptyset' $. $ A = \cup_e \alpha_e $.


Rekurzívne stromy[editovat | editovat zdroj]

Rekurzívny strom je rekurzívna množina nula-jedničkových retiazkov taká, že ak do nej patrí $ \sigma $, tak do nej patrí aj každý prefix $ \sigma $.

$ f $ je nekonečná vetva v strome, pokiaľ $ \forall n (f \upharpoonright n \in T) $, kde $ f \upharpoonright n $ je obmedzenie $ f $ na prvých $ n $ položiek. a $ f $ je nekonečný binárny retiazok.

Königová lema: Binárny strom je nekonečný práve vtedy, keď obsahuje nekonečnú vetvu.

Dôkaz: Jedným smerom triviálny. Druhým smerom: buď ľavý alebo pravý podstrom koreňa je nekonečný, tak ideme do toho podstromu. Iterujeme a tým nájdeme nekonečnú vetvu.

Aké ťažké je zistiť, či je strom konečný? Máme otázku $ \exists h : \forall \alpha (|\alpha| = h \implies \alpha \notin T)? $ ($ h $ je hĺbka). To je existenčný kvantifikátor na rekurzívnu podmienku (všeobecný kvantifikátor je obmedzený), takže je to v $ \Sigma_1 $ a $ \emptyset^\prime $ nám na odpoveď stačí.

Úplnosti[editovat | editovat zdroj]

Veta: Tot = $ \{x: W_x = \mathbb{N}\} $ je $ \Pi_2 $ úplná.

Dôkaz: Tot = $ \{x: \forall y \exists s \varphi_{x, s}(y) \downarrow\} $. Tot je v $ \Pi_2 $

Nech B je v $ \Pi_2 $. $ x \in B \iff \forall y \exists s (Q(x, y, s)) $. $ Q $ je rekurzívny. Vyrobme $ \alpha(x, y) = \mu_s (Q(x, y, s) $. Podľa s-m-n vety $ \alpha(x, y) = \varphi_{g(x)}(y) $. $ x\in B $ $ \iff $ $ \forall y \exists s (Q(x, y, s)) $ $ \iff $ $ \forall y (\alpha(x, y)\downarrow) $ $ \iff $ $ \forall y (\varphi_{g(x)}(y)\downarrow) $ $ \iff $ $ g(x) \in \mathrm{Tot} $.

Veta: $ Inf = \{x: W_x \mbox{ je nekonečná}\} $ je $ \Pi_2 $ úplná.

Dôkaz: Inf = $ \{x: \forall s \exists j>s \exists t (j\in W_{x, t})\} $. Inf je v $ \Pi_2 $

Prevedieme Tot na Inf pomocou 1prevoditeľnosti. Vyrobíme si funkciu $ \alpha(x, j) $, ktorá robí to, že na čísla od $ 1 $ po $ j $ postupne spúšťa $ \varphi_x $ a zastane vtedy, keď všetky zastanú. Podľa s-m-n $ \alpha(x, j) = \varphi_{a(x)}(j) $.

$ x $ patrí do Tot práve keď $ \varphi_x(j) $ zastaví pre každé $ j $, takže $ \alpha(x, j) $ zastaví pre každé $ j $, takže $ \varphi_{a(x)} $ zastaví pre nekonečne veľa (všetky) $ j $, teda $ a(x) $ patrí do Inf.

Ak $ x $ nepatrí do Tot, tak $ \varphi_x(j) $ pre nejaké $ j $ nezastaví, takže $ \alpha(x, j) $ nezastaví pre všetky $ j^\prime $ väčšie ako $ j $, takže $ \varphi_{a(x)} $ zastaví len pre konečne veľa $ j $, takže $ a(x) $ nepatrí do Inf.

$ a(x) $ prevádza Tot na Inf. Keby sme potrebovali prevod opačným smerom, stačí povedať, že Tot je $ \Pi_2 $ úplná.

Tato část je neúplná a potřebuje rozšířit. {{{1}}}

Veta: Fin - doplnok Inf - je $ \Sigma_2 $ (pravdepodobne úplný)

Veta: Rek = $ \{x: W_x \mbox{ je rekurzívne}\} $ je $ \Sigma_3 $ úplná.