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

*def: Množina A je m-převeditelná na B (značíme $A{\le }_{m}B$), jestliže existuje (ne nutně prostá) ORF f taková, že $x\in A\iff f(x)\in B$. *def: Množina A je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ní 1-převeditelná

*def: Množina A je m-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ní m-převeditelná

Užitečné rekurzivně-spočetné množiny

Abychom měli na co převádět, hodí se mít nějaké šikovné třídy funkcí.

*def: $W_x$ (x-tá rekurzivně spočetná množina) =

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 39: …, \varphi_x(y) \̲m̲b̲o̲x̲{je definována}…

• důležitá definice, $W_x$ už budeme používat skoro pořád!

• ${\phi }_x$ je x-tá ČRF

*def: $K=\{x,x\in W_x\}$

• Jinými slovy

  ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 19: …, \varphi_x(x) \̲m̲b̲o̲x̲{je definovana}…

  , tedy

  ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 18: …x, \psi_1(x,x) \̲m̲b̲o̲x̲{je definovana}…

• ${\psi }_1$ je univerzální funkce z Kleeneho věty

*def: $K_0=\{<y,x>|y\in W_x\}$

Vlastnosti množiny K

Věta: Množina K je rekurzivně spočetná, ale není rekurzivní a její doplněk není rekurzivně spočetný

Důkaz:

• K je rek. spočetná. Jistě existuje ČRF f(x), která bude vyčíslovat ${\psi }_1(x,x)$ (f zkonstruujeme pomocí substituce atd.), K je definičním oborem f.

• Nechť doplněk K je RSM. Pak $\exists x_0:\bar{K}=W_{x_0}$. Pokud $x_0\in \bar{K}$, pak $x_0\in W_{x_0}$, pak $x_0\in K$ (z definice K). Spor.

Věta: K je 1-úplná

Důkaz:

*K je rekurzivně spočetná viz definice, dále vezmu libovolnou rek. spočetnou množinu $W_x$, vezmu ČRF fci $\alpha (y,x,w)$, popisující x-tou RSM.

• Pro každou rek.spoč. množinu existuje ČRF, jejímž definičním oborem je daná množina

• Proměnná w je fiktivní proměnná – běžný trik pro obejití nulárnosti

*Tedy $\alpha (y,x,w)\downarrow \iff y\in W_x$ *Vyjádřím si alfu pomocí univerzální funkce ${\psi }_3(a,y,x,w)$

*s-m-n větou ${\psi }_1(s_2(a,y,x),w)$ ($s_2$ je z Kleeneho věty PRF (tedy i ORF) a prostá) *Položme $h(y,x)=s_2(a,y,x)$

*$\forall y\in W_x:\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$ nazáleží

*Tedy $W_x$ je 1-převeditelná na K pomocí funkce $h(y,x)$

EDIT (Ivan): Mně to přijde hezčí takto:

• Chceme pro libovolné x ukázat, že $W_x=dom({\phi }_x){\le }_{1}K$. Chceme najít prostou ORF h(y) takovou, že $y\in W_x\iff h(y)\in K$, což dle definice K platí, právě když $h(y)\in W_{h(y)}\iff {\Psi }_1(h(y),h(y))\downarrow$.

• ${\phi }_x(y)\simeq {\Psi }_1(x,y)\simeq {\Psi }_2(e,y,w)\simeq {\Psi }_1(s_1(e,y),w)$. Položme $h(y)\simeq s_1(e,y)$.

• Uměle jsme přidali proměnnou w, nemající vliv na hodnotu funkce. h(y) je prostá ORF, dokonce rostoucí.

• $y \in W_x \Leftrightarrow \varphi_x(y) \downarrow \Leftrightarrow \Psi_1(h(y),w) \downarrow

\Leftrightarrow \Psi_1(h(y),h(y)) \downarrow \Leftrightarrow h(y) \in K$

• h(y)-tá funkce jedné proměnné je vlastně konstantní, všude definovaná, tedy h(y) musí být v K.

EDIT (Jindra): Myslím si, že to jde víc jednoduše - bez použití proměnné x uvnitř důkazu (viz následující důkaz):

Alternativní důkaz:

• K je RSM, což je dokázáno v předchozí větě. Pro libovolnou RSM $W_x$ vezměme její popisující ČRF ${\phi }_x$.

• Definujme funkci dvou proměnných $\alpha$(y,w) podle předpisu $\alpha$(y,w)$\downarrow$ = ${\phi }_x(y)$.

  • Tato funkce je jistě ČRF, buď tedy $e$ její index.

  • Proměnná $w$ je použita stejně jako v původním důkazu, tedy jako fiktivní proměnná, na jejíž hodnotě výsledná hodnota funkce nezávisí.

• Platí (*): $\alpha (y,w)\simeq {\psi }_2(e,y,w)\simeq {\psi }_1(s_1(e,y),w)\simeq {\phi }_{s_1(e,y)}(w)$

• Položme $h=s_1(e,y)$.

  • Tato funkce je podle s-m-n věty prostá a rostoucí ve všech proměnných (nám stačí to, že je prostá).

• Potom $y \in W_x

\Leftrightarrow \alpha(y,w)\downarrow \Leftrightarrow \varphi_{h(y)}(w)\downarrow

\Leftrightarrow \varphi_{h(y)}(h(y))\downarrow \Leftrightarrow h(y) \in W_{(h(y)}

\Leftrightarrow h(y) \in K$

• První ekvivalence plyne z definice funkce $\alpha$, druhá z řádku označeného (*), další z toho, že w je fiktivní proměnná a tudíž za ní lze dosadit cokoliv, aniž by se změnil výsledek. Předposlední ekvivalenci dostáváme ze vztahu x-té ČRF a x-té RSM a poslední plyne přímo z definice množiny K.

$\square$

EDIT (Jindra): Rozdíl mezi původním a alternativním důkazem je v tom, že alternativní důkaz pro každou RSM W (s indexem x) hledá funkci h, a pro každou RSM jí taky najde. Důkaz původní dokazuje trochu silnější tvrzení, a to tak, že najde jednu funkci, která je pak převádějící funkcí pro všechny RSM najednou.

Věta: $K_0$ je 1-úplná

Důkaz: Převodem $K$ na $K_0$. Předpis může být $f(x)=(x,x)$ - zakóduji x do dvojice (x,x). Je důležité si uvědomit, že ačkoli je f totální a prostá, nemusí se "trefit" do všech bodů množiny napravo.

Množina $K$ souvisí s Halting problémem (viz definice rekurzivně spočetné množiny) – kdyby $K$ byla rekurzivní => by bylo možné díky tomu, že $K$ je 1-převoditelná na $K_0$, rozhodnout halting problém.