TIN064 Věty o rekurzi

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

Věty o rekurzi (zkracujeme na VR) jsou klíčové pro teorii vyčíslitelnosti, a možná i proto mají různé krycí názvy a existuje jich několik (my si uvedeme čtyři verze). Místo věta o rekurzi se říká též věta o self-referenci či věta o pevném bodě.

VR1 - základní věta o rekurzi

"Nechť f je ČRF jedné proměnné. Pak existuje číslo $ a $ (tzv. pevný bod), že $ \forall x: \varphi_{f(a)}(x) \simeq \varphi_a(x) $."

Tato věta říká, že pro každou totální f existuje program s indexem $ a $, který je ekvivalentní (ve smyslu $ \simeq $) programu s indexem $ f(a) $. Jinými slovy programy s indexy $ a $ a $ f(a) $ vyčíslují tutéž funkci. (Pevný bod v této větě tedy neznamená, že $ f(a)=a $. To by ostatně např. pro funkci následníka ani nebylo možné.)

Důkaz

Důkaz je celkem jednoduchý, zvlášť když člověk dostane vnuknutí (hint), že číslo $ a $ bude ve tvaru $ a=s_1(z,z) $ pro nějaké $ z $. Funkce $ s_1 $ je PRF, takže $ \varphi_{f(s_1(z,z))}(x) $ je ČRF dvou proměnných $ z $ a $ x $ — což bychom v lambda kalkulu zapsali λxz. φ_f(s1(z,z))(x) — a existuje její index $ e $ takový, že:

$ \varphi_{f(s_1(z,z))}(x) \simeq \psi_2(e,z,x) \simeq \psi_1(s_1(e,z),x) \simeq \varphi_{s_1(e,z)}(x) $.

V předchozí (podmíněné) rovnosti jsme použili s-m-n větu. Pokud nyní za $ z $ dosadíme index $ e $, máme $ a=s_1(e,e) $, čímž dostaneme požadovanou rovnost:

$ \varphi_{f(a)}(x) \simeq \varphi_{f(s_1(e,e))}(x) \simeq \psi_2(e,e,x) \simeq \psi_1(s_1(e,e),x) \simeq \varphi_a(x) $.

Průběh výpočtu

Funkce $ f $ zobrazuje program na program. Bod $ a $ je pevným bodem $ f $ (pevný bod chápeme v "relaci nad programy", tzn. to že $ a $ je pevným bodem $ f $ znamená, že programy $ a $ a $ f(a) $ dělají to samé, ne to že číslo $ a $ se rovná číslu $ f(a) $ ). Jak $ a $ a $ f(a) $ vypadají? A který počítá déle?

• Program $ a $ vznikne jako $ s_1(e,e) $. Nechť na vstupu dostane $ x $. Program $ a $ vezme $ e $, přidá ho k $ x $ a spustí program $ e $ na vstupu $ (e,x) $. Co udělá program $ e $ na těchto datech? Spočítá $ s_1(e,e) $ (tedy $ a $), potom $ f(s_1(e,e)) $ (tedy $ f(a) $) a výsledek použije jako program, který spustí s parametrem $ x $.
• Oproti tomu $ f(a) $ dělá jen to poslední a tedy je rychlejší.

VR2 - Věta o generování pevných bodů

"Nechť f je ČRF jedné proměnné. Pak existuje rostoucí PRF g jedné proměnné, že $ \forall x: \varphi_{f(g(j))}(x) \simeq \varphi_{g(j)}(x) $."

Předchozí věta dokazovala existenci jednoho pevného bodu, ale pomocí g si můžeme takových bodů vygenerovat nekonečně mnoho.

Důkaz

Důkaz je obdobný jako u VR1, pouze jako hint použijeme $ g(j)=s_2(z,z,j) $.

$ \varphi_{f(s_2(z,z,j))}(x) \simeq \psi_3(e,z,j,x) \simeq \psi_1(s_2(e,z,j),x) \simeq \varphi_{s_2(e,z,j)}(x) $.

Pro $ z:=e $ máme $ g(j)=s_2(e,e,j) $ a tedy $ \varphi_{f(g(j))}(x) \simeq \varphi_{f(s_2(e,e,j))}(x) \simeq \psi_3(e,e,j,x) \simeq \psi_1(s_2(e,e,j),x) \simeq \varphi_{g(j)}(x) $.

VR3 - pro více proměnných

"Nechť f je ČRF n+1 proměnných. Pak existuje číslo a, že $ \forall x_1,...,x_n: \varphi_a(x_1,...,x_n) \simeq f(a,x_1,...,x_n) $."

Důkaz

Pro jednu proměnnou: Máme $ f(y,x) \simeq \Psi_{2}(e,y,x) \simeq \Psi_{1}(s_1(e,y),x) \simeq \varphi_{s_1(e,y)}(x) $ pro nějaké $ e $ (číslo funkce $ f $). Zadefinujme novou funkci $ g $ jako: $ g(y) = s_1(e,y) \, $. Pro $ g $ najdeme dle VR1 pevný bod $ a $. Po dosazení platí.

Pro více proměnných: $ f(y,x_1,...,x_n) \simeq \Psi_{n+1}(e,y,x_1,...,x_n) \simeq \Psi_{n}(s_1(e,y),x_1,...,x_n) \simeq \varphi_{s_1(e,y)}(x_1,...,x_n) $

Kde funkce $ s_1(e,y) $ (jedné proměnné $ y $) má podle VR1 pevný bod $ a $, takže $ \varphi_{s_1(e,a)} \simeq \varphi_{a} $. Opět stačí dosadit $ a $ za $ y $.

Důsledek: quine v ČRF je snadný

Quine je program, který vypíše svůj vlastní (zdrojový) kód, aniž by používal vstupní parametry (to proto, aby program nemohl získat svůj zdroják ze vstupu). Ve světě ČRF jsme zatím nezavedli nulární funkce (bez vstupních parametrů), takže bychom mohli quine definovat jako index e takový, že $ \forall x: \varphi_e(x)=e $ (vstupní parametr je sice jeden, ale vůbec na něm nezáleží). Existence takového quine indexu $ a $ plyne z předchozí věty, pokud za f dosadíme funkci $ f(a,x)=a $.

VR4 - v závislosti na parametrech

"Nechť f je ČRF n+1 proměnných. Pak existuje PRF g n proměnných, že $ \forall x, y_1,...,y_n: \varphi_{f(g(y_1,...,y_n),y_1,...,y_n)}(x) \simeq \varphi_{g(y_1,...,y_n)}(x) $."

Znění této věty je dobré si zapamatovat, protože ji ještě častokrát použijeme. Poněkud stručněji bychom ji mohli zapsat jako: $ \forall f \in \check{C}RF_{n+1} \, \exists g \in PRF_n: \forall x \in \mathbb{N}, \forall \vec y \in \mathbb{N}^n: \varphi_{f(g(\vec y), \vec y)}(x) \simeq \varphi_{g(\vec y)}(x) $.

Note: Všimněte si, že je to prakticky ten samý princip jako u VR2, jen místo $ j $ máme $ \vec y $, který je ještě navíc jako parametr $ f $.

Důkaz

Jako hint použijeme $ g(\vec y)=s_{n+1}(z,z,\vec y) $ a zopakujeme osvědčený postup: $ \varphi_{f(s_{n+1}(z,z,\vec y),\vec y)}(x) \simeq \psi_{n+2}(e,z,\vec y,x) \simeq \psi_1(s_{n+1}(e,z,\vec y),x) \simeq \varphi_{s_{n+1}(e,z,\vec y)}(x) $

$ g(\vec y):=s_{n+1}(e,e,\vec y) $.

Riceova věta

"Nechť $ \mathcal{A} $ je třída ČR funkcí jedné proměnné, která je netriviální (tzn., že je neprázdná, ale nejsou v ní všechny ČRF jedné proměnné), pak množina $ B=\{x| \varphi_x \in \mathcal{A}\} $ není rekurzivní."

Jinak zapsáno: $ \forall \mathcal{A} (\mathcal{A} \subseteq \check{C}RF_1 \And \mathcal{A} \ne \empty \And \mathcal{A} \ne \check{C}RF_1) \Rightarrow (B=\{x| \varphi_x \in \mathcal{A}\} \notin RM) $

• $ \mathcal{A} $ je množina funkcí, kdežto $ B $ je množina programů (které vyčíslují nějakou funkci z $ \mathcal{A} $). I pokud tedy dáme do $ \mathcal{A} $ jen jednu funkci, tak množina $ B $ bude nekonečná, protože programů (tím se myslí indexů těchto programů), které vyčíslují tuto funkci, je nekonečně mnoho.

Důkaz

Důkaz provedeme sporem a využijeme v něm větu o rekurzi. Mějme tedy rekurzivní množinu $ B $. Jelikož $ \mathcal{A} $ je netriviální, nutně musí existovat nějaký bod $ b \in B $ a nějaký bod $ c \notin B $. Sestrojíme funkci f tak, že

$ f(x)=\begin{cases} b & \mbox{pokud } x \notin B \\ c & \mbox{pokud } x \in B \end{cases} $

Ano, použili jsme osvědčenou vyčíslitelnickou fintu a $ f $ jsme sestrojili naschvál "obráceně". Všechny prvky z $ B $ se zobrazí mimo $ B $ a všechny prvky z doplňku $ B $ se zobrazí dovnitř $ B $. Díky předpokladu, že $ B $ je rekurzivní, můžeme tvrdit, že $ f $ je ORF (charakteristická funkce $ B $ vrací 1 či 0, naše $ f $ vrací místo jedničky $ c $ a místo nuly $ b $).

Teď přichází ta správná chvíle pro větu o rekurzi (a to v základní verzi VR1). Funkce $ f $ je ČRF, tedy existuje nějaký její pevný bod $ e $ takový, že

$ \forall x: \varphi_{f(e)}(x) \simeq \varphi_e(x) $.

Předpokládejme nyní, že $ e \in B $. Pak $ f(e)=c \notin B $. Máme tedy $ \varphi_e \in \mathcal{A} \And \varphi_{f(e)} \notin \mathcal{A} $. Jenže věta o rekurzi říká, že programy s indexy $ e $ a $ f(e) $ jsou ekvivalentní, čili vyčíslují stejnou funkci a ta buď náleží do $ \mathcal{A} $, nebo ne, ale musíme dostat stejnou odpověď pro $ \varphi_e $ i pro $ \varphi_{f(e)} $. Dostali jsme spor.

Pokud $ e \notin B $, dostaneme spor obdobným způsobem: $ e \notin B \Rightarrow f(e)=b \in B $.

Sporem jsme tudíž dokázali, že množina $ B $ nemohla být rekurzivní. $ \Box $

Důsledek: ekvivalence programů

"Ekvivalenci programů nelze rozhodnout algoritmicky."

Mějme nějaký program s indexem e. Zvolíme $ \mathcal{A}=\{\varphi_e\} $, čili $ B=\{x|\varphi_x = \varphi_e\} $ je množina všech programů (jejich indexů), které jsou ekvivalentní s programem e. Dle Riceovy věty je množina B nerekurzivní.