TIN064 Převeditelnost
| Wiki-skripta pro Vyčíslitelnost I |
| Obsah |
|---|
|
- 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 \Leftrightarrow 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 \Leftrightarrow 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) = $ dom( \varphi_x) = \{ y, \varphi_x(y) \mbox{je definována} \} $
- důležitá definice, $ W_x $ už budeme používat skoro pořád!
- $ \varphi_x $ je x-tá ČRF
- def: $ K = \{x, x \in W_x\} $
- Jinými slovy $ \{x, \varphi_x(x) \mbox{je definovana} \} $, tedy $ \{x, \psi_1(x,x) \mbox{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 \Leftrightarrow 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 \Leftrightarrow \varphi_{h(y,x)}(w)\downarrow \Leftrightarrow \varphi_{h(y,x)}(h(y,x))\downarrow \Leftrightarrow 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(\varphi_x) \leq_1 K $. Chceme najít prostou ORF h(y) takovou, že $ y \in W_x \Leftrightarrow h(y) \in K $, což dle definice K platí, právě když $ h(y) \in W_{h(y)} \Leftrightarrow \Psi_1(h(y),h(y)) \downarrow $.
- $ \varphi_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 $ \varphi_x $.
- Definujme funkci dvou proměnných $ \alpha $(y,w) podle předpisu $ \alpha $(y,w)$ \downarrow $ = $ \varphi_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 \varphi_{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.
$ \Box $
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.
