{{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 <math>K</math> je rekurzivně spočetná, ale není rekurzivní a její doplněk není rekurzivně spočetný
'''Důkaz:'''
* <math>K</math> je rek. spočetná, jelikož je def. oborem <math>\psi_1(x)</math>, která je ČRF
* Doplněk není rekurzivně spočetný, důkaz sporem pomocí Cantorovy diagonální metody, nebo klasicky vezmeme-li charakteristickou funkci doplňku a dosadíme do ní její vlastní kód.
'''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 (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): Taky mi z nějakýho důvodu nefunguje math syntax u výrazů, který ještě nejsou vyrenderovaný. Asi by se měl kontaktovat nějakej správce, jestli tu nějakej je. Z tohoto důvodu to bude trošku neesteticky.'''
'''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</math>(y).
** 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</math>(y,w) <math> \simeq </math> <math>\psi_2</math>(e,y,w) <math> \simeq </math> <math>\psi_1</math>(<math>s_1</math>(e,y), w) <math> \simeq </math> <math>\varphi</math> ''s indexem <math>s_1</math>(e,y)'' (w)
* Položme h(y) = <math>s_1</math>(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 <math>y \in W_x</math> <math> \Leftrightarrow </math> <math>\alpha</math>(y,w)<math>\downarrow </math><math> \Leftrightarrow </math> <math> \varphi </math> ''s indexem h(y)'' (w)<math>\downarrow </math><math> \Leftrightarrow </math><math> \varphi </math> ''s indexem h(y)'' (h(y))<math>\downarrow </math><math> \Leftrightarrow </math> h(y) <math> \in </math> W ''s indexem h(y)''<math> \Leftrightarrow </math> h(y) <math> \in </math> <math>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>
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řeveditelná na <math>K_0</math>, rozhodnout halting problém.
