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

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

Nechť P je while-program s proměnnými x1,…,xn, 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í definice3)

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

Věta o numeraci 6)

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

Nechť \small A\subseteq \mathbb{N}^k,\ B\subseteq \mathbb{N}.
  1. 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.
  2. 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.) 8)

Nechť \small A\subseteq \mathbb{N}^k,\ B\subseteq \mathbb{N}.
  1. Množina B je r.e. \Leftrightarrow\ \small \exists VF \small f:\mathbb{N}\rightarrow \mathbb{N} taková, že B = range(f).
  2. Množina B je r.e. \Leftrightarrow\ \small \exists VF \small f:\mathbb{N}\rightarrow \mathbb{N} taková, že B = dom(f).
  3. 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í).
  4. Množina B je r.e. \Leftrightarrow\ \small \exists (while) program, který množinu B generuje.
  5. 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 9)

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ť Pf(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 I10)

  • 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 11)

Nechť A,B\subseteq N.
  1. Ří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).
  2. Ří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 12)

Nechť A \small{ \leq_{\scriptsize m}} \large B pak:
  1. Je-li B rekurzivní, pak i A je rekurzívní.
  2. Je-li B rekurzívně spočetná, pak i A je rekurzívně spočetná
  3. \overline{A} \small{ \leq_{\scriptsize m}} \large \overline{B}


Důsledek:

  1. Jestliže A není rekurzivní, pak B není rekurzivní.
  2. 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 13)

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

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žina15)

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

Existují totálně vyčíslitelné funkce h,g:N2→N takové, že pro libovolné dvě r.e. množiny W_i,\ W_j platí:
  1. W_i\cup W_j = W_{h(ij)}
  2. 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í. Wi 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í 17)

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}18). 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 index19), 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 A1 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í.

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

1) Luboš Brim, Výpočetní modely, Přednáška č. 1, slide. 41
2) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 13
3) Luboš Brim, Numerace vyčíslitelných funkcí, Přednáška č. 2, str. 3
4) definici naleznete v Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 21-22
5) definici naleznete v Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 22
6) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str. 24
7) Luboš Brim, Vyčíslitelnost – poznámky k přednášce, 2002, str 39
8) Luboš Brim, Vyčíslitelnost – poznámky k přednášce, 2002, str 44
9) , 10) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 51
11) , 12) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 57
13) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 41
14) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 42
15) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 47
16) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 48
17) Luboš Brim, Vyčíslitelnost - poznámky k přednášce, 2002, str 23
18) důkaz viz skripta str. 61 a dále
19) aspoň tak to chápu já

Diskuze

, 2008/06/16 17:04

Pro snažší pochopení první Riceovy věty neformální vysvětlení, jak to chápu já:

Jde o redukci K na I. Chci ukázat, že pomocí rekurzivity množiny I bych uměl rozhodovat i množinu K. Jak teda můžu využít rekurzivitu I k rozhodování K? Vezmu si nějakou vyčíslitelnou funkci, \theta, která má neprázdný definiční obor. Předpokládám, že všechny její indexy jsou v I (dokazuji sporem). Potom předpokládám, že prázdná funkce (\mu) má všechny svoje indexy v co-I. Díky tomu můžu u každého programu podle jeho indexu rozhodnout, zda se rovná \theta nebo \mu, prostě podle toho, jestli ten index patří do I nebo ne.
Když si vezmu program
begin x_2 = \Phi(i, i); x_1 = \theta(x_1) end
potom jeho index dokážu pro každé i spočítat (označím si ten index f(i)). Tento program se rovná buď \theta nebo \mu podle toho, jestli i\in K nebo ne. Takže právě když f(i) \in I, pak i i \in K a to je spor.

Hm.. tak nevim, jestli tohle někomu pomůže :)

, 2008/06/19 15:42

Jo dobře jsi to vysvětlil. Ten důkaz je tady nekompletní chybí tam nějaké předpoklady.

, 2008/06/20 13:45

Souhlas, dobře vysvětlený, přidal jsem předpoklady, ale pořád je to takové těžkopádné, pokud to někdo chcete upravit, tak můžete.

, 2008/06/19 18:04

Množina K nie je r.e.? Množina K predsa je r.e., alebo sa mýlim?

, 2008/06/19 18:32

samozrejme, ze je..inak by to nemohol byt uplny problem pre r.e., treba to v texte opravit

, 2008/06/20 12:49

opraveno, se mi tam zamotaly 2 myšlenky dohromady :|

, 2008/06/21 13:46

V definici 6.1 je chyba. Rozhodovacia funkcia pre A musi byt totalne vycislitelna.

, 2008/06/21 14:21

jj, ted jsem se ji ucil, tak to tam opravim, naopak u r.e. nemusi byt TVF, kdyz zadame podminku, ze B!=0. V jednom miste je tam jeste pomotana charakteristicka funkce a schematicka + nejaky preklepy, tak to opravim.

, 2008/06/21 15:01

Upravil jsem sekci příklady, jednak jsem přidal základní přehled příkladů a oddělil je od samotného řešení a druhak jsem přidal nějaké nové

, 2008/06/21 15:36

Neuteklo ti ve vete 7.4 ve druhe casti na prave strane W? taky g,h jsou z NxN → N a aplikace je tvaru g(ij), tj. N → N. Vim ze to nejsou moc dulezite pripominky, pisu to jen abys o tom vedel.

, 2008/06/24 12:43

POZOR: v dvoch definíciách r.e. množiny boli chyby, bolo tam:

Základná definícia:

  • Množina B je rekurzívně spočetná právě když \small B=\emptyset nebo existuje vyčíslitelná funkce \small f:N\rightarrow N taková, že B=range(f). Pak f se nazývá numerující funkce pro B

a potom ešte v prvej alternatívnej definícii bolo:

  • Množina B je rekurzívně spočetná právě když existuje totálně vyčíslitelná funkce \small f:N\rightarrow N taková, že B=range(f)

Správne to má byť:

  • Množina B je rekurzívně spočetná právě když \small B=\emptyset nebo existuje TOTÁLNĚ vyčíslitelná funkce \small f:N\rightarrow N taková, že B=range(f). Pak f se nazývá numerující funkce pro B

a:

  • Množina B je rekurzívně spočetná právě když existuje totálně vyčíslitelná funkce \small f:N\rightarrow N taková, že B=range(f)

Idem to opraviť a doplniť ďalšie definície…
EDIT: Hotovo

You could leave a comment if you were logged in.
home/inf/in13.txt · Poslední úprava: 2014/10/27 09:07 (upraveno mimo DokuWiki)
Nahoru
CC Attribution-Noncommercial-Share Alike 3.0 Unported
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0