{{TOC float}} {{Sources| *Tohle je poněkud obšírnější výcuc ke z pro obory a , pocházející ze [Strojilových skript](http://ladislav.strojil.cz/), papírových zápisků [A. Kazdy](http://atrey.karlin.mff.cuni.cz/%7Ealexak/) a zápisků z předmětu [Vyčíslitelnost I](Vyčíslitelnost%20I) ze -- 14:01, 17 Aug 2010 (CEST)* }} ## Věty o rekurzi ## #### Věta (O rekurzi, o pevném bodě, self-reference) #### Jestliže $ f\,\!$ je ORF{{ref|1}} jedné proměnné, potom existuje $ a\,\!$ takové, že $ \varphi_{f(a)}(x)\simeq \varphi_a(x)\,\!$ pro všechna $ x\,\!$ (kde $ \varphi_a(x)\,\!$ značí $ a\,\!$-tou funkci, tedy odpovídá $ \Psi_1(a,x)\,\!$). #### Důkaz #### Zjevně platí následující -- první výraz je ČRF, má tedy své číslo $ e\,\!$, druhá rovnost plyne ze S-m-n věty: :$ \lambda z,\!x (\varphi_{f(s_1(z,z))}(x)) \simeq \Psi_2(e,z,x) \simeq \varphi_{s_1(e,z)}(x) $ Dosadíme $ z=e\,\!$ a dostáváme hledané $ a=s_1(e,e)\,\!$. Platí totiž $ \varphi_{f(s_1(e,e))}(x) \simeq \Psi_2(e,e,x) \simeq \varphi_{s_1(e,e)}(x). $ #### Vlastnosti programů $a$ a $f(a)$ #### Funkce $ f\,\!$ zobrazuje program na program. Bod $ a\,\!$ je pevným bodem zobrazení $ f\,\!$. Jak vypadají programy $ a\,\!$ a $ f(a)\,\!$? Který z nich počítá déle? Uvidíme, že program $ a\,\!$ počítá déle než $ f(a)\,\!$. Co dělá program $ e\,\!$ na datech $ (z,x)\,\!$? Počítá $ \varphi_{f(s_1(z,z))}\,\!$, tj. vezme $ z\,\!$ a spočítá neprve $ s_1(z,z)\,\!$, potom $ f(s_1(z,z))\,\!$, který ale nemusí konvergovat. Jestliže $ f(s_1(z,z))\!\!\downarrow\,\!$, spustí se na vstup $ x\,\!$. Co dělá program $ a\,\!$? Program $ a\,\!$ vznikne jako $ s_1(e,e)\,\!$. Mějme na vstupu $ x\,\!$. Program $ a\,\!$ vezme $ e\,\!$ a přidá ho k $ x\,\!$ a spustí program $ e\,\!$ na $ (e,x)\,\!$. Co udělá program $ e\,\!$ na těchto datech? Spočítá $ s_1(e,e)\,\!$ (tedy spočítá $ a\,\!$), potom $ f(s_1(e,e))=f(a)\,\!$ a spustí program $ f(a)\,\!$ na $ x\,\!$. Program $ a\,\!$ tedy neprve spočítá $ a\,\!$, potom spočítá $ f(a)\,\!$ (pokud konverguje) a ten simuluje na vstupu $ x\,\!$. Program $ a\,\!$ je tedy složitější než $ f(a)\,\!$ a počítá déle. #### Poznámka z $\lambda$kalkulu #### V $\lambda$kalkule sa ekvivalentné tvrdenie ukazuje trošku jednoduchšie. Pre každý $\lambda$term $F$ (program $F$) existuje $\lambda$term $X$ taký, že $X = FX$ (program $F$ aplikovaný na $X$ sa rovná $X$). Dôkaz je nasledovný *Majme $F$, pre ktoré chceme nájsť jeho pevný bod X. *Nech $W = \lambda x.F(xx)$ (to je funkcia, ktorá $x$ priradí $F(xx)$). *$X = WW$ (to môžeme chápať ako program/funkciu $W$ aplikovaný na $W$) *$X = WW = (\lambda x.F(xx)) W = F(WW) = F(X)$ (tretia rovnosť je $\beta$pravidlo $\lambda$kalkulu. Ak si ale $(\lambda x.F(xx)) W$ predstavíme ako funkciu, ktorá $x$ priradí $F(xx)$ aplikovanú na $W$, rovnosť je (snáď) jasnejšia). #### Věta (O generování pevných bodů) #### Pro každou ORF{{ref|1}} $f$ existuje prostá rostoucí PRF $ g\,\!$ taková, že platí: :$\varphi_{f(g(j))}(x)\simeq\varphi_{g(j)}(x)\,\!$ Tedy $ g\,\!$ rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce $ f\,\!$. #### Důkaz #### Postupujeme stejně jako v důkazu předchozí věty, jen máme o proměnnou (parametr $ j\,\!$ funkce $ g\,\!$) navíc, tj. platí $ \varphi_{f(s_2(z,z,j))}(x)\simeq\Psi_3(e,z,j,x)\simeq\varphi_{s_2(e,z,j)}(x)\,\!$. Zvolme $ g(j)=s_2(e,e,j)\,\!$. #### Věta (O rekurzi pro více proměnných) #### Nechť $ f\,\!$ je ČRF $ n+1\,\!$ proměnných. Potom existuje číslo $ a\,\!$ takové, že platí $ \varphi_a(x_1,\ldots,x_n)\simeq f(a,x_1,\ldots,x_n)\,\!$ (tj. $ a\,\!$ je indexem funkce $ \lambda{x_1,\ldots,x_n} f(a,x_1,\ldots,x_n)\,\!$). #### Důkaz #### $f(y,x_1,\ldots,x_n)\simeq \Psi_{n+1}(e,y,x_1,\ldots,x_n)\simeq \varphi_{s_1(e,y)}(x_1,\ldots,x_n)$ Následně aplikujeme větu o rekurzi na $ s_1(e,y)\,\!$ v proměnné $ y\,\!$ a dostáváme hledané $ a\,\!$ (podle VR platí: $ \exists a: \varphi_{s_1(e,a)}\simeq \varphi_{a}\,\!$). #### Věta (O rekurzi v závislosti na parametrech) #### Jestliže $ f\,\!$ je ČRF $ n+1\,\!$ proměnných, potom existuje PRF $ g\,\!$ o $ n\,\!$ proměnných taková, že platí: :$\varphi_{f(g(y_1,\ldots,y_n),y_1,\ldots,y_n)}(x)\simeq \varphi_{g(y_1,\ldots,y_n)}(x)\,\!$ #### Důkaz #### Pro $ n=0\,\!$ je to totéž jako verze bez parametrů. $ g\,\!$ nachází pevné body v závislosti na parametrech. Podobně jako v předchozích větách platí: $ \varphi_{f(s_{n+1}(z,z,y_1,\ldots,y_n),y_1,\ldots,y_n)}(x) \simeq \Psi_{n+2}(e,z,y_1,\ldots,y_n,x) \simeq \varphi_{s_{n+1}(e,z,y_1,\ldots,y_n)}(x)\,\!$. Zvolme $ g(y_1,\ldots,y_n)=s_{n+1}(e,e,y_1,\ldots,y_n)\,\!$. ## Riceova věta ## #### Věta (Rice) #### Jestliže $ \mathcal{A}\,\!$ je třída ČRF (jedné proměnné), která je netriviální (nejsou to všechny funkce a není prázdná), potom indexová množina $ A_{\mathcal{A}} = \{ x : \varphi_x \in \mathcal{A}\}\,\!$ (indexy programů, které vyčíslují funkce z $\mathcal{A}$) je nerekurzivní. #### Důkaz #### Sporem. Nechť $ A_{\mathcal{A}}\,\!$ je rekurzivní. Potom lze vytvořit ORF $ f\,\!$ takovou, že všechny prvky z $ A_{\mathcal{A}}\,\!$ zobrazí na nějaký prvek $ b \notin A_{\mathcal{A}}\,\!$ a všechny prvky mimo $ A_{\mathcal{A}}\,\!$ zobrazí na nějaký prvek $ a \in A_{\mathcal{A}}\,\!$. Podle věty o rekurzi existuje pevný bod $ f\,\!$ -- $ u_0\,\!$, tedy platí: :$ \varphi_{u_0}=\varphi_{f(u_0)} \,\!$ Takže: :$ u_0 \in A_{\mathcal{A}} \Rightarrow f(u_0)=b \notin A_{\mathcal{A}}$ :$u_0 \notin A_{\mathcal{A}} \Rightarrow f(u_0)=a \in A_{\mathcal{A}} $ To je ovšem spor, protože $ u_0\,\!$ a $ f(u_0)\,\!$ jsou indexy stejné funkce, a tedy buď obě čísla v $ A_{\mathcal{A}}\,\!$ leží, nebo obě neleží. #### Důsledky #### Pozor, nejedná se o třídu programů, ale třídu funkcí. Tedy i pro jednoprvkovou $ \mathcal{A}\,\!$ bude $ A_{\mathcal A}\,\!$ nekonečná a nerekurzivní (každá funkce je vyčíslovaná nekonečně mnoha programy a rozhodnout o jejich ekvivalenci nelze efektivně). Proto platí: * Nechť $ \mathcal{A}=\{\varphi_e\}\,\!$, potom $ A_{\mathcal{A}}=\{x:\varphi_x=\varphi_e\}\,\!$ je nerekurzivní. * Rozhodnout o rovnosti funkcí vyčíslovaných dvěma programy nelze algoritmicky. ---- {{note|1|Věta platí i pro ČRF, s využitím toho, že ani jedna ze stran $\simeq$ nemusí dávat smysl, aby výraz platil.}} {{Statnice I3}}