{{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 aa (tzv. pevný bod), že x:φf(a)(x)φa(x)\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 aa, který je ekvivalentní (ve smyslu \simeq) programu s indexem f(a)f(a). Jinými slovy programy s indexy aa a f(a)f(a) vyčíslují tutéž funkci. (Pevný bod v této větě tedy neznamená, že f(a)=af(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 aa bude ve tvaru a=s1(z,z)a=s_1(z,z) pro nějaké zz. Funkce s1s_1 je PRF, takže φf(s1(z,z))(x)\varphi_{f(s_1(z,z))}(x) je ČRF dvou proměnných zz a xx — což bychom v lambda kalkulu zapsali λxz. φ<sub>f(s<sub>1</sub>(z,z))</sub>(x) — a existuje její index ee takový, že:

φf(s1(z,z))(x)ψ2(e,z,x)ψ1(s1(e,z),x)φs1(e,z)(x)\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č φf(s1(z,z))(x)\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 zz dosadíme index ee, máme a=s1(e,e)a=s_1(e,e), čímž dostaneme požadovanou rovnost:

φf(a)(x)φf(s1(e,e))(x)ψ2(e,e,x)ψ1(s1(e,e),x)φa(x)\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 s1,s2,s3...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.

φf(s1(z,z))(x)ψ1(f(s1(z,z)),x)ψ2(e,z,x)smnψ1(s1(e,z),x)φs1(e,z)(x)\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:

φf(s1(e,e))(x)ψ1(f(s1(e,e)),x)ψ2(e,e,x)smnψ1(s1(e,e),x)φs1(e,e)(x)\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 s1(e,e)s_1(e,e).

Průběh výpočtu

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

  • Program aa vznikne jako s1(e,e)s_1(e,e). Nechť na vstupu dostane xx. Program aa vezme ee, přidá ho k xx a spustí program ee na vstupu (e,x)(e,x). Co udělá program ee na těchto datech? Spočítá s1(e,e)s_1(e,e) (tedy aa), potom f(s1(e,e))f(s_1(e,e)) (tedy f(a)f(a)) a výsledek použije jako program, který spustí s parametrem xx.

  • Oproti tomu f(a)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 x:φf(g(j))(x)φg(j)(x)\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)=s2(z,z,j)g(j)=s_2(z,z,j).

φf(s2(z,z,j))(x)ψ3(e,z,j,x)ψ1(s2(e,z,j),x)φs2(e,z,j)(x)\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:=ez:=e máme g(j)=s2(e,e,j)g(j)=s_2(e,e,j) a tedy φf(g(j))(x)φf(s2(e,e,j))(x)ψ3(e,e,j,x)ψ1(s2(e,e,j),x)φg(j)(x)\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 s1(e,e)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 s1(e,e)s_1(e,e) spočítáme.

Funkci v(j) definujeme: φv(j)φjs1(z,z)\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: φv(j)φjs1(z,z)φf(s1(z,z))\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)=s1(v(j),v(j))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

x1,...,xn:φa(x1,...,xn)f(a,x1,...,xn)\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)proneˇjakeˊ pro nějaké e(cˇıˊslofunkce (číslo funkce f).Zadefinujmenovoufunkci). Zadefinujme novou funkci gjako: jako: g(y) = s_1(e,y) ,.Pro. Pro gnajdemedleVR1pevnyˊbod 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 s1(e,y)s_1(e,y) (jedné proměnné yy) má podle VR1 pevný bod aa, takže φs1(e,a)φa\varphi_{s_1(e,a)} \simeq \varphi_{a}. Opět stačí dosadit aa za yy.

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 x:φe(x)=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 aa plyne z předchozí věty, pokud za f dosadíme funkci f(a,x)=af(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 x,y1,...,yn:φf(g(y1,...,yn),y1,...,yn)(x)φg(y1,...,yn)(x)\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:

fCˇRFn+1gPRFn:xN,yNn:φf(g(y),y)(x)φg(y)(x)\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 jj máme y\vec y, který je ještě navíc jako parametr ff.

Důkaz

Jako hint použijeme g(y)=sn+1(z,z,y)g(\vec y)=s_{n+1}(z,z,\vec y) a zopakujeme osvědčený postup:

φf(sn+1(z,z,y),y)(x)ψn+2(e,z,y,x)ψ1(sn+1(e,z,y),x)φsn+1(e,z,y)(x)\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(y):=sn+1(e,e,y)g(\vec y):=s_{n+1}(e,e,\vec y).

Riceova věta

"Nechť A\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φxA}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)$

  • A\mathcal{A} je množina funkcí, kdežto BB 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 A\mathcal{A} jen jednu funkci, tak množina BB 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 BB. Jelikož A\mathcal{A} je netriviální, nutně musí existovat nějaký bod bBb \in B a nějaký bod cBc \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 ff jsme sestrojili naschvál "obráceně". Všechny prvky z BB se zobrazí mimo BB a všechny prvky z doplňku BB se zobrazí dovnitř BB. Díky předpokladu, že BB je rekurzivní, můžeme tvrdit, že ff je ORF (charakteristická funkce BB vrací 1 či 0, naše ff vrací místo jedničky cc a místo nuly bb).

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 ff je ČRF, tedy existuje nějaký její pevný bod ee takový, že

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

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

Pokud eBe \notin B, dostaneme spor obdobným způsobem:

eBf(e)=bBe \notin B \Rightarrow f(e)=b \in B.

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

Důsledek: ekvivalence programů

"Ekvivalenci programů nelze rozhodnout algoritmicky."

Mějme nějaký program s indexem e. Zvolíme A={φe}\mathcal{A}=\{\varphi_e\}, čili B={xφx=φe}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í.