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 ORF jedné proměnné. Pak existuje číslo $ a $ (tzv. pevný bod), že $ \forall x: \varphi_{f(a)}(x) \simeq \varphi_a(x) $."

(Otázka : Co když f má prázdný definiční obor? Předpokládá se, že má neprázdný? Odpověď: ORF je definovaná jako totální ČRF, definiční obor je celé N)

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) $.

• • • Nemohl by někdo napsat, proč $ \varphi_{f(s_1(z,z))}(x) $ je ČRF dvou promenných? Chápu, že pro zjištění hodnoty funkce jsou třeba dva vstupy, ale v závorce je jen jedno číslo ... Rovnici výše také příliš nerozumím, autor si s proměnnými hází jak chce. Prostě ať to někdo napíše pořádně, já ten důkaz stále nevidím :( ODPOVED: je to funkcia dvoch premennych, lebo musis tam najprv stale dosadit "z", aby si dostal funkciu jednej premennej (premennej x). Pokial nedosadis z a x, tak nevies dostat vysledok funkcie.

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) $.

Důkaz 2 (od Ivana)

Z s-m-n věty víme, že existují PRF $ s_1, s_2, s_3 ... $ a jsou všude definované, f je také všude definovaná. Pro každé z můžeme mluvit o f(s1(z,z))-té funkci.

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

Ekvivalence * : tvrdíme, že existuje e-tá funkce 2 proměnných, ekvivalentní funkci nalevo. Tato e-tá funkce dostane z, x a může např. vyčíslit f(s1(z,z)) a simulovat běh f(s1(z,z))-té funkce nad x.

Výraz výše platí pro každé z, tedy i pro z = e:

$ \varphi_{f(s_1(e,e))}(x) \simeq \psi_1(f(s_1(e,e)),x) \simeq^{*} \psi_2(e,e,x) \simeq^{smn} \psi_1(s_1(e,e),x) \simeq \varphi_{s_1(e,e)}(x) $ ... Námi hledané a je $ s_1(e,e) $.

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) $."

(Otázka: Odkud se ve větě vzalo j? Je to volná proměnná? Platí to pro všechna j přirozená? Myslím, že j je Godelovo číslo f. ODPOVED: no to je predsa ta pointa, j moze byt hocijake cislo z N, lebo je to argument funkcie g (ktora je PRF = totalna). Ta veta hovori, ze existuje funkcia g, ktorej rng(g) je mnozina pevnych bodov funkcie f. ktora generuje nekonecno pevnych bodov. To znamena, )

Předchozí věta dokazovala existenci jednoho pevného bodu, ale pomocí g si můžeme pro libovolnou funkci vygenerovat nějaký pevný bod.

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) $.

Důkaz(alternativní)

Důkaz vychází z důkazu VR1(od Ivana). Hledaný pevný bod je $ s_1(e,e) $. Funkce s_1 je zkonstruovaná v odkazovaném důkazu (nezávisí na f, a navíc je PRF). Parametr e ale musíme spočítat, kdybychom měli nějakou totální funkci v(j), co e vyčíslí pro libovolnou funkci f, tak $ s_1(e,e) $ spočítáme.

Funkci v(j) definujeme: $ \varphi_{v(j)} \simeq \varphi_{j} \circ s1(z,z) $. Funkce v(j) vrátí kód funkce co skládá funkci f s s1 (přečíst 2x, inception). Funkce v(j) existuje a je PRF, protože ji dostaneme z s-m-n věty na složení f a s1.

Proč takhle definované v(j) funguje je celkem jasné, stačí to rozepsat: $ \varphi_{v(j)} \simeq \varphi_{j} \circ s1(z,z) \simeq \varphi_{f(s1(z,z))} $ což je přesně ta funkce, co má kód e v odkazovaném důkazu. Funkce g tedy je $ g(j)=s_1(v(j),v(j)) $.

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 indexů těchto funkcí (stejná funkce může mít více indexů, více způsobů odvození, paralela: stejný jazyk může přijímat několik různých TS). 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.

---

Náhled získaný od Martina Mareše (06/2014)

Riceova věta říká, že každa netriviální vlastnost rekurzivně spočetných jazyků je nerozhodnutelná.

Neboli: Vezmi si jakoukoli sémantickou vlastnost funkce napsané v nějakém běžném programovacím jazyce (např. vlastnost:funkce je rostoucí, nebo: její program neobsahuje konkrétní chybu). Pokud je to vlastnost rozumná (taková, kterou aspoň jedna funkce má a jedna funkce nemá), pak není možné obecně tuto vlastnost jen ze zdrojáku otestovat.

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í.