{{TIN064 Skripta}} 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 (tzv. pevný bod), že ."
(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 , který je ekvivalentní (ve smyslu ) programu s indexem . Jinými slovy programy s indexy a vyčíslují tutéž funkci. (Pevný bod v této větě tedy neznamená, že . 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 bude ve tvaru pro nějaké . Funkce je PRF, takže je ČRF dvou proměnných a — což bychom v lambda kalkulu zapsali λxz. φ<sub>f(s<sub>1</sub>(z,z))</sub>(x) — a existuje její index takový, že:
.
Nemohl by někdo napsat, proč 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 dosadíme index , máme , čímž dostaneme požadovanou rovnost:
.
Důkaz 2 (od Ivana)
Z s-m-n věty víme, že existují PRF 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.
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:
... Námi hledané a je .
Průběh výpočtu
Funkce zobrazuje program na program. Bod je pevným bodem (pevný bod chápeme v "relaci nad programy", tzn. to že je pevným bodem znamená, že programy a dělají to samé, ne to že číslo se rovná číslu ). Jak a vypadají? A který počítá déle?
Program vznikne jako . Nechť na vstupu dostane . Program vezme , přidá ho k a spustí program na vstupu . Co udělá program na těchto datech? Spočítá (tedy ), potom (tedy ) a výsledek použije jako program, který spustí s parametrem .
Oproti tomu 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 ."
(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 .
.
Pro máme a tedy .
Důkaz(alternativní)
Důkaz vychází z důkazu VR1(od Ivana). Hledaný pevný bod je . 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 spočítáme.
Funkci v(j) definujeme: . 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: což je přesně ta funkce, co má kód e v odkazovaném důkazu. Funkce g tedy je .
VR3 - pro více proměnných
"Nechť f je ČRF n+1 proměnných. Pak existuje číslo a, že
."**
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)efgg(y) = s_1(e,y) ,ga$. 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 (jedné proměnné ) má podle VR1 pevný bod , takže . Opět stačí dosadit za .
Důsledek: quine v ČRF je snadný
wen:quine%20%28computing%29 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 (vstupní parametr je sice jeden, ale vůbec na něm nezáleží). Existence takového quine indexu plyne z předchozí věty, pokud za f dosadíme funkci .
VR4 - v závislosti na parametrech
"Nechť f je ČRF n+1 proměnných. Pak existuje PRF g n proměnných, že ."
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:
.
Note: Všimněte si, že je to prakticky ten samý princip jako u VR2, jen místo máme , který je ještě navíc jako parametr .
Důkaz
Jako hint použijeme a zopakujeme osvědčený postup:
.
Riceova věta
"Nechť 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 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)$
je množina funkcí, kdežto 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 jen jednu funkci, tak množina 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 . Jelikož je netriviální, nutně musí existovat nějaký bod a nějaký bod . 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 jsme sestrojili naschvál "obráceně". Všechny prvky z se zobrazí mimo a všechny prvky z doplňku se zobrazí dovnitř . Díky předpokladu, že je rekurzivní, můžeme tvrdit, že je ORF (charakteristická funkce vrací 1 či 0, naše vrací místo jedničky a místo nuly ).
Teď přichází ta správná chvíle pro větu o rekurzi (a to v základní verzi <#VR1%20-%20základní%20věta%20o%20rekurzi>). Funkce je ČRF, tedy existuje nějaký její pevný bod takový, že
.
Předpokládejme nyní, že . Pak . Máme tedy . Jenže věta o rekurzi říká, že programy s indexy a jsou ekvivalentní, čili vyčíslují stejnou funkci a ta buď náleží do , nebo ne, ale musíme dostat stejnou odpověď pro i pro . Dostali jsme spor.
Pokud , dostaneme spor obdobným způsobem:
.
Sporem jsme tudíž dokázali, že množina nemohla být rekurzivní.
Důsledek: ekvivalence programů
"Ekvivalenci programů nelze rozhodnout algoritmicky."
Mějme nějaký program s indexem e. Zvolíme , čili je množina všech programů (jejich indexů), které jsou ekvivalentní s programem e. Dle Riceovy věty je množina B nerekurzivní.