====== IN13 Vyčíslitelnost ======

===== Zadání =====
(rekurzivní a rekurzivně spočetné množiny. První Riceova věta. Redukce a její vlastnosti. Uzávěrové vlastnosti rekurzívních a rekurzivně spočetných množin. Příklady rekurzivních a rekurzivně spočetných množin.)


===== Vypracování =====

==== Zkratky a termíny ====

  * **VF** -- vyčíslitelná funkce
  * **TVF** -- totálně vyčíslitelná funkce
  * **TS** -- Turingův stroj
  * //**dom(f)**// -- definiční obor funkce **f**
  * //**range(f)**// -- obor hodnot funkce **f**
  * **rek.** -- rekurzivní
  * **r.e.** -- rekurzivně spočetná (//recursively enumarable//)

==== Základy ====

V zadání sice tyto znalosti nejsou požadovány, ale myslím, že jsou nezbytné pro pochopení dalšího textu.

**<color blue>Vyčíslitelnost</color>** nám poskytuje základní klasifikaci problémů z hlediska jejich **<color blue>řešitelnosti</color>**.
V teorii vyčíslitelnosti uvažujeme 3 základní výpočetní modely: Turingovy stroje, RAM stroje a while programy. Nejčastěji se setkáme s problémy: //Je funkce vyčíslitelná? Patří prvek do dané množiny?//

<box green 95% round | Churchova teze ((Luboš Brim, Výpočetní modely, Přednáška č. 1, slide. 41))>Každá částečná funkce nad přirozenými čísly je **intuitivně vyčíslitelná** (v jakémkoliv akceptovatelném smyslu) tehdy a jen tehdy když je vyčíslitelná (while-programem, TS, RAM prog.)</box>Je důležité si uvědomit, že nejde o matematické tvrzení, tudíž nelze dokázat. Obecně se má za to, že platí, a proto některé důkazy vyčíslitelnosti problému se odkazují na tuto tezi (formálně to ale není správně!).

Poskytneme si nyní formálnější definice vyčíslitelnosti
<box blue 95% round | Definice 3.1 Sémantická funkce programu ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 13))>

Nechť //**P**// je while-program s proměnnými //**x<sub>1</sub>,...,x<sub>n</sub>, j >= 0**//. Definujeme funkci <math>\varphi^{\scriptsize{(j)}}_{\scriptsize{P}} : N^j \rightarrow N</math> takto:

<math>\varphi^{\scriptsize{(j)}}_{\scriptsize{P}}(a_1,...,a_j)=^{\scriptsize{df}}\{^{[P](\sigma)(x_1)\  je-li[P](\sigma)\ def}_{\perp\ jinak}</math>

kde <math>\sigma</math> je stav takový, že

<math> \sigma (x_i)=\{^{\ a_i \ pro\ 1\leq i \leq j}_{0\ jinak}</math>

Funkce <math>\varphi^{\scriptsize{(j)}}_{\scriptsize{P}}</math> se nazývá **sémantická funkce** programu //**P**// (arity //**j**//).</box>Sémantická funkce je jak vidmo z definice taková funkce, která vyjadřuje chování programu, obsahuje v sobě výpočet algoritmu(abychom byly úplně přesní, tak by bylo třeba uvést definici kroku výpočtu algoritmu a další definice, ale pro základní pochopení to snad stačí).
<box blue 95% round | Základní definice((Luboš Brim, Numerace vyčíslitelných funkcí, Přednáška č. 2, str. 3))>Funkce <math>\Psi : N^j \rightarrow N</math> se nazývá **<color blue>(efektivně) vyčíslitelná</color>**, právě když existuje while-program //**P**// takový, že <math>\Psi = \varphi^{\scriptsize{(j)}}_{\scriptsize{P}}</math>. 
Jeli funkce <math>\Psi</math> totální a vyčíslitelná, pak se nazývá **totálně vyčíslitelná**.
</box>
Dále je důležitá **numerace funkcí**, jde o způsob, jakým očíslovat všechny sémantické funkce a tím pádem i všechny programy.
K tomu používáme funkci //**code: P->N**// ((definici naleznete v Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 21-22)) //**code(P)**// často nazýváme indexem programu //**P**//.
Další nástroj je **standardní numerace programů a funkcí** ((definici naleznete v Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 22)) použitím numerace získáme index programu/funkce.

<box green 95% round | Věta o numeraci ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 24))>Ke každému <math>j\geq 1</math> existuje vyčíslitelná funkce <math>\Phi : N_{j+1} \rightarrow N</math> která je univerzální pro standardní numeraci j-árních vyčíslitelných funkcí, t.j. pro každé <math>e\in N, \ (a_1,...,a_j)\in N^j</math> platí:
<math>
\Phi (e,a_1,...,a_j)=\varphi_e (a_1,...,a_j)</math></box>Jak už sama věta říká, jde o univerzální funkci, této funkci když předložíme index funkce a vstupní parametry, tak vypočítá totéž, co by vypočítala funkce, jejíž index jsme zadali.


==== Rekurzivní a rekurzivně spočetné množiny ====
  * rekurzivní množina = rozhodnutelná množina = řešitelná množina (alternativní názvy)
  * rekurzívně spočetná = částečně rozhodnutelná = rekurzívně vyčíslitelná = r.e.
  * o problému budeme říkat, že je rozhodnutelný, respektive částečně rozhodnutelný

Rekurzivní a r.e. množiny popisují vyčíslitelné vlastnosti z pohledu množin. Důležitou vlastností množin je to, zda mají totálně vyčíslitelnou (rekurzivní) charakteristickou funkci (tak nazýváme funkci, která rozhoduje, zda prvek patří, nebo nepatří do množiny), množiny s totálně vyčíslitelnou charakteristickou funkcí nazýváme rekurzivní.
Další vlastnost je to, zda je množina definičním oborem vyčíslitelné funkce. Tuto vlastnost mají vyčíslitelně spočetné množiny(r.e. množiny).
Rekurzivní množiny jsou rozhodnutelné v tom smyslu, že existuje algoritmus pro rozhodování, zda prvek patří nebo nepatří do množiny. Naproti tomu pro r.e. existuje pouze algoritmus, který vytváří seznam prvků množiny.

<box 95% round blue| Definice 6.1 Rekurzivní a rekurzívně spočetná množina ((Luboš Brim, Vyčíslitelnost -- poznámky k přednášce, 2002, str 39))>Nechť <math>\small A\subseteq \mathbb{N}^k,\ B\subseteq \mathbb{N} </math>.
  - Množina //**A**// je **<color blue>rekurzivní</color>** <math>\Leftrightarrow\ \small \exists</math> **<color red>TVF</color>** <math>\small f: \mathbb{N}^k\rightarrow \mathbb{N}</math> taková, že <math>\small A = f^{-1}(\{1\})</math>. Pak //**f**// se nazývá **rozhodovací funkce pro //A//**.
  -  Množina //**B**// je **<color blue>rekurzívně spočetná</color>** <math>\Leftrightarrow\ \small B=\emptyset\ \vee\ \exists</math> **<color red>TVF</color>** <math>\small f: \mathbb{N}\rightarrow \mathbb{N}</math> taková, že //**B = range(f)**//. Pak //**f**// se nazývá **numerující funkce pro //B//**.
</box>V definici používáme //**f<sup> -1</sup>**//, rozumíme tím <math>\small f^{-1}(C)=\{x|f(x)\in C\}</math>

Existují ekvivalentní definice 
<box 95% round blue| Definice 6.15 další definice **<color blue>rekurzívní spočetnosti (r.e.)</color>**  ((Luboš Brim, Vyčíslitelnost -- poznámky k přednášce, 2002, str 44))>Nechť <math>\small A\subseteq \mathbb{N}^k,\ B\subseteq \mathbb{N} </math>.
  - Množina //**B**// je r.e. <math>\Leftrightarrow\ \small \exists</math> **<color red>VF</color>** <math>\small f:\mathbb{N}\rightarrow \mathbb{N}</math> taková, že //**B = range(f)**//.
  - Množina //**B**// je r.e. <math>\Leftrightarrow\ \small \exists</math> **<color red>VF</color>** <math>\small f:\mathbb{N}\rightarrow \mathbb{N}</math> taková, že //**B = dom(f)**//.
  - Množina //**B**// je r.e. <math>\Leftrightarrow\ \small \exists</math> **TS**, který **akceptuje** každý prvek z //**B**// (na prvku, který z b není, buď neakceptuje, nebo cyklí).
  - Množina //**B**// je r.e. <math>\Leftrightarrow\ \small \exists</math> (while) **program**, který množinu //**B**// **generuje**.
  - Relace //**B**// je r.e. právě když je projekcí rekurzivní relace.

</box>
Třídy rekurzivních množin a r.e. množin jsou různé. Každá rekurzivní množina je rekurzívně spočetná (pokud dokážeme rozhodnout, zda prvek patří do množiny, dokážeme i generovat prvky množiny), ale opak obecně neplatí. Důležitou roli hrají r.e. množiny, které nejsou rekurzivní(například problém zastavení, viz. příklady).

==== První Riceova věta ====
Riceova věta říká, že rozhodnutelnost je výjimkou, která potvrzuje pravidlo.

<box 95% round green|Věta 8.1 - Riceova ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 51))>Nechť <math> I \subseteq N, I \neq \emptyset, I \neq N</math> a nechť //**I**// je rekurzivní. Pak existují <math> i\in I</math> a <math> j \in \overline{I}</math> tak, že <math> \varphi_i = \varphi_j </math>.</box>

<box 95% round orange | Důkaz>

Tvrzení dokážeme sporem. Předpokládejme, že pro všechna <math>i\in I</math> a <math>j\in \overline{I}</math> platí <math>\varphi_i \neq \varphi_j</math>. Předpokládejme, že //**I**// obsahuje index nějaké vyčíslitelné funkce <math>\theta</math>(a tím i všechny její indexy), která je různá od prázdné funkce <math>\mu</math>, a že <math>\overline{I}</math> obsahuje všechny indexy <math>\mu</math>.

Nechť //**P<sub>f(i)</sub>**// je program (<math>f(i)</math> je index programu P):

<math>begin\ x_2:=  \Phi (i,i);\ x1:=\theta (x_1)\ end</math>

Program P je tedy vyčíslitelný. Je zřejmé, že 

<math>\varphi _{f(i)} = \{ ^{\small \theta\ je-li\ \varphi _i(i)\ definovano}
_{\small \mu\ jinak}
</math>

Tedy pro všechna <math> i\in N</math> platí <math>  \varphi_{f(i)} =  \theta</math> právě, když je <math> \varphi _i(i)</math> definováno, t.j. <math> i\in K</math>.

Dále, je-li <math> \varphi_{f(i)} = \mu</math>, pak <math>f(i) \in \overline{I}</math>(jakožto index funkce <math> \mu</math>).

Jestliže tedy <math> f(i) \in I</math>, pak <math>  \varphi_{f(i)} \neq  \mu</math> a proto <math>  \varphi_{f(i)} =  \theta</math>.

Obráceně pak, jestliže <math>  \varphi _{f(i)} =  \theta</math>, pak <math> f(i) \in I</math>(jakožto index funkce <math> \theta</math>). Nechť <math>\chi_{I}</math> je charakteristická funkce množiny //**I**//. Pak pro všechna <math>i \in N</math> platí:

<math>
\chi_I (f(i)) = 1 \Leftrightarrow \varphi _{f(i)} = \theta
</math>

<math>\chi_I (f(i)) = 1 \Leftrightarrow i\in K</math>

Protože <math>\chi_I \circ f</math> je totálně vyčíslitelná, je //**K**// rekurzivní, což je spor.
</box>//poznámka: jako index funkce používáme f(i) z toho důvodu, že f(i) nám říká, že máme funkci(totálně vyčíslitelnou) s jejíž pomocí jsme schopni vždy index programu P vypočítat(bude pro každé i jiný), stejně tak použijeme tuto funkci při dokazování problému zastavení v příkladech//

Často se věta formuluje obráceně s využitím následující definice:
<box 95% round blue|Definice 8.2 - respektování funkcí>Říkáme, že množina <math> I \subseteq N</math> respektuje funkce, jestliže platí:
<math>i\in I\ a\ \varphi_i = \varphi_j \Rightarrow j\in I</math>((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 51))
</box>

<note>
  * Bezprostředně z definice plyne, že pokud //**I**// respektuje funkce, pak i //**co-I**// respektuje funkce.
  * Množiny <math>\small \{ i | 7\in range (\varphi_i) \},\ \{ i |\varphi_i = \mu \}</math>, kde <math>\small \mu</math> je prázdná funkce, jsou příklady množin, které respektují funkce
  * Množina //**K**// nerespektuje funkce, důkaz viz příklady

Důsledek:
Netriviální (t.j. neprázdná a vlastní) podmnožina množiny //**N**//, která respektuje funkce, není rekurzivní.</note>Existují další 2 Riceovy věty, to sice není to v zadání, ale může se hodit vědět, že složí k dokázání, že množina není //**r.e**//


==== Redukce a její vlastnosti ====
Redukci jsme již použili v první Riecově větě, konkrétně v důkazu 1. R.v, kdy jsme využili sporu s rekurzivností //**K**// (množinu //**K**// jsme redukovali na //**I**// ).

<box 95% round blue| Definice 9.1 Redukce ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 57))>Nechť <math> A,B\subseteq N</math>.
  - Říkáme, že //**A**// se **<color blue>redukuje</color>** na //**B**//(píšeme <math>A \small{ \leq_{\scriptsize m}} \large B</math>) právě když existuje totálně vyčíslitelná funkce <math> f:N\rightarrow N</math> taková, že <math> A = f^{-1}(B)</math>.
  - Říkáme, že //**A**// a //**B**// jsou **<color blue>m-ekvivalentní</color>** (píšeme <math> A\small{\equiv_{\scriptsize m}}\large B</math>) právě když <math>A \small{ \leq_{\scriptsize m}} \large B</math> a <math>B \small{ \leq_{\scriptsize m}} \large A</math>
</box>Index //m// v označení relace znamená, že fce //**f**// nemusí být prostá (může být //many-to-one//)
Redukce je reflexivní, transitivní, tj. je kvaziuspořádání.

Redukce se používá k dokazování, že je množina rekurzivní, respektive r.e.
<box 95% round green| Věta 9.3 ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 57))>
Nechť <math>A \small{ \leq_{\scriptsize m}} \large B</math> pak:
  - Je-li //**B**// rekurzivní, pak i //**A**// je rekurzívní.
  - Je-li //**B**// rekurzívně spočetná, pak i //**A**// je rekurzívně spočetná
  - <math>\overline{A} \small{ \leq_{\scriptsize m}} \large \overline{B}</math>

\\

**Důsledek**:
  - Jestliže //**A**// není rekurzivní, pak //**B**// není rekurzivní.
  - Jestliže //**A**// není r.e., pak //**B**// není r.e.
</box>


Redukce poskytuje nástroj na porovnání množin.
<box 95% round green| Věta >Jeli množina <math>A \subseteq N</math> r.e., pak <math>A \small{ \leq_{\scriptsize m}} \large K</math>
</box>Důkaz viz skripta
Tato věta nám říká, že problém příslušnosti do //**K**// je alespoň tak **těžký** jako jakýkoliv jiný r.e. problém. Tj. pokud by existoval algoritmus pro rozhodování //**K**//, pak by existoval i algoritmus pro rozhodování libovolného r.e. problému. Protože je //**K**// r.e, říkáme, že //**K**// je nejtěžší množina mezi r.e. množinami, tj. je úplná na množině r.e.
<box 95% round blue | Definice těžkosti a n-úplnosti>Nechť //**C**// je třída podmnožin množiny //**N**// a <math>A \subseteq N</math>. Řekneme, že množina //**A**// je //**C-těžká**//, právě když pro každou množinu <math>B \in C</math> platí <math>B \small{ \leq_{\scriptsize m}} \large A</math>. Jeli navíc <math>A \in C</math>, pak //**A**// se nazývá //**C-úplná**//(úplná v třídě //**C**//)</box>


==== Uzávěrové vlastnosti ====
<box 95% round green| Lema 6.5 Uzavřenost vůči doplňku ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 41))>Nechť <math>\small A \subseteq N</math> je rekurzívní množina.
Pak množina //**co-A**// je rekurzivní množina
</box><box 95% round green| Lema 6.5 A a co-A jsou r.e. ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 42))>Množina <math>\small A \subseteq N</math> je rekurzívní právě když //**A**// a //**co-A**// jsou r.e.
</box>


<box 95% round green| Věta 7.1 Rekurzivní a množina((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 47))>Nechť <math>\small A,B \subseteq N</math> jsou rekurzívní množiny a //**f:N->N**// je totálně vyčíslitelná funkce.
Pak množiny
<math> A \cup B,\ A \cap B,\ \overline{A},\ f^{-1}(A),\ A\times B</math>
jsou rekurzivní.
</box>

<box 95% round green|Věta 7.4 uzávěrové vlastnosti r.e. ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 48))>Existují totálně vyčíslitelné funkce //**h,g:N<sup>2</sup>->N**// takové, že pro libovolné dvě r.e. množiny <math>W_i,\ W_j</math> platí:
  - <math>W_i\cup W_j = W_{h(ij)}</math>
  - <math>W_i\cap W_j = W_{g(ij)}</math>
</box> Jde o svým způsobem vyslovenou uzavřenost r.e. množin vůči průniku a sjednocení. W<sub>i</sub> značí množinu vyčíslenou i-tým programem.

<box 95% round green|Věta 7.7>
  * Kartézký součin dvou r.e. množin je r.e. množina
  * Libovolný řez rekurzivní množiny je rekurzivní množina
  * Libovolný řez r.e. množiny je r.e. množina
  * Libovolná projekce r.e. množiny je r.e. množina.
</box>


==== Příklady r.e. a rekurzivních množin ====
//Ač si nemyslím, že je v silách kohokoliv demonstrovat tyto příklady u SZZ včetně jejich řešení, uvádím tu i jejich řešení pro úplnost.//

==== Základní příklady ====
Problém zastavení //**K**// není rekurzivní, ale je r.e.
Problém verifikace: dokázat, <math>A_3 = \{i|\varphi_i = g\}</math> kde //**g**// je pevná vyčíslitelná funkce není rekurzivní. (praktický důsledek: neumíme obecně sestrojit program, který zjistí, zda námi vytvořený program počítá co má.)
Problém ekvivalence: dokázat, <math>A = \{i,j|\varphi_i = \varphi_j\}</math> není rekurzivní(praktický důsledek - program nezjistí, zda 2 programy počítají totéž)
Problém nezastavení //**co-K**// není r.e. 

=== Problém zastavení ===
Asi nejdůležitějším příkladem této kapitoly je tzv. <color blue>problém zastavení</color>
<box 95% round green | Věta 4.7 Problém zastavení ((Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 23))> Funkce //**f:N->N**// taková, že 
<math>f(i)\ = \ \{^{1\ je-li\ \varphi_i(i)\ def.}_{0\ pokud\ \varphi_i(i)\ def.\ neni}</math>
**není vyčíslitelná**
</box>Důkaz:
Tvrzení dokážeme sporem. Předpokládejme, že funkce //**f**// je vyčíslitelná, nechť //**halt**// je program, který počítá funkci //**f**//. Uvažujme funkci <math>g:N\rightarrow N</math> takovou, že
<math> g(i)=\{^{\perp\ pokud\ f(i)=1} _{1\ pokud\ f(i)=0}</math>

program //**confuse**//, který počítá funkci //**g**//, vypadá následovně:
<code>begin 
  while halt(x1) = 1 do x1 = x1;
  x1 = 1
end;
</code>Nechť //**e**// je index programu //**confuse**//. Pak <math>\normalsize g(i)=\varphi_e (i)</math> pro všechna //**i**//. Z definice funkcí //**g**// a //**f**// pak dostáváme pro //**i = e**//
<math>\normalsize g(i)=\varphi_e (i) = \{^{\perp\ pokud\ \varphi_e (i) je def.} _{1\ pokud\ \varphi_e (i) neni def.}</math>.
Dostáváme tím spor: <math>\varphi_e (i)</math> je definováno, právě když <math>\varphi_e (i)</math> není definováno. Funkce //**f**// proto nemůže být vyčíslitelná.

**Důkaz, že //**K**// nerespektuje funkce:**
Existuje index <math>e</math> tak, že <math>W_e\ = \ {e}</math>((důkaz viz skripta str. 61 a dále)). Tedy <math>e\in K</math>. Máme-li <math>e' \neq e</math> takové, že <math>\varphi_{e'}=\varphi_e</math>, pak <math>e'\notin K</math> 
//Slovně: máme W, který vypíše svůj index((aspoň tak to chápu já)), které má index e, pokud máme program s indexem e', jehož funkce je stejná, tj. vypíše program e, pak nepatří do K.//

Množinově můžeme problém zastavení popsat následovně:
<math> K = \{ \ i\ |\ \varphi_{i}(i)\ je\ definovano\ \}</math>
Množina //**K**// není rekurziní jelikož její charakteristická funkce není totálně vyčíslitelná, ale je r.e.

Proč je tento problém tak důležitý?
  * využívá se k důkazům, že něco není vyčíslitelné (přes redukci, uzávěrové vlastnosti atd.)
  * je to úplný problém pro množinu r.e. problémů

**<color blue>Problém nezastavení</color>**, tj. **//co-K//** **<color blue>není r.e.</color>** dokážeme triviálně přes uzávěrové vlastnosti - Lema 6.5 A a co-A jsou r.e. => A je rekurzivní, takže pokud by byla **//co-K//** r.e. byla by //**K**// rekurzivní, což jsme dokázali, že není.

=== Příklad na použití Riceovy věty ===
<math> A_1=\{ \ i\ |\ \varphi_i\ je\ totalni\}</math> není rekurzivní.
Dle důsledku r.v. stačí ukázat, že //**A<sub>1</sub>**// respektuje funkce a je netriviální.
Respektování funkcí: <math> i\in A_1\ a\ \varphi_i = \varphi_j\ pak\ \varphi_j\ je\ totalni \Rightarrow j\in A_1</math>
Zřejmě index identické funkce do množiny patří a index prázdné ne, funkce je tedy netriviální (není prázdná a není vlastní podmnožinou //**N**//)

=== Redukce ===
<math> B = \{ \ i\ |\ \varphi_i = identita\}</math> není rekurzivní. Můžeme to sice dokázat triviálně přes 1. r.v., ale použijeme redukci.

Nechť //**f(i)**// je index programu

<math>begin\ x_2 := \Phi(i,x_1)\ end</math>
zřejmě
<math>\varphi_{\small{f(i)}}(x)=\{^{x\ jeli\ \varphi_i(x)\ definovano}_{\perp\ jinak}</math>

Tedy <math>\varphi_{f(i)}(x)=identita</math> právě když <math>\varphi_{i}(x)</math> je definováno pro všechna //**x**// a to je právě když je <math>\varphi_{i}</math> totální. Funkce //**f**// je totálně vyčíslitelná, <math> A_1=\{ \ i\ |\ \varphi_i\ je\ totalni\}</math> není rekurzivní a <math>A_1 \small{ \leq_{\scriptsize m}} \large B</math>, tedy //**B**// **není rekurzivní**.


===== Vypracuje =====
Marek Babák ICQ: 67179550) 99%, z mé strany hotovo, byl bych rád, kdyby to někdo prošel a napsal co si o tom myslí, nebylo to zcela triviální.

FIXME Je potřeba ještě zapracovat [[http://statnice.dqd.cz/tmp/vycislitelnost.pdf|poznámky od Jitky Pospíšilové]].

~~DISCUSSION~~