{{Template:TIN064 Skripta}}
*def: Množina '''A je 1-převeditelná na B''' (značíme <math> A \le_1 B</math>), jestliže existuje prostá ORF ''f'' taková, že <math> x \in A \Leftrightarrow f(x) \in B</math>.
*def: Množina '''A je m-převeditelná na B''' (značíme <math> A \le_m B</math>), jestliže existuje (ne nutně prostá) ORF ''f'' taková, že <math> x \in A \Leftrightarrow f(x) \in B</math>.
*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: <math>W_x</math> (x-tá rekurzivně spočetná množina) = <math> dom( \varphi_x) = \{ y, \varphi_x(y) \mbox{je definována} \} </math>
** důležitá definice, <math>W_x</math> už budeme používat skoro pořád!
** <math>\varphi_x </math> je x-tá ČRF
*def: <math>K = \{x, x \in W_x\}</math>
** Jinými slovy <math>\{x, \varphi_x(x) \mbox{je definovana} \}</math>, tedy <math>\{x, \psi_1(x,x) \mbox{je definovana}\}</math>
** <math>\psi_1</math> je univerzální funkce z Kleeneho věty
*def: <math>K_0 = \{<y, x> |\ y \in W_x\}</math>
===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 <math>\psi_1(x,x)</math> (f zkonstruujeme pomocí substituce atd.), K je definičním oborem f.
* Nechť doplněk '''K''' je RSM. Pak <math>\exists x_0 : \bar{K} = W_{x_0}</math>. Pokud <math>x_0 \in \bar{K}</math>, pak <math>x_0 \in W_{x_0}</math>, pak <math>x_0 \in K</math> (z definice '''K'''). Spor.
'''Věta:''' K je 1-úplná
'''Důkaz:'''
*K je rekurzivně spočetná viz [[TIN064_Vlastnosti_RSM|definice]], dále vezmu libovolnou rek. spočetnou množinu <math>W_x</math>, vezmu ČRF fci <math>\alpha(y,x,w)</math>, 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 <math>\alpha(y,x,w)\downarrow \Leftrightarrow y \in W_x</math>
*Vyjádřím si alfu pomocí univerzální funkce <math>\psi_3(a,y,x,w)</math>
*s-m-n větou <math>\psi_1(s_2(a,y,x),w)</math> (<math>s_2</math> je z Kleeneho věty PRF (tedy i ORF) a prostá)
*Položme <math>h(y,x) = s_2(a,y,x)</math>
*<math>\forall y \in W_x: \alpha(y,x,w)\downarrow \Leftrightarrow \varphi_{h(y,x)}(w)\downarrow \Leftrightarrow \varphi_{h(y,x)}(h(y,x))\downarrow \Leftrightarrow h(y,x) \in K</math>
** Zde jsme mohli za <math>w</math> dosadit <math>h(y, x)</math>, neboť hodnota <math>\alpha</math> na <math>w</math> nazáleží
*Tedy <math>W_x</math> je 1-převeditelná na K pomocí funkce <math>h(y,x)</math>
'''EDIT (Ivan)''': Mně to přijde hezčí takto:
* Chceme pro libovolné x ukázat, že <math>W_x = dom(\varphi_x) \leq_1 K</math>. Chceme najít prostou ORF h(y) takovou, že <math>y \in W_x \Leftrightarrow h(y) \in K</math>, což dle definice K platí, právě když <math>h(y) \in W_{h(y)} \Leftrightarrow \Psi_1(h(y),h(y)) \downarrow</math>.
* <math>\varphi_x(y) \simeq \Psi_1(x,y) \simeq \Psi_2(e,y,w) \simeq \Psi_1(s_1(e,y),w)</math>. Položme <math>h(y) \simeq s_1(e,y)</math>.
* Uměle jsme přidali proměnnou w, nemající vliv na hodnotu funkce. h(y) je prostá ORF, dokonce rostoucí.
* <math>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</math>
* 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 <math>W_x</math> vezměme její popisující ČRF <math>\varphi_x</math>.
* Definujme funkci dvou proměnných <math>\alpha</math>(y,w) podle předpisu <math>\alpha</math>(y,w)<math> \downarrow</math> = <math>\varphi_x(y)</math>.
** Tato funkce je jistě ČRF, buď tedy <math>e</math> její index.
** Proměnná <math>w</math> 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í (*): <math>\alpha(y,w) \simeq \psi_2(e,y,w) \simeq \psi_1(s_1(e,y),w) \simeq \varphi_{s_1(e,y)}(w)</math>
* Položme <math>h = s_1(e,y)</math>.
** 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 <math>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</math>
** První ekvivalence plyne z definice funkce <math>\alpha</math>, 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.
<math>\Box</math>
'''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:''' <math>K_0</math> je 1-úplná
'''Důkaz:''' Převodem <math>K</math> na <math>K_0</math>. Předpis může být <math>f(x) = (x,x)</math> - 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 <math>K</math> souvisí s Halting problémem (viz definice rekurzivně spočetné množiny) – kdyby <math>K</math> byla rekurzivní => by bylo možné díky tomu, že <math>K</math> je 1-převoditelná na <math>K_0</math>, rozhodnout halting problém.
