TIN064 Převeditelnost

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
  • 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.