Státnice - Věty o rekurzi I2

Vety o rekurzi a jejich aplikace, Riceova veta (6×🎓)

Zážitky ze zkoušek

Věta o rekurzi a její aplikace (2013) - Zkoušejícího zajímalo znění, důkaz (preferoval ten přes s-m-n větu, ale spokojil se i s diagonalizačním), aplikace (Riceova věta a její znění, existence množin jako $ W_x=\{x\} $ s důkazem). Věty o rekurzi, Riceova věta (2009) - Napsal jsem základní větu, generování pevných bod a větu o rekurzi v závislosti na parametrech (vše samozřejmě s těmi jednoduchými důkazy). Napsal jsem Riceovu větu a její důkaz plynoucí ze základní věty o rekurzi. Ptal se mě odkud plynou důkazy, odpovědel jsem, že z Kleeneho věty a s.m.n. Pak se ještě ptal na trochu jinou verzi "Věty o programu co vypíše sám sebe", tam jsem trochu tápal, ale intuitivně jsem věděl (tu větu jsem znal, bohužel jsem ji neuvedl). vety o rekurzi (2009, Mlcek) - Ze zacatku jsme se bavili o tom, co jsem si pripravil, pak se to stocilo nekam, kde uz jsem se moc nechytal, ale prislo mi, ze mi spis chtel ukazat, jak se ty vety taky daj taky hezky a elegantne pouzit pro dukaz ruznejch kuriozit, takze to pak byla spis takova prednaska. Bohuzel jsem byl v takovym rozpolozeni, ze jsem si z ni moc neodnes :-) Kazdopadne docela pohoda. Vety o rekurzii a ich aplikacie (2009, Mlcek) - Napisal som 2 z 3 zakladnych viet. Ukazal som ako sa to pouzije pri dokaze Rice. Samozrejme nasledovala otazka na 3. z viet o rekurzii (resp. pevnom bode), co vlastne viedlo na program, ktory na kazdom vstupe vypise vlasny program. Aj ked som nebol 100%-tny vo vsetkom, tiez prijemne skusanie Vety o rekurzi a jejich dusledky (+ Riceova veta) (2009, Mlcek) Formuloval jsem a dokazal Vo pevnem bode, Vo generovani PB a Riceovu vetu (+ jeji dusledek). Dale to uz byl jen dialog jak se daji ty vety aplikovat (program co vypise svuj kod). Dalsi otazky jako co je to ze predikat Psi e x konverguje - rek. spoc. (halting problem), co je to mna K, Ko, jejich ekvivalence (jiz bez dukazu jen ustne). Vety o rekurzii (2008,Mlček) - pre mňa najťažšia otázka, našťastie som si fotograficky zapamätal dôkaz Riceovej vety a niektoré vety o rekurzii, takže ma nevyhodil

Věta ( VoR ):  ∀ ORF f ∃ (její pevný bod) n: φₙ ≃ φ_f(n)

💡 ∀ ORF transformacni funkci algoritmu f ∃ n tak že oba TS počítají stejnou fci (mají stejný algoritmus)

💡 n se říká pevný bod f

Dk (přes s-m-n větu)

Nechť e₁ je číslem funkce, pro kterou platí φₑ₁(e, x) ≃ φ_f(φₑ(e))(x), (tuto funkci bychom snadno odvodili pomocí univerzální ČRF).

Nechť b je Gödelovým číslem funkce s¹₁(e₁, e), podle s-m-n věty tedy platí, že :

φ_φb(e)(x) $ \stackrel{\text{dosadím s¹₁}}{≃} $ φ_{s₁¹(e₁, e)}(x) $ \stackrel{\text{obrácená sᵐₙ}}{≃} $ φₑ₁(e, x) $ \stackrel{\text{použijeme φₑ₁(e, x) ≃ φ_{f(φₑ(e))}(x)}}{≃} $ φ_f(φₑ(e))(x)

Protože φ_b je PRF (podle s-m-n), platí φ_b(b)↓ a také platí, že φ_φb(b) ≃ φ_f(φb(b)), φ_b(b) je tedy hledaným pevným bodem f.

Důsledky VoR

Věta ( 💡 ):  ∃ prostá PRF g, která ke GČ funkce f určí její pevný bod

Věta ( 💡 ):  ∀ ORF f má ∞ pevných bodů

Věta ( 💡 ): ∃ n ∈ ℕ, pro nějž:

1. Wₙ = {n}
2. φₙ ≃ λx[n]

Dk

1. Nechť e je Gödelovo číslo funkce definované jako φₑ⁽²⁾(x, y) ≃ μz[x = y] (💡 tedy φₑ⁽²⁾(x, y)↓ ⇔ x = y). Použijeme s-m-n větu a definujeme-li f(x) ≃ s₁¹(e, x), dostaneme, že φ_f(x) ≃ φ_s-1-1(e,x) ≃ φₑ(x, y) a tedy W_f(x) = {x}. Funkce f je ORF (podle s-m-n), a tak podle VoR: ∃ n: φₙ ≃ φ_f(n), a tak Wₙ = W_f(n) = {n}.
2. Podobně, nechť e je GČ funkce definované jako φₑ⁽²⁾(x, y) ≃ x. Pomocí s-m-n věty definujeme-li f(x) = s₁¹(e, x), dostaneme φ_f(x)(y) ≃ x a s použitím VoR nalezneme n, pro něž je φₙ(y) ≃ φ_f(n)(y) ≃ n.

Věta ( VoR s parametry ):  f(x,y) je ORF ⇒ ∃ prostá ORF n(y) taková, že φ_n(y) ≃ φ_f(n(y),y) ∀y ∈ N

Riceova v. - dk s VoR

Věta (Rice): 𝓒 třída ČRF, A_𝓒 = {e | φₑ ∈ C } je RM ⇔ 𝓒 = ∅ nebo 𝓒 obsahuje všechny ČRF

💡  A_𝓒 je mnozina indexů (Gödel.č.) funkci z třídy 𝓒

Dk (sporem)

předpokládejme že 𝓒 NEní ∅ a 𝓒 NEobsahuje všechny ČRF

předpokládejme sporem že A_𝓒 je rekurzivní

definujme si fci f:

f(x) = a    x ∉ A_𝓒

f(x) = b    x ∈ A_𝓒

f je ORF

a ∈ A_𝓒

b ∉ A_𝓒

n je pevný bod f a φₙ≃ φ_f(n)

φₙ ∈ 𝓒 ⇒ n ∈ A_𝓒 ⇒ f(n)=b ⇒ f(n)∉ A_𝓒 ⇒ φ_f(n) ∉ 𝓒

φₙ ∉ 𝓒 ⇒ n ∉ A_𝓒 ⇒ f(n)=a ⇒ f(n)∈ A_𝓒 ⇒ φ_f(n) ∈ 𝓒

⇒ spor

Dk (pomocí převoditelnosti)

předpokládejme že $ \cal C $ NEní ∅ a $ \cal C $ NEobsahuje všechny ČRF ukážeme sporem že $ K ≤_1 A_\cal C $ $ e_0 $ je GČ fce nedefinové pro žádný vstup a $ φ_{e0} ∈ \overline{\cal C} $ $ e_1 $ je GČ fce $ φ_{e1}∈C $ a $ φ_{e0}≄ φ_{e1} $ $ \varphi_{e_2}(x, y)\simeq\cases{ \varphi_{e_1}(y)&je-li $x\in K$\cr \uparrow } $ $ φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y) $ $ x∈K ⇒ φ_{f(x)}≃φ_{e1} ⇒ φ_{f(x)}(y) ∈ C ⇒ f(x) ∈ A_\cal C $ $ x∉K ⇒ φ_{f(x)}≃φ_{e0} ⇒ φ_{f(x)}(y) ∉ C ⇒ f(x)∉ A_\cal C $ tedy $ x ∈ K ⇔ f(x) ∈ Ac $

Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic