TIN064 Převeditelnost

Wiki-skripta pro Vyčíslitelnost I
Obsah
Úvod (náhled do problematiky) Prerekvizity (co je dobré vědět předem) ČRF, ORF, PRF Rekurzivní spočetnost Převeditelnost RSM Generování RSM Imunní a simple množiny Věty o rekurzi Produktivní a kreativní množiny Neoddělitelné množiny Gödelova věta Seznam zkratek

• 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á, jelikož je def. oborem $ \psi_1(x) $, 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 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 (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 $ 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 indexem $ s_1 $(e,y) (w)
• Položme h(y) = $ 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 $ s indexem h(y) (w)$ \downarrow $$ \Leftrightarrow $$ \varphi $ s indexem h(y) (h(y))$ \downarrow $$ \Leftrightarrow $ h(y) $ \in $ W s indexem 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 $

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řeveditelná na $ K_0 $, rozhodnout halting problém.