Obsah

IN13 Vyčíslitelnost
Diskuze

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.

Vyčíslitelnost nám poskytuje základní klasifikaci problémů z hlediska jejich řešitelnosti.
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?

Churchova teze ¹⁾

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

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

Definice 3.1 Sémantická funkce programu ²⁾

Nechť P je while-program s proměnnými x₁,…,x_n, j >= 0. Definujeme funkci $\varphi^{\scriptsize{(j)}}_{\scriptsize{P}} : N^j \rightarrow N$ takto:

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

kde $\sigma$ je stav takový, že

$\sigma (x_i)=\{^{\ a_i \ pro\ 1\leq i \leq j}_{0\ jinak}$

Funkce $\varphi^{\scriptsize{(j)}}_{\scriptsize{P}}$ se nazývá sémantická funkce programu P (arity j).

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

Základní definice³⁾

Funkce $\Psi : N^j \rightarrow N$ se nazývá (efektivně) vyčíslitelná, právě když existuje while-program P takový, že $\Psi = \varphi^{\scriptsize{(j)}}_{\scriptsize{P}}$ .
Jeli funkce $\Psi$ totální a vyčíslitelná, pak se nazývá totálně vyčíslitelná.

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 ⁴⁾ code(P) často nazýváme indexem programu P.
Další nástroj je standardní numerace programů a funkcí ⁵⁾ použitím numerace získáme index programu/funkce.

Věta o numeraci ⁶⁾

Ke každému $j\geq 1$ existuje vyčíslitelná funkce $\Phi : N_{j+1} \rightarrow N$ která je univerzální pro standardní numeraci j-árních vyčíslitelných funkcí, t.j. pro každé $e\in N, \ (a_1,...,a_j)\in N^j$ platí:
$\Phi (e,a_1,...,a_j)=\varphi_e (a_1,...,a_j)$

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.

Definice 6.1 Rekurzivní a rekurzívně spočetná množina ⁷⁾

Nechť $\small A\subseteq \mathbb{N}^k,\ B\subseteq \mathbb{N}$ .

Množina A je rekurzivní $\Leftrightarrow\ \small \exists$ TVF $\small f: \mathbb{N}^k\rightarrow \mathbb{N}$ taková, že $\small A = f^{-1}(\{1\})$ . Pak f se nazývá rozhodovací funkce pro A.
Množina B je rekurzívně spočetná $\Leftrightarrow\ \small B=\emptyset\ \vee\ \exists$ TVF $\small f: \mathbb{N}\rightarrow \mathbb{N}$ taková, že B = range(f). Pak f se nazývá numerující funkce pro B.

V definici používáme f^-1, rozumíme tím $\small f^{-1}(C)=\{x|f(x)\in C\}$

Existují ekvivalentní definice

Definice 6.15 další definice rekurzívní spočetnosti (r.e.) ⁸⁾

Nechť $\small A\subseteq \mathbb{N}^k,\ B\subseteq \mathbb{N}$ .

Množina B je r.e. $\Leftrightarrow\ \small \exists$ VF $\small f:\mathbb{N}\rightarrow \mathbb{N}$ taková, že B = range(f).
Množina B je r.e. $\Leftrightarrow\ \small \exists$ VF $\small f:\mathbb{N}\rightarrow \mathbb{N}$ taková, že B = dom(f).
Množina B je r.e. $\Leftrightarrow\ \small \exists$ TS, který akceptuje každý prvek z B (na prvku, který z b není, buď neakceptuje, nebo cyklí).
Množina B je r.e. $\Leftrightarrow\ \small \exists$ (while) program, který množinu B generuje.
Relace B je r.e. právě když je projekcí rekurzivní relace.

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.

Věta 8.1 - Riceova ⁹⁾

Nechť $I \subseteq N, I \neq \emptyset, I \neq N$ a nechť I je rekurzivní. Pak existují $i\in I$ a $j \in \overline{I}$ tak, že $\varphi_i = \varphi_j$ .

Důkaz

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

Nechť P_f(i) je program ( $f(i)$ je index programu P):

$begin\ x_2:= \Phi (i,i);\ x1:=\theta (x_1)\ end$

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

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

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

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

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

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

$\chi_I (f(i)) = 1 \Leftrightarrow \varphi _{f(i)} = \theta$

$\chi_I (f(i)) = 1 \Leftrightarrow i\in K$

Protože $\chi_I \circ f$ je totálně vyčíslitelná, je K rekurzivní, což je spor.

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:

Definice 8.2 - respektování funkcí

Říkáme, že množina $I \subseteq N$ respektuje funkce, jestliže platí:
$i\in I\ a\ \varphi_i = \varphi_j \Rightarrow j\in I$ ¹⁰⁾

Bezprostředně z definice plyne, že pokud I respektuje funkce, pak i co-I respektuje funkce.
Množiny $\small \{ i | 7\in range (\varphi_i) \},\ \{ i |\varphi_i = \mu \}$ , kde $\small \mu$ 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í.

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

Definice 9.1 Redukce ¹¹⁾

Nechť $A,B\subseteq N$ .

Říkáme, že A se redukuje na B(píšeme $A \small{ \leq_{\scriptsize m}} \large B$ ) právě když existuje totálně vyčíslitelná funkce $f:N\rightarrow N$ taková, že $A = f^{-1}(B)$ .
Říkáme, že A a B jsou m-ekvivalentní (píšeme $A\small{\equiv_{\scriptsize m}}\large B$ ) právě když $A \small{ \leq_{\scriptsize m}} \large B$ a $B \small{ \leq_{\scriptsize m}} \large A$

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.

Věta 9.3 ¹²⁾

Nechť $A \small{ \leq_{\scriptsize m}} \large B$ 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á
$\overline{A} \small{ \leq_{\scriptsize m}} \large \overline{B}$

Důsledek:

Jestliže A není rekurzivní, pak B není rekurzivní.
Jestliže A není r.e., pak B není r.e.

Redukce poskytuje nástroj na porovnání množin.

Věta

Jeli množina $A \subseteq N$ r.e., pak $A \small{ \leq_{\scriptsize m}} \large K$

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.

Definice těžkosti a n-úplnosti

Nechť C je třída podmnožin množiny N a $A \subseteq N$ . Řekneme, že množina A je C-těžká, právě když pro každou množinu $B \in C$ platí $B \small{ \leq_{\scriptsize m}} \large A$ . Jeli navíc $A \in C$ , pak A se nazývá C-úplná(úplná v třídě C)

Uzávěrové vlastnosti

Lema 6.5 Uzavřenost vůči doplňku ¹³⁾

Nechť $\small A \subseteq N$ je rekurzívní množina.
Pak množina co-A je rekurzivní množina

Lema 6.5 A a co-A jsou r.e. ¹⁴⁾

Množina $\small A \subseteq N$ je rekurzívní právě když A a co-A jsou r.e.

Věta 7.1 Rekurzivní a množina¹⁵⁾

Nechť $\small A,B \subseteq N$ jsou rekurzívní množiny a f:N→N je totálně vyčíslitelná funkce.
Pak množiny
$A \cup B,\ A \cap B,\ \overline{A},\ f^{-1}(A),\ A\times B$ jsou rekurzivní.

Věta 7.4 uzávěrové vlastnosti r.e. ¹⁶⁾

Existují totálně vyčíslitelné funkce h,g:N²→N takové, že pro libovolné dvě r.e. množiny $W_i,\ W_j$ platí:

$W_i\cup W_j = W_{h(ij)}$
$W_i\cap W_j = W_{g(ij)}$

Jde o svým způsobem vyslovenou uzavřenost r.e. množin vůči průniku a sjednocení. W_i značí množinu vyčíslenou i-tým programem.

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.

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, $A_3 = \{i|\varphi_i = g\}$ 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, $A = \{i,j|\varphi_i = \varphi_j\}$ 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. problém zastavení

Věta 4.7 Problém zastavení ¹⁷⁾

Funkce f:N→N taková, že
$f(i)\ = \ \{^{1\ je-li\ \varphi_i(i)\ def.}_{0\ pokud\ \varphi_i(i)\ def.\ neni}$ není vyčíslitelná

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 $g:N\rightarrow N$ takovou, že
$g(i)=\{^{\perp\ pokud\ f(i)=1} _{1\ pokud\ f(i)=0}$

program confuse, který počítá funkci g, vypadá následovně:

begin  
  while halt(x1) = 1 do x1 = x1; 
  x1 = 1 
end;

Nechť e je index programu confuse. Pak $\normalsize g(i)=\varphi_e (i)$ pro všechna i. Z definice funkcí g a f pak dostáváme pro i = e $\normalsize g(i)=\varphi_e (i) = \{^{\perp\ pokud\ \varphi_e (i) je def.} _{1\ pokud\ \varphi_e (i) neni def.}$ .
Dostáváme tím spor: $\varphi_e (i)$ je definováno, právě když $\varphi_e (i)$ není definováno. Funkce f proto nemůže být vyčíslitelná.

Důkaz, že K nerespektuje funkce: Existuje index $e$ tak, že $W_e\ = \ {e}$ ¹⁸⁾. Tedy $e\in K$ . Máme-li $e' \neq e$ takové, že $\varphi_{e'}=\varphi_e$ , pak $e'\notin K$ Slovně: máme W, který vypíše svůj index¹⁹⁾, 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ě:
$K = \{ \ i\ |\ \varphi_{i}(i)\ je\ definovano\ \}$ 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ů

Problém nezastavení, tj. co-K není r.e. 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

$A_1=\{ \ i\ |\ \varphi_i\ je\ totalni\}$ není rekurzivní.
Dle důsledku r.v. stačí ukázat, že A₁ respektuje funkce a je netriviální.
Respektování funkcí: $i\in A_1\ a\ \varphi_i = \varphi_j\ pak\ \varphi_j\ je\ totalni \Rightarrow j\in A_1$ 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

$B = \{ \ i\ |\ \varphi_i = identita\}$ 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

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

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

Je potřeba ještě zapracovat poznámky od Jitky Pospíšilové.

¹⁾

Luboš Brim, Výpočetní modely, Přednáška č. 1, slide. 41

²⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 13

³⁾

Luboš Brim, Numerace vyčíslitelných funkcí, Přednáška č. 2, str. 3

⁴⁾

definici naleznete v Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 21-22

⁵⁾

definici naleznete v Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 22

⁶⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 24

⁷⁾

Luboš Brim, Vyčíslitelnost – poznámky k přednášce, 2002, str 39

⁸⁾

Luboš Brim, Vyčíslitelnost – poznámky k přednášce, 2002, str 44

⁹⁾ , ¹⁰⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 51

¹¹⁾ , ¹²⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 57

¹³⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 41

¹⁴⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 42

¹⁵⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 47

¹⁶⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 48

¹⁷⁾

Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 23

¹⁸⁾

důkaz viz skripta str. 61 a dále

¹⁹⁾

aspoň tak to chápu já