{{Template:TIN064 Skripta}} *def: Množina A je 1-převeditelná na B (značíme A≤1B A \le_1 B), jestliže existuje prostá ORF f taková, že x∈A⇔f(x)∈B x \in A \Leftrightarrow f(x) \in B.

*def: Množina A je m-převeditelná na B (značíme A≤mB A \le_m B), jestliže existuje (ne nutně prostá) ORF f taková, že x∈A⇔f(x)∈B 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: WxW_x (x-tá rekurzivně spočetná množina) =

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 39: …, \varphi_x(y) \̲m̲b̲o̲x̲{je definována}…

  • důležitá definice, WxW_x už budeme používat skoro pořád!

  • φx\varphi_x je x-tá ČRF

*def: K={x,x∈Wx}K = \{x, x \in W_x\}

  • Jinými slovy

    ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 19: …, \varphi_x(x) \̲m̲b̲o̲x̲{je definovana}…

    , tedy

    ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 18: …x, \psi_1(x,x) \̲m̲b̲o̲x̲{je definovana}…

  • ψ1\psi_1 je univerzální funkce z Kleeneho věty

*def: K0={<y,x>∣ y∈Wx}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 ψ1(x,x)\psi_1(x,x) (f zkonstruujeme pomocí substituce atd.), K je definičním oborem f.

  • Nechť doplněk K je RSM. Pak ∃x0:Kˉ=Wx0\exists x_0 : \bar{K} = W_{x_0}. Pokud x0∈Kˉx_0 \in \bar{K}, pak x0∈Wx0x_0 \in W_{x_0}, pak x0∈Kx_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 WxW_x, vezmu ČRF fci α(y,x,w)\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 α(y,x,w)↓⇔y∈Wx\alpha(y,x,w)\downarrow \Leftrightarrow y \in W_x *Vyjádřím si alfu pomocí univerzální funkce ψ3(a,y,x,w)\psi_3(a,y,x,w)

*s-m-n větou ψ1(s2(a,y,x),w)\psi_1(s_2(a,y,x),w) (s2s_2 je z Kleeneho věty PRF (tedy i ORF) a prostá) *Položme h(y,x)=s2(a,y,x)h(y,x) = s_2(a,y,x)

*∀y∈Wx:α(y,x,w)↓⇔φh(y,x)(w)↓⇔φh(y,x)(h(y,x))↓⇔h(y,x)∈K\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 ww dosadit h(y,x)h(y, x), neboť hodnota α\alpha na ww nazáleží

*Tedy WxW_x je 1-převeditelná na K pomocí funkce h(y,x)h(y,x)

EDIT (Ivan): Mně to přijde hezčí takto:

  • Chceme pro libovolné x ukázat, že Wx=dom(φx)≤1KW_x = dom(\varphi_x) \leq_1 K. Chceme najít prostou ORF h(y) takovou, že y∈Wx⇔h(y)∈Ky \in W_x \Leftrightarrow h(y) \in K, což dle definice K platí, právě když h(y)∈Wh(y)⇔Ψ1(h(y),h(y))↓h(y) \in W_{h(y)} \Leftrightarrow \Psi_1(h(y),h(y)) \downarrow.

  • φx(y)≃Ψ1(x,y)≃Ψ2(e,y,w)≃Ψ1(s1(e,y),w)\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)≃s1(e,y)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 WxW_x vezměme její popisující ČRF φx\varphi_x.

  • Definujme funkci dvou proměnných α\alpha(y,w) podle předpisu α\alpha(y,w)↓ \downarrow = φx(y)\varphi_x(y).

    • Tato funkce je jistě ČRF, buď tedy ee její index.

    • Proměnná ww 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í (*): α(y,w)≃ψ2(e,y,w)≃ψ1(s1(e,y),w)≃φs1(e,y)(w)\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=s1(e,y)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: K0K_0 je 1-úplná

Důkaz: Převodem KK na K0K_0. Předpis může být f(x)=(x,x)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 KK souvisí s Halting problémem (viz definice rekurzivně spočetné množiny) – kdyby KK byla rekurzivní => by bylo možné díky tomu, že KK je 1-převoditelná na K0K_0, rozhodnout halting problém.