Státnice - Věty o rekurzi

Tohle je poněkud obšírnější výcuc ke státnicovým okruhům z vyčíslitelnosti pro obory Matematická lingvistika a 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 -- 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¹ 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¹ $ 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.

---

* ^ ad 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.

Státnice -- Matematická lingvistika
Složitost a vyčíslitelnost -- Tvorba algoritmů, Odhady složitosti, NP-úplnost, Aproximační algoritmy, Vyčíslitelné funkce, Rekurzivní množiny, Nerozhodnutelné problémy, Věty o rekurzi.
Datové struktury -- Stromy, Hašování, Dynamizace, Vnější paměť, Třídění.
Formální popis jazyka -- Závislostní syntax, Frázové gramatiky, Obecná lingvistika, FGD, Formální sémantika
Statistické metody -- Korpusy, Strojové učení, Stochastické metody, Experimenty
Automatické zpracování jazyka -- Analýza jazyka, Generování jazyka, Analýza a syntéza řeči, Extrakce informací, Strojový překlad