{{TOC float}}

{{Sources| Tohle je poněkud obšírnější výcuc ke <Státnice> z <Státnice_-Informatika-Vyčíslitelnost> pro obory <Státnice-Informatika-_I3:Matematická_lingvistika> a <Státnice-Informatika-_I2:_Softwarové_systémy>, pocházející ze Strojilových skript, papírových zápisků A. Kazdy a zápisků z předmětu Vyčíslitelnost I ze <Studnice%20vědomostí> -- User:Tuetschek 14:01, 17 Aug 2010 (CEST)

}}

Rekurzivně spočetné množiny

Definice (Rekurzivní a rekurzivně spočetná množina)

Charakteristická funkce množiny $M$ označuje charakteristickou funkci predikátu náležení do množiny, tj. funkci $c_M(x)$, kde $c_M(x)=\downarrow 1$ pro $x\in M$ a $c_M(x)\downarrow =0$ pro $x\notin M$.

Analogicky se definuje částečná charakteristická funkce množiny -- $c_M(x)=\downarrow 1$ pro $x\in M$ a $c_M(x)\uparrow$ pro $x\notin M$.

Množina $M$ je rekurzivní, je-li její charakteristická funkce obecně rekurzivní (každá char. fce je totální, takže ČRF by bylo totéž). Množina $M$ je rekurzivně spočetná, jestliže je definičním oborem nějaké ČRF (neboli jestliže je její částečná char. funkce částečně rekurzivní).

Množina je rekurzivní, jestliže existuje program, který se na libovolném vstupu zastaví a rozhodne, zda do ní vstup patří. Množina je rekurzivně spočetná, jestliže existuje program, který se zastaví právě na jejích prvcích. Je-li množina rekurzivní, je i rekurzivně spočetná, opačně to neplatí.

Definice ($dom,rng$)

V následujícím $dom$ značí definiční obor, $rng$ obor hodnot.

Definice ($x$-tá rekurzivně spočetná množina)

$W_x$ ($x$-tá rekurzivně spočetná množina) $=dom({\phi }_x)=\{y:{\phi }_x(y)\downarrow \}$

Definice (K)

$K=\{x:x\in W_x\}=\{x:{\phi }_x(x)\downarrow \}=\{x:{\Psi }_1(x,x)\downarrow \}$

Množina $K$ vlastně odpovídá <Státnice%20-%20Algoritmicky%20nerozhodnutelné%20problémy>. Platí o ní následující tvrzení.

Věta (Rekurzivní spočetnost $K$)

Množina $K$ je rekurzivně spočetná, není rekurzivní, $\overline{K}$ není rekurzivně spočetná.

Důkaz

$K$ není rekurzivní, neboť $\overline{K}$ není rekurzivně spočetná. $\overline{K}$ není rekurzivně spočetná, neboť kdyby byla, měla by index $x_0$. Jednoduchou diagonalizací dostáváme $x_0\in \overline{K}\iff x_0\in W_{x_0}\iff x_0\in K$. Spor.

1-převeditelnost, m-převeditelnost

Definice ($1$-převeditelnost, $m$-převeditelnost, $1$-úplnost, $m$-úplnost)

• Množina $A$ je 1-převedilná na $B$ (značíme $A{\le }_{1}B$), jestliže existuje prostá ORF $f$ taková, že $x\in A\iff f(x)\in B$.

• Množina $A$ je $m$-převedilná na $B$ (značíme $A{\le }_{m}B$), jestliže existuje ORF $f$ (ne nutně prostá) taková, že $x\in A\iff f(x)\in B$.

• Množina $M$ je 1-úplná, jestliže $M$ je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převedilná.

• Množina $M$ je $m$-úplná, jestliže $M$ je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni m-převedilná.

Věta (1-úplnost $K$)

$K$ je 1-úplná. Tedy halting problem je vzhledem k $1$ a $m$-převoditelnosti nejtěžší mezi rekurzivně spočetnými problémy.

Důkaz

Mějme libovolnou rekurzivně spočetnou množinu $W_x$.

Mějme ČRF $\alpha (y,x,w)$, popisující $x$-tou rekurzivně spočetnou množinu. Tedy $\alpha (y,x,w)\downarrow \iff y\in W_x\iff {\Psi }_1(x,y)\downarrow \iff {\phi }_x(y)\downarrow .$ $w$ je tady fiktivní proměnná, funkce $\alpha$ na její hodnotě nezáleží. Z s-m-n věty dostáváme: $\alpha (y,x,w)\simeq {\Psi }_3(a,y,x,w)\simeq {\Psi }_1(s_2(a,y,x),w)\simeq {\phi }_{s_2(a,y,x)}(w).$ Označme $h(y,x)=s_2(a,y,x)$ ($s_2$ je PRF, tím spíše ORF). $y\in W_x\iff \alpha (y,x,w)\downarrow \iff {\phi }_{h(y,x)}(w)\downarrow \iff {\phi }_{h(y,x)}(h(y,x))\downarrow \iff h(y,x)\in K$ Zde jsme mohli za $w$ dosadit $h(y,x)$, neboť hodnota $\alpha$ na $w$ nezáleží! Tedy $W_x{\le }_{1}K$ pomocí funkce $\lambda y:h(y,x)$.

Lemma ($K_0$ je 1-úplná)

$K_0=\{⟨y,x⟩:y\in W_x\}$ je 1-úplná.

Důkaz

Zřejmé. $K{\le }_1{K}_0$ a $K$ je $1$-úplná.

Lemma (Poznámky k 1-převeditelnosti)

1. Relace ${\le }_1$ a ${\le }_m$ jsou tranzitivní, reflexivní.

2. $A{\le }_{1}B\Rightarrow A{\le }_{m}B$

3. $B$ rekurzivní, $A{\le }_{m}B\Rightarrow A$ rekurzivní.

4. $B$ rekurzivně spočetná, $A{\le }_{m}B\Rightarrow A$ rekurzivně spočetná.

Důkaz

1. Zřejmé.

2. Zřejmé.

3. Složením funkce dokazující ${\le }_m$ s procedurou, která rozhoduje o $x\in B$, dostaneme proceduru rozhodující o $x\in A$. Dostáváme $c_A(x)=c_B(f(x))$.

4. Stejně.

Důsledek

$K$ a $\overline{K}$ jsou $m$-nesrovnatelné.

Důkaz

Plyne z faktu, že $K$ je rekurzivně spočetná, $\overline{K}$ není, a z bodu 4 předchozího lemma.

Definice (Rekurzivní permutace)

Permutace na $\mathbb{N}$, která je ORF, se nazývá rekurzivní permutace.

Definice (Rekurzivní isomorfismus)

Množiny $A$ a $B$ jsou rekurzivně isomorfní, jestliže existuje rekurzivní permutace $p$ taková, že $p(A)=B$. Značíme $A\equiv B$.

Definice (1-ekvivalence a m-ekvivalence)

• $A{\equiv }_{1}B$, jestliže $A{\le }_{1}B\wedge B{\le }_{1}A$.

• $A{\equiv }_{m}B$, jestliže $A{\le }_{m}B\wedge B{\le }_{m}A$.

Věta (Myhillova)

$A\equiv B\iff A{\equiv }_{1}B$

Důkaz

Jedná se o vlastně o obdobu wen:Cantor–Bernstein–Schroeder%20theorem.

$\Rightarrow$ Triviální.

$\Leftarrow$ Z předpokladů máme dvě prosté ORF $f,g$ převádějící vzájemně $A$ na $B$ a opačně. Chceme sestrojit rekurzivní permutaci $h$ takovou, že $h(A)=B$.

Plán: v krocích budeme generovat graf $h$ tak, že v kroku $n$ bude platit $\{0,\dots ,n\}\subseteq dom(h),\{0,\dots ,n\}\subseteq rng(h).$

Z toho plyne, že $h$ bude definovaná na celém $\mathbb{N}$ a bude na. Současně zajistíme, že $h$ bude prostá.

Navíc budeme chtít, aby platilo $y\in A\iff h(y)\in B$, tedy aby $h$ převáděla $A$ na $B$.

Začneme v bodě 0 a položíme $h(0)=f(0)$. Rozlišíme následující případy:

1. $f(0)=0$: vše je v pořádku, $h(0)=f(0)=0$ a $0\in A\iff 0\in B$, pokračujeme dalším prvkem.

2. $f(0)\ne 0$: rozlišíme dva podpřípady

   1. $g(0)\ne 0$: definujeme $h(g(0))=0$. Tedy $0\in dom(h)\cap rng(h)$.

   2. $g(0)=0$: nemůžeme použít $h(g(0))=0$, protože v bodě 0 je již $h$ definována. Najdeme tedy volný bod: definujme $h(g(f(0)))=0$. Určitě $g(f(0))\ne 0$, protože $g$ je prostá a $f(0)\ne 0$. Tímto jsme opět dostali bod 0 do definičního oboru $h$ i oboru hodnot. Zároveň funkci $h$ definujeme podle $f$ a $g$, tedy převádí vzájemně $A$ na $B$.

Indukční krok: nechť v kroku $k$ je $z$ první volný prvek. Všechna čísla menší než $z$ máme v $dom(h)\cap rng(h)$. Podíváme se, zda je $f(z)$ volný. Jestliže ano, položíme $h(z)=f(z)$. Jestliže $f(z)$ není volný, hledám "cik-cak" další volný (podobně jako pro $0$, maximálně $z$ prvků je blokovaných, tj. maximálně po $z$ iteracích tohoto postupu dojdu k volnému prvku).

Důsledek

$K\equiv K_0$.

Důkaz

Zřejmé, neboť $K{\equiv }_1{K}_0$ (obě množiny jsou 1-úplné).

Rekurzivně spočetné predikáty

Lemma (ORF $\to$ RSP)

Je-li $Q$ obecně rekurzivní predikát, potom $\exists y:Q$ je rekurzivně spočetný predikát.

Důkaz

${\mu }_{y}Q$ je ČRF, její definiční obor je $\{\exists y:Q\}$.

Věta (Univerzální RSP)

Predikát $\exists y{T}_k(e,x_1,\dots ,x_k,y)$ je univerzálním RSP pro třídu RSP $k$ proměnných, tj. lze definovat index (Gödelovo číslo) rekurzivně spočetného predikátu.

Důkaz

Z věty o normální formě -- numerace ČRF nám dává numeraci predikátů.

Věta (Log. spojky a rek. spočetnost)

Konjukce a disjunkce zachovávají rekurzivní spočetnost. Tedy průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.

Důkaz

Pro průnik spustíme oba programy současně a čekáme, až se oba zastaví. Pro sjednocení čekáme, až se zastaví alespoň jeden.

Formálně pro průnik ($(w{)}_{2,1}$ znamená to, že $w$ kóduje usp. dvojici a vybíráme z ní první prvek; to je PRF): $\exists s_1{T}_k(a,x,w_1)\wedge \exists s_2{T}_k(b,x,w_2)\iff \exists w(T_k(a,x,(w{)}_{2,1})\wedge T_k(b,x,(w{)}_{2,2}))$. Uvedený predikát je rekurzivně spočetný, tedy má nějaký index, tj. ekvivalence pokračuje: $\exists w{T}_{k+2}(e,a,b,x,w)\iff \exists w{T}_k(s_2(e,a,b),x,w)$

Poznámka

Konjunkce a disjunkce tedy rek. spočetnost zachovávají, o negaci (tj. doplňku) to ale už samozřejmě neplatí.

Věta (Kvantifikace a rek. spočetnost)

Omezená kvantifikace $(\forall y{)}_{y\le t}$ a existenční kvantifikace (pro $k\ge 2$) zachovávají rekurzivní spočetnost.

Důkaz

Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem.

Formálně: $(\forall y{)}_{y\le t}\exists s:T_k(e,x_1,\dots ,x_{k-1},y,s)\iff \exists$ kód $(t+1)$-tice $w:(\forall y{)}_{y\le t}{T}_k(e,x_1,\dots ,x_{k-1},y,(w{)}_{t+1,y})$.

$y$ můžeme zkoušet primitivní rekurzí, $w$ minimalizací, dostáváme tedy rekurzivně spočetný predikát, který má nějaký index $b$, dále můžeme použít S-m-n větu. $\exists s:T_{k+1}(b,e,x_1,\dots ,x_{k-1},t,s)\iff \exists s:T_k(s_1(b,e),x_1,\dots ,x_{k-1},t,s).$

Pro existenční kvantifikátor je situace ještě jednodušší. Kvantifikaci přes dvě proměnné převedeme na kvantifikaci přes jednu, kterou budeme považovat za kód dvojice a v predikátu potom vydělíme jednotlivé složky (a použijeme opět S-m-n větu). Dostáváme predikát $k-1$ proměnných, proto je ve větě požadavek na minimální velikost $k\ge 2$.

:$\exists y:\exists s:T_k(e,x_1,\dots ,x_{k-1},y,s)\iff \exists w:T_k(e,x_1,\dots ,x_{k-1},(w{)}_{2,1},(w{)}_{2,2})$ :$\iff \exists s:T_k(b,e,x_1,\dots ,x_{k-1},s)\iff \exists s:T_{k-1}(s_1(b,e),x_1,\dots ,x_{k-1},s)$

Poznámka

Neomezená obecná kvantifikace ($\forall$) rekurzivní spočetnost nezachovává.

Věta (O selektoru)

Nechť $Q$ je RSP $k+1$ proměnných. Potom existuje ČRF $\phi$ $k$ proměnných taková, že:

:$\phi (x_1,\dots ,x_k)\downarrow \iff \exists y:Q(x_1,\dots ,x_k,y)$ :$\phi (x_1,\dots ,x_k)\downarrow \Rightarrow Q(x_1,\dots ,x_k,\phi (x_1,\dots ,x_k))$

Věta říká, že pro každý rekurzivně spočetný predikát existuje ČRF taková, že konverguje, právě když existuje $y$ splňující predikát. Tato funkce navíc přímo vrací jedno takové $y$, pro které predikát platí. Tato $\phi$ je selektor na grafu $Q$.

Důkaz

Dáno $x$, hledáme nejmenší dvojici $(y,s)$ takovou, že za $s$ kroků ověříme, že $Q(x,y)$ (tj. program pro $Q$ konverguje za $s$ kroků). Pak vydáme $y$.

Obecně: univerzální vyjádření RSP $\exists s:T_{k+1}(e,x,y,s)$, hledáme nejmenší $w$ (kód dvojice) takové, že $\phi (x)\simeq ({\mu }_w{T}_{k+1}(e,x,(w{)}_{2,1},(w{)}_{2,2}){)}_{2,1}.$ Funkce $\phi$ vrací první složku z první dvojice, kterou najde (v uspořádání daném naším kódováním dvojic).

Věta (Vztah ČRF a RS grafů)

Funkce je ČRF $\iff$ má rekurzivně spočetný graf.

Důkaz

Je-li $\phi$ ČRF, je její graf rekurzivně spočetný:

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 37: …k,y\rangle \in \̲m̲b̲o̲x̲{Graf} \Leftrig…

Opačně, je-li graf funkce $\phi$ rekurzivně spočetný, je selektor na něm ČRF, ale selektor na grafu funkce je přímo ona funkce.

Věta (Postova)

Množina $M$ je rekurzivní, právě když $M$ i $\overline{M}$ jsou rekurzivně spočetné.

Predikát $Q$ je ORP, právě když $Q$ i $\neg Q$ jsou RSP.

Důkaz

"$\Rightarrow$": Triviální.

"$\Leftarrow$": Intuitivně: $M=dom(P_1)$, $\overline{M}=dom(P_2)$. Pustíme oba programy současně a čekáme, který se zastaví. Zastaví se právě jeden.

Formálně: $(x\in M\wedge y=1)\vee (x\in \overline{M}\wedge y=0)$ je rekurzivně spočetný predikát, selektor na něm je ORF, která je charakteristickou funkcí pro $M$.

Generování rekurzivně spočetných množin

Lemma (Rek. spočetná množina je obor hodnot ČRF)

Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.

Důkaz

Pro každou množinu $W_x$ vytvoříme množinu dvojic $R=\{⟨y,y⟩:y\in W_x\}$. Množina $R$ je rekurzivně spočetná, tedy má ČRF selektor $\phi$, platí $dom(\phi )=rng(\phi )=W_x$.

Myšlenka toho důkazu je, že body, kde ${\phi }_x$ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude zárověň jeho oborem hodnot.

Věta (ČRF odpovídá Rek. spočetným množinám)

Každý obor hodnot ČRF je rekurzivně spočetná množina.

Důkaz

Máme ČRF $g$ a její obor hodnot. Zkonstruujeme pseudoinverzní funkci $h$ k ČRF $g$, tj. funkci takovou, že $dom(h)=rng(g)$ a to tak, že vyrobíme RS predikát $Q(x,y)\iff g(x)\simeq y$ a to má ČRF selektor, který hledáme -- $h$.

Definice (Úseková funkce)

Funkce $f$ je úseková, jestliže jejím definičním oborem je počáteční úsek $\mathbb{N}$ (nebo celé $\mathbb{N}$).

Věta (Rek. množiny a úsekové ČRF)

Rekurzivní množiny jsou právě obory hodnot rostoucích úsekových ČRF.

Důkaz

$\Rightarrow$: Definujeme ČRF $f$, která bude rostoucí a úseková.

• Začneme $f(0)\simeq {\mu }_x(x\in M)$.

• Dále $f(n+1)\simeq {\mu }_y(y>f(n)\wedge y\in M)$

$\Leftarrow$: Máme $f$ rostoucí úsekovou ČRF.

1. V případě, že je $f$ má konečné $dom$ (tohle ale nejsme schopni efektivně rozpoznat!), víme jak, známe $D=dom(f)$ a tedy $rng(f)$ je rekurzivní.

2. V případě, že je $f$ je všude definovaná (totální): $y\in M=rng(f)\iff \exists x:(f(x)=y))\iff \exists x\le y:(f(x)=y)$ Poslední ekvivalence platí, protože $f$ je rostoucí a úseková. Tedy $y\in M\iff y\in \{f(0),\dots ,f(y)\}.$

Věta (O generování)

Mějme nekonečnou množinu $M$. Potom:

• Množina $M$ je rekurzivní, právě když $M$ lze generovat rostoucí ORF.

• Množina $M$ je rekurzivně spočetná, právě když $M$ lze generovat prostou ORF.

Důkaz

Důsledek předchozí, resp. následující věty.

Věta (Rek. spočetné množiny a prosté úsekové ČRF)

Rekurzivně spočetné množiny jsou právě obory hodnot prostých úsekových ČRF.

Důkaz

"$\Leftarrow$": Víme, obor hodnot ČRF je rekurzivně spočetná množina (z věty <#ČRF%20odpovídá%20Rek.%20spočetným%20množinám>).

"$\Rightarrow$": Mějme ČRF $\phi$ ($M=rng(\phi )$ pro nějaké $\phi$, z lemmatu <#Lemma%20%28Rek.%20spočetná%20množina%20je%20obor%20hodnot%20ČRF%29>).

Důkaz provedeme pomocí rekurzivní množiny $B=\{⟨x,s⟩:\phi (x)\downarrow$ přesně za $s$ kroků $\}$. Je vidět, že každé $x$ bude pouze v jednom z párů $⟨x,s⟩$.

Množinu $B$ lze, protože je rekurzivní, generovat pomocí rostoucí úsekové ČRF $h$. Funkce $h$ generuje dvojice, definujeme tedy $g(x)\simeq (h(x){)}_{2,1}$. Zřejmě $g$ je prostá, úseková a ČRF (a generuje $rng(\phi )$).

Důsledek

Každá nekonečná rekurzivně spočetná množina obsahuje nekonečnou rekurzivní podmnožinu.

Důkaz

Mějme $f$, která prostě generuje $M$. Vyber rostoucí podposloupnost. Ta je rekurzivní.

:$g(0)=f(0)$ :$g(n+1)=f({\mu }_j(f(j)>g(n)))$

Obor hodnot $g$ je nekonečná rekurzivní množina a je podmnožinou $M$.

{{Statnice I3}}