{{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 ${\phi }_{f(a)}(x)\simeq {\phi }_a(x)$ pro všechna $x$ (kde ${\phi }_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({\phi }_{f(s_1(z,z))}(x))\simeq {\Psi }_2(e,z,x)\simeq {\phi }_{s_1(e,z)}(x)$ Dosadíme $z=e$ a dostáváme hledané $a=s_1(e,e)$. Platí totiž ${\phi }_{f(s_1(e,e))}(x)\simeq {\Psi }_2(e,e,x)\simeq {\phi }_{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á ${\phi }_{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í:

:${\phi }_{f(g(j))}(x)\simeq {\phi }_{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í ${\phi }_{f(s_2(z,z,j))}(x)\simeq {\Psi }_3(e,z,j,x)\simeq {\phi }_{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í ${\phi }_a(x_1,\dots ,x_n)\simeq f(a,x_1,\dots ,x_n)$ (tj. $a$ je indexem funkce $\lambda x_1,\dots ,x_{n}f(a,x_1,\dots ,x_n)$).

Důkaz

$f(y,x_1,\dots ,x_n)\simeq {\Psi }_{n+1}(e,y,x_1,\dots ,x_n)\simeq {\phi }_{s_1(e,y)}(x_1,\dots ,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:{\phi }_{s_1(e,a)}\simeq {\phi }_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í:

:${\phi }_{f(g(y_1,\dots ,y_n),y_1,\dots ,y_n)}(x)\simeq {\phi }_{g(y_1,\dots ,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í: ${\phi }_{f(s_{n+1}(z,z,y_1,\dots ,y_n),y_1,\dots ,y_n)}(x)\simeq {\Psi }_{n+2}(e,z,y_1,\dots ,y_n,x)\simeq {\phi }_{s_{n+1}(e,z,y_1,\dots ,y_n)}(x)$. Zvolme $g(y_1,\dots ,y_n)=s_{n+1}(e,e,y_1,\dots ,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:{\phi }_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í:

:${\phi }_{u_0}={\phi }_{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}=\{{\phi }_e\}$, potom $A_{\mathcal{A}}=\{x:{\phi }_x={\phi }_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}}