TIN064 Věty o rekurzi: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Důsledek: quine v ČRF je snadný)
m (Důkaz: chybelo y v parametrech)
Řádka 52: Řádka 52:
 
=== Důkaz ===
 
=== Důkaz ===
 
Jako hint použijeme <math>g(\vec y)=s_{n+1}(z,z,\vec y)</math> a zopakujeme osvědčený postup:
 
Jako hint použijeme <math>g(\vec y)=s_{n+1}(z,z,\vec y)</math> a zopakujeme osvědčený postup:
<math>\varphi_{f(s_{n+1}(z,z,\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)</math>
+
<math>\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)</math>
  
 
<math>g(\vec y):=s_{n+1}(e,e,\vec y)</math>.
 
<math>g(\vec y):=s_{n+1}(e,e,\vec y)</math>.

Verze z 20. 1. 2009, 13:43

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 ČRF f existuje program s indexem $ a $, který je ekvivalentní (ve smyslu $ \simeq $) programu s indexem $ f(a) $. (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 $ \lambda x, z\, \varphi_{f(s_1(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

Ve Strojilových skriptech (str. 11) je celkem hezky popsáno, proč program $ a $ počítá déle než program $ f(a) $. Ve zkratce program $ a $ nejdříve vypočítá svůj index (čili $ a $) a pak vypočítá hodnotu $ f(a) $.
Tato část je neúplná a potřebuje rozšířit. přepsat sem?

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

Tato část je neúplná a potřebuje rozšířit. převede se na VR1

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

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

  • Důležité je uvědomit si, že se nejedná o třídu programů, ale o třídu funkcí. 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.

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í, tedy buďto oba náleží do $ \mathcal{A} $, nebo oba náleží mimo $ \mathcal{A} $. 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í.