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

{{Zkazky|

• 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

}}

{{theorem | ∀ ORF f ∃ (její pevný bod) n: φₙ ≃ φ_f(n)

| VoR }}

:: 💡 ∀ 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¹₁}}{\simeq }$ φ_s₁¹_{(''e₁, e'')}(x) $\stackrel{\text{obraˊcenaˊ sᵐₙ}}{\simeq }$ φₑ₁*(e, x)*

ParseError: KaTeX parse error: Expected 'EOF', got '_' at position 40: …e φₑ₁(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

{{theorem

| ∃ prostá PRF g, která ke GČ funkce f určí její pevný bod | 💡

}} {{theorem

| ∀ ORF f má ∞ pevných bodů | 💡

}} {{theorem

|∃ n ∈ ℕ, pro nějž: # Wₙ = {n}

1. φₙ ≃ λ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.

{{theorem

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

}}

Riceova v. - dk s VoR

{{theorem |1= 𝓒 třída ČRF, A_𝓒 = {e | φₑ ∈ C } je RM ⇔ 𝓒 = ∅ nebo 𝓒 obsahuje všechny ČRF

|2= Rice }}

💡  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

{{collapse|1=Dk (pomocí převoditelnosti)|2=

:: předpokládejme že $\mathcal{C}$ NEní ∅ a $\mathcal{C}$ NEobsahuje všechny ČRF :: ukážeme sporem že

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 9: K ≤_1 A_\̲c̲a̲l̲ ̲C

ParseError: KaTeX parse error: Undefined control sequence: \cases at position 26: …_2}(x, y)\simeq\̲c̲a̲s̲e̲s̲{ \varphi_{e_1}…

ParseError: KaTeX parse error: Undefined control sequence: \cr at position 1: \̲c̲r̲ ̲\uparrow }

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 52: …∈ C ⇒ f(x) ∈ A_\̲c̲a̲l̲ ̲C

ParseError: KaTeX parse error: Got function '\cal' with no arguments as subscript at position 53: …∉ C ⇒ f(x)∉ A_\̲c̲a̲l̲ ̲C

}}

{{Statnice I2}}