{{Template:TIN064 Skripta}}
* 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 </math> právě tehdy když <math> f(x) \in B</math>
* množina '''A je m-převeditelná na B''' (značíme <math> A \le_m B</math>), jestliže existuje ORF (ne nutně prostá) f taková, že <math> x \in A </math> právě tehdy když <math> 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>, která ji popisuje
** 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>
*Tedy <math>W_x</math> je 1-převeditelná na K pomocí funkce <math>h(y,x)</math>
'''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.
