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 <math>W_x=\{x\}</math> 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 :

φφ<sub>b</sub>(''e'')(x) <math>\stackrel{\text{dosadím s¹₁}}{≃}</math> φs₁¹(''e₁, e'')(x) <math>\stackrel{\text{obrácená sᵐₙ}}{≃}</math> φₑ₁(e, x) <math>\stackrel{\text{použijeme φₑ₁(e, x) ≃ φ_{f(φₑ(e))}(x)}}{≃}</math> φf(''φₑ''(''e''))(x)

Protože φb je PRF (podle s-m-n), platí φb(b) a také platí, že φφ<sub>b</sub>(''b'') ≃ φf(''φ<sub>b(b))</sub>, φ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 Wf(x) = {x}. Funkce f je ORF (podle s-m-n), a tak podle VoR: ∃ n: φₙ ≃ φf(n), a tak Wₙ = Wf(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 <math>\cal C</math> NEní ∅ a <math>\cal C</math> NEobsahuje všechny ČRF

ukážeme sporem že <math>K ≤_1 A_\cal C</math>

<math>e_0</math> je GČ fce nedefinové pro žádný vstup a <math>φ_{e0} ∈ \overline{\cal C}</math>

<math>e_1</math> je GČ fce <math>φ_{e1}∈C</math> a <math>φ_{e0}≄ φ_{e1}</math>

<math>\varphi_{e_2}(x, y)\simeq\cases{ \varphi_{e_1}(y)&je-li $x\in K$\cr \uparrow }</math>

<math>φ_{e2}(x , y) ≃ φ_{s^1_1}(e, x) (y) ≃ φ_{f(x)}(y)</math>

<math>x∈K ⇒ φ_{f(x)}≃φ_{e1} ⇒ φ_{f(x)}(y) ∈ C ⇒ f(x) ∈ A_\cal C</math>

<math>x∉K ⇒ φ_{f(x)}≃φ_{e0} ⇒ φ_{f(x)}(y) ∉ C ⇒ f(x)∉ A_\cal C</math>

tedy <math>x ∈ K ⇔ f(x) ∈ Ac</math>

}}

{{Statnice I2}}