{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke <Státnice> z <Státnice_-Informatika-Vyčíslitelnost> pro obory <Státnice-Informatika-_I3:Matematická_lingvistika> a <Státnice-Informatika-_I2:_Softwarové_systémy>, pocházející ze Strojilových skript, papírových zápisků A. Kazdy a zápisků z předmětu Vyčíslitelnost I ze <Studnice%20vědomostí> -- User:Tuetschek 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}}