Státnice - Informatika - Vyčíslitelnost: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
(Rekurzivně spočetné predikáty)
(Věty o rekurzi)
Řádka 538: Řádka 538:
 
:V předchozích větách jsme hledali pro ČRF zobrazení jeden pevný bod, pak pro vícerozměrné zobrazení parametrizovaný pevný bod. Tahle věta říká, že pro dané zobrazení můžou pevné body generovat prosto funkci.
 
:V předchozích větách jsme hledali pro ČRF zobrazení jeden pevný bod, pak pro vícerozměrné zobrazení parametrizovaný pevný bod. Tahle věta říká, že pro dané zobrazení můžou pevné body generovat prosto funkci.
  
'''Věta (o programu co vypíše sám sebe)''': Nechť <math>f(x, y_1, y_2, ... ,y_m)</math> je ČRF. Pak existuje ''a'' takové, že <math>\varphi_a(y_1, y_2, ..,y_m) \simeq f(a, y_1, y_2, ..., y_m)</math>.
+
'''Věta (o programu co vypíše sám sebe - Quine)''': Nechť <math>f(x, y_1, y_2, ... ,y_m)</math> je ČRF. Pak existuje ''a'' takové, že <math>\varphi_a(y_1, y_2, ..,y_m) \simeq f(a, y_1, y_2, ..., y_m)</math>.
 
:'''Důkaz''': Jelikož f je ČRF, platí <math>f(x, y_1, y_2, ... ,y_m) \simeq \Psi(e, x, y_1, y_2, ... ,y_m) \simeq^{s-m-n} \Psi(s_1(e, x), y_1, y_2, ... ,y_m) \simeq \varphi_{s_1(e,x)}(y_1, y_2, ..,y_m)</math>. Použijeme větu o rekursi na <math>s_1(e,x)</math> v proměnné ''x'' a dostáváme  <math>\varphi_{s(e,a)}(x) \simeq \varphi_a(x)</math> pro nějaký pevný bod ''a''.
 
:'''Důkaz''': Jelikož f je ČRF, platí <math>f(x, y_1, y_2, ... ,y_m) \simeq \Psi(e, x, y_1, y_2, ... ,y_m) \simeq^{s-m-n} \Psi(s_1(e, x), y_1, y_2, ... ,y_m) \simeq \varphi_{s_1(e,x)}(y_1, y_2, ..,y_m)</math>. Použijeme větu o rekursi na <math>s_1(e,x)</math> v proměnné ''x'' a dostáváme  <math>\varphi_{s(e,a)}(x) \simeq \varphi_a(x)</math> pro nějaký pevný bod ''a''.
  

Verze z 7. 2. 2010, 17:03

Tento souhrn slouží pro přípravu k magisterským státnicím. Detailní informace o předmětu hledej na stránkách Vyčíslitelnost I a Vyčíslitelnost II.

Rozsah látky

Státnicové otázky z vyčíslitelnosti jsou poměrně obecné a rozsáhlé. Dle Kučery by mělo platit, že přibližně pokrývají látku předmětu Vyčíslitelnost I [1]. Kromě toho Kučera soukromě mailem potvrdil, že není třeba znát pojmy imunní množina, simple množina a úplně produktivní množina ani tvrzení s nimi související.

Seznam oficiálních státnicových otázek pro studijní obory Teoretická informatika a Diskrétní modely a algoritmy:

Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Primitivně a částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. Algoritmicky nerozhodnutelné problémy. Věty o rekurzi a jejich aplikace. Gödelovy věty.

Studijní obory Softwarové systémy a Matematická lingvistika mají okruhy Složitost a Vyčíslitelnost do spojeny do okruhu jednoho:

Metody tvorby algoritmů: rozděl a panuj, dynamické programování, hladový algoritmus. Dolní odhady pro složitost třídění (rozhodovací stromy). Amortizovaná složitost. Úplné problémy pro třídu NP, Cook-Levinova věta. Pseudopolynomiální algoritmy, silná NP-úplnost. Aproximační algoritmy a schémata. Algoritmicky vyčíslitelné funkce, jejich vlastnosti, ekvivalence jejich různých matematických definic. Částečně rekurzivní funkce. Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti. Algoritmicky nerozhodnutelné problémy (halting problem). Věty o rekurzi a jejich aplikace: příklady, Riceova věta.

Algoritmicky vyčíslitelné funkce, jejich vlastnosti

see wen:Computable function

Definice se vždy odkazuje na některý z výpočetních modelů efektivně vyčíslitelné = turingovsky vyčíslitelné = algoritmicky vyčíslitelné = algoritmicky řešitelné atd. Jedna z ekvivalentních definic tedy je:

Aritmetická funkce $ f:\mathbb{N} \rightarrow \mathbb{N} $ je (turingovsky) vyčíslitelná pokud existuje Turingův stroj, který ji vyčísluje.

Ekvivalence různých matematických definic

wen:Turing machine equivalents


Matematické modely

Turingův stroj, definice

Turingův stroj je šestice $ M=(Q, \Gamma, s, b, F, \delta) $ kde :

  • $ Q $ je konečná množina vnitřních stavů
  • $ \Gamma $ je konečná abeceda symbolů a znaků
  • $ s\in Q $ je počáteční stav
  • $ b\in \Gamma $ je symbol reprezentující prázdný symbol ( $ b $ neni součástí vstupní abecedy přijímaného řetězce)
  • $ F\subseteq Q $ je množina koncových stavů
  • $ \delta: \{Q - q_f \in F\}\times\Gamma\rightarrow Q\times\Gamma \times \{L,N,R\} $ přechodová funkce, kde:
    • $ L $ znamená posun čtecí hlavy vlevo
    • $ R $ znamená posun čtecí hlavy vpravo
    • $ N $ znamená neposunutí čtecí hlavy

ČRF, definice

Viz níž.

Postovy systémy, definice

Postův systém je trojice (m, A, P), kde

  • m je kladné celé číslo (deletion number).
  • A je konečná abeceda symbolů, jeden ze symbolů je koncový symbol (halting symbol) halting symbol. Slova jsou konečné posloupnosti symbolů z A.
  • P je množina přepisovacích pravidel (production rules), přiřazujících každému symbolu x z A slovo P(x) (production). Produkce (P(H)). Zastavovacímu symbolu (kro transparentnost) je přiřazeno slovo následovně: P(H) = 'H', ikdyž to nehraje roli.

2-tag system (m=2)
    m=2
    Alphabet: {a,b,c,H} 
    Production rules:
         a  -->  ccbaH
         b  -->  cca
         c  -->  cc

# Computation: podle nejlevějšího písmene použij pravidlo: odmaž m=2 nejlevějších písmen 
# a připoj pravou stranu přepisovacího pravidla

    Initial word: baa
                    acca
                      caccbaH
                        ccbaHcc
                          baHcccc
                            Hcccccca (halt).

Lambda kalkulus, definice

Lambda výraz se skládá z

Proměnných v1, v2, . . . vn
abstrahujícího symbolu λ and .
závorek ( )

Množina lambda výrazů, Λ, je definována rekursivně:

  1. Pokud x je proměnná, pak x ∈ Λ
  2. Pokud x je proměnná a M ∈ Λ, pak ( λ x . M ) ∈ Λ
  3. Pokud M, N ∈ Λ, pak ( M N ) ∈ Λ


0 := λ f x. x
1 := λ f x. f x
2 := λ f x. f (f x)
3 := λ f x. f (f (f x))

SUCC := λ n f x. f (n f x)
PLUS := λ m n f x. n f (m f x)

RAM programy, definice

RAM stroj se sklálá z registrů, ke kterým máme přímý přístup. RAM program se pak skládá z instrukcí čtyř typů:

  1. $ L R_i <- R_i + 1 $
  2. $ L R_i <- R_i - 1 $
  3. $ L R_i $ jump (M,N)
  4. continue,

kde L je návěští (má tvar "k:", k přirozené, je nepovinné), $ R_i $ je registr s adresou i, M,N jsou konkrétní návěstí použitá v programu.

Práce RAM stroje probíhá instrukce v pořadí v jakém jsou zapsané (s výjimkou instrukce 4 - tedy jump). Význam jednotlivých instrukcí je tento:

  1. zvýší se hodnota v poli $ R_i $ o jedničku
  2. sníží se hodnota v poli $ R_i $ o jedničku
  3. test na hodnotu v poli $ R_i $; pro kladnou hodnotu skoč na instrukci s návěstím M, pro 0 instrukce s návěstím N.
  4. continue nic nedělá, pouze oznamuje konec práce.

RAM porgram vyčísluje fci n proměnných takto: Vstupem je n-tice zadaná v registrech $ R_1,...,R_n $. Pokud je fce pro tuto n-tici definovaná, RAM program skončí a v registru $ R_1 $ bude funkční hodnota.

Ekvivalence TS a ČRF

Viz wiki skripta - ekvivalence, UTS.

Důkazy ostatních definicí

Na přednášce nebylo...

Vlastnosti efektivně vyčístlitelných funkcí

Postova věta

(wen:Post's theorem), a uzavřenost PRF, ORF a ČRF na doplněk (ČRF ne), sjednocení, průnik, omezená kvantifikace, kvantifikace

Inkluze v ČRF, ORF, PRF

Neostré inkluze

Je zřejmé, že každá ORF je ČRF a že i každá PRF je ČRF. Základní funkce jsou totální a operátory substituce a primitivní rekurze totálnost zachovávají. PRF tedy musí být totální. Tím jsme dokázali, že $ \mbox{PRF} \subseteq \mbox{ORF} \subseteq \mbox{ČRF} $

Ostré inkluze

Platí: $ \mbox{PRF} \subsetneq \mbox{ORF} \subsetneq \mbox{ČRF} $.

  • ČRF, která není ORF

Chceme najít nějakou netotální ČRF. Zkonstruujeme tedy například funkci f, která není nikde definovaná (tzv. prázdná funkce). K tomu budeme muset zjevně použít operátor minimalizace: f:=M(g), kde g je nějaká funkce, která nikdy nevrací nulu. Nejjednodušší by bylo vzít jako g rovnou následníka, tedy $ f:=M_0(\mathbf{s}) $. Problém je, že jsme si nezavedli nulární funkce (a tou by f byla).

Zvolme tedy $ g:=S^1_2(\mathbf{s},\mathbf{I^2_2}) $, což znamená, že $ g(x,y)=y+1 $ (na první proměnné nezáleží). Pak máme $ f:=M_1(g) $, dohromady tedy $ f:=M_1\big(S^1_2(\mathbf{s},\mathbf{I^2_2})\big). $

  • ORF, která není PRF

Příkladem takové funkce je Ackermannova funkce nebo univerzální funkce pro třídu PRF.

A(0,n) = n + 1
A(m,0) = A(m-1,1)
A(m,n) = A(m-1,A(m,n-1)); m>0 && n>0
  • důkaz (resp. myšlenka důkazu), že Ackermannova fce je ORF, ale není PRF (TODO nejsem si jistej, že tomu rozumim správně)
  1. A(x,y) je ORF
    1. A je totální (je všude definovaná na všech dvojicích ordinálních čísel omega^2)
    2. A je efektivně vyčíslitelná - ?? zastaví se program na vstupních datech?? zobrazíme vstupní data na dobré uspořádání (TODO def) a v průběhu programu klesáme, v dobrém uspořádání neexistuje nekonečný klesající řetězec a tedy program vždy skončí
    3. je A ČRF? (nějaký čachry s minimalizací)
  2. A není PRF
    1. definuje se "strukturální" složitost PR programů (nechť PR programy jsou PR termy - tj. základní fce, substituce, primitivní rekurze)
    2. definuje se hloubka PR-termů - maximální počet do sebe zanořených for-cyklů (operátorů rekurze)
      1. $ hl(s)=hl(o) = hl(I^j_n) = 0 $
      2. $ hl(S^m_n(f, g_1, g_2, ..., g_m)) = max(hl(f), hl(g_1), hl(g_2), ... hl(g_m)) $
      3. $ hl(R^n_n(f, g)) = max(hl(f), hl(g) + 1)) $
    3. definuje se třída funkcí $ R_i $ obsahující PR-programy hloubky nejvýše $ i $
    4. fce $ f_i $ je z ($ R_i $ \ $ R_{i-1} $) - je na ní potřeba aspoň $ i $ vnořených for-cyklů (s méně to nejde)
    5. sjednocení všech $ R_i $ je PRF
    6. teď se na $ A(x,y) $ nahlídne jako na množinu funkcí $ f_x(y) $ a dokáže se, že $ f_x(x) $ není z žádného $ R_i $
    7. $ A(x,y) $ je rostoucí na obou proměnných
    8. jakákoliv fce z $ R_i $ < jakákoliv fce z $ R_{i+1} $ (síla $ i $ vnořených cyklů je menší než síla $ i+1 $ vnořených cyklů)
    9. sporem, nechť $ A(x,x) $ je z PRF, pak je z nějakého $ R_i $, tedy musí být $ A(x,x) < f_{i+1}(x) < f_x(x) $, pro $ x>i+1 $ SPOR

Primitivně a částečně rekurzivní funkce

see wen:Primitive recursive function, wen:μ-recursive function

Částečně rekurzivní funkce

Základní funkce

  • nulová funkce

$ \mathbf{o}(x) = 0 \quad (\forall x) $

function nulova(x) { return 0; }
  • následník

$ \mathbf{s}(x) = x+1 \quad (\forall x) $

function succ(x) { return x+1; }
  • vydělení j-té složky

$ \mathbf{I^j_n}(x_1,...,x_n) = x_j \quad (\forall j,n: 1 \le j \le n) $

function selekce<j>($ x_1,...,x_n $) { return $ x_j $; }

Operátory

Všechny tři operátory mají v dolním indexu n, což značí, že výsledná funkce $ \mathbf{h} $ bude funkcí n proměnných.

  • substituce

$ S^m_n(\mathbf{f},\mathbf{g_1},...,\mathbf{g_m})=\mathbf{h} $, kde
$ \mathbf{h}(x_1,...,x_n) \simeq \mathbf{f}(\mathbf{g_1}(x_1,...,x_n),...,\mathbf{g_m}(x_1,...,x_n)) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce m proměnných a všechny $ \mathbf{g_i} $ jsou funkce n proměnných. Pokud zavedeme konvenci, že $ \vec x = (x_1,...,x_n) $, tak můžeme zjednodušeně psát $ \mathbf{h}(\vec x) \simeq \mathbf{f}(\mathbf{g_1}(\vec x),...,\mathbf{g_m}(\vec x)) $.

operator $ S^m_n $<$ \mathbf{f},\mathbf{g_1},...,\mathbf{g_m} $>($ x_1,...,x_n $){
  return $ \mathbf{f}(\mathbf{g_1} $($ x_1,...,x_n $), ... , $ \mathbf{g_m} $($ x_1,...,x_n $));
}

Operátor substituce je základní prvek programování (v lib. prog. jazyce, co znám) — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.

  • primitivní rekurze

$ R_n(\mathbf{f},\mathbf{g})=\mathbf{h} $, kde
$ \mathbf{h}(0,x_2,...,x_n) \simeq \mathbf{f}(x_2,...,x_n) $
$ \mathbf{h}(i+1,x_2,...,x_n) \simeq \mathbf{g}(i,\mathbf{h}(i,x_2,...,x_n),x_2,...,x_n) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce n-1 proměnných a $ \mathbf{g} $ je funkce n+1 proměnných.

operator $ R_n\! $<$ \mathbf{f},\mathbf{g} $>($ x_1,x_2,...,x_n $){
  pom := $ \mathbf{f} $($ x_2,...,x_n $);
  for i := 1 to $ x_1 $ do
    pom := $ \mathbf{g} $(i-1, pom, $ x_2,...,x_n $);
  return pom;
}

Je vidět, že operátor primitivní rekurze má sílu for-cyklu.

Proměnná $ x_1 $ má zvláštní význam — slouží jako čítač.

Na přednášce se uváděl vysvětlující příklad na primitivní rekurzi pro n=1. Pak h(0)=konstanta a h(i+1)=g(i,h(i)). Malý problém je v tom, že jsme si nedefinovali nulární funkce a f by v tomto případě musela mít n-1=0 proměnných.

  • minimalizace

$ M_n(\mathbf{f})=\mathbf{h} $, kde
$ \mathbf{h}(x_1,...,x_n)\downarrow = z \iff \big(\mathbf{f}(x_1,...,x_n,z)\downarrow = 0 \And \forall j<z: \mathbf{f}(x_1,...,x_n,j)\downarrow \ne 0\big) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce n+1 proměnných.

operator $ M_n\! $<$ \mathbf{f} $>($ x_1,...,x_n $){
  i:=0;
  while ($ \mathbf{f} $($ x_1,...,x_n $, i) != 0) do i++;
  return i;
}

Je vidět, že operátor minimalizace má sílu while-cyklu. Poslední proměnná ve funkci f (v pseudokódu označená jako i) má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší i takové, aby f vracela nulu.

Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná (výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostali na vstupu totální funkce, vrátili také totální funkci.

Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.


Příklad: sčítání dvou čísel

$ R_2(I^1_1,S^1_3(s,I^2_3)) $
Příklad: $ x_1=2; x_2=3; $
$ h(0,x_2)=I^1_1(x_2)=I^1_1(3)=3 $
$ h(1,x_2)=s(I^2_3(0,h(0,x_2),x_2))=s(I^2_3(0,3,3))=s(3)=4 $
$ h(2,x_2)=s(I^2_3(1,h(1,x_2),x_2))=s(I^2_3(1,4,3))=s(4)=5 $
Def Odvozeni funkce
posloupnost funkcí f0 .. fn = f, kde kazda funkce je bud základní funkce nebo vznikne použitím operátoru na predchozi funkce
Def Totální funkce
funkce je totální, pokud funkce (program) skončí na každem vstupu
Def Částečne rekurzivní funkce (ČRF)
funkce je částečně rekurzivní (ČRF), pokud má odvození.
Def Obecně rekurzivní funkce (ORF)
pokud je ČRF a je totální.
Def Primitivně rekurzivní (PRF)
pokud ma odvození pouze s použitím operatorů S_n^m a R_n (bez minimalizace, tj bez while cyklu)

$ PRF \subset ORF \subset CRF $ Důkaz výše.

Univerzální funkce

  • existuje univerzální ČRF pro každou třídu ČRF o k proměnných, která dostane na vstup kód fce (e) a k-proměnných a vydá výsledek e-té funkce (ta univerzální funkce je tvaru minimalizace PRP), viz Kleeneho věta.
  • třída PRF má svoji univerzální funkci, která ale sama do třídy PRF nepatří

důkaz sporem: Nechť U(x, x) je univerzální PRF, která počítá výstup x-té PRF na vstupu x. Pak U(x, x) + 1 je také PRF (použitím operátoru substituce a funkce následníka). Protože U je univerzální funkce, platí, že $ U(x, x) + 1 \simeq U(x_0, x) $ pro nějaké $ x_0 $. Nyní přichází klíčový krok důkazu, kdy za x dosadíme $ x_0 $ (tzn. wcs:Cantorova diagonální metoda) a dostáváme $ U(x_0, x_0) + 1 \simeq U(x_0, x_0) $, což je spor. Předpoklad, že U je primitivně rekurzivní funkce, byl tedy chybný. (TODO - na přednášce používal doc. Kučera operator "mínus s tečkou", definovaný jako x-y pro x>=y, a 0 pro x<y, nazývaný aritmetický rozdíl. Tento operátor zachovává totálnost.)

Def Univerzální funkce pro pro k proměnných (numerace)
funkce U je univerzální pro spočetnou přídu aritmetických funkcí k proměnných A, pokud
  • Pro každé $ e\; \lambda_{x_1, ..., x_k} U(e, x_1,..., x_k) $ patří do A
  • Pro každé $ f \in A $ existuje e tak, že $ f(x_1, x_2, ..., x_k) \simeq \lambda_{x_1, ..., x_k} U(e, x_1,..., x_k) $

e se nazývá index funkce

Def Gödelovská univerzální funkce

Univerzální funkce je gödelovská, jestliže

  • Je efektivně vyčíslitelná
  • index složené funkce funkce lze efektivně zjistit z indexů skládaných funkcí, tj. pokud existuje efektivně vyčístlitelná $ \alpha $, taková, že

$ U(p, U(q, x))\simeq U(\alpha(p, q), x) \simeq p \circ q (x) $

Kleenova věta

Def Kleeneho T predikát ( vystupuje v té větě)

Kleeneho T predikát $ T(e, x, z) $ platí, právě když e je kód programu, x je vstup programu a z kóduje výpočet nad e-tého programu nad vsupem x, který zastaví.

Existence T predikátu říká, že každá ČRF má standardní tvar $ \simeq Result(\mu_z(T(e,x,z))) $

  • Kleeneho věta (o normální formě)

Pro každé $ k \ge 1 $ existují

  • ČRF $ \Psi_k(e, x_1, ..., x_k) $ k+1 proměnných (univerzální funkce)
  • PRP $ T_k $. k+2 proměnných (kleeneho T predikát)
  • PRF $ U $. jedné proměnné (PRF "obal" univerzální funkce)
  • PRF $ s_k $. k+1 proměnných (fixování prvních k proměnných)

takové, že

  • $ \Psi_k $ je univerzální funkcí pro třídu k proměnných. Jde efektivně zíkat e z odvození (normalizace) a naopak z e jde získat efektivně odvouení.
  • $ \Psi_k(e, x_1, ..., x_k) \simeq U(\mu_y(T_k(e, x_1, x_2, ..., x_k, y))) $
  • $ s_k $ jsou prosté funkce rostoucí ve všech proměnných
  • $ \Psi_{m+n}(e, y_1, ..., y_m, x_1, ..., x_n) \simeq \Psi_{n}(s_m(e, y_1, ..., y_m), x_1, ..., x_n) $ (s-m-n věta)
  • $ T_k(e, x_1, ..., x_k, y)\;AND\; T_k(e, x_1, ..., x_k, z) \Rightarrow y=z $ (standardnost univerzální funkce)
Tato část je neúplná a potřebuje rozšířit. Mate nekdo naznak dukazu??

Vlastnosti univerzální funkce (pro ČRF)

  • Je taky ČRF
  • Nelze rozšířit na ORF (nemůže být definovaná všude – numeruje i programy, které jsou smyčka)

Formální důkaz toho, že nejde rozšířit na ORF: Předpokládejme, že f je rozšíření na ORF. Položme $ g(x) \simeq 1 - f(x, x) $. Jelikož f je ORF je i g ORF. Funkce g má svoje gödelovo číslo a a tedy $ g(x) \simeq \Psi_1(a,x) $. Specielní případ, pro $ x=a $, kdy $ g(a) \simeq \Psi_1(a,a) $. A to je spor: $ g(a) \simeq 1 - f(a, a) $, a protože f je rozšíření $ \Psi_1 $, platí že $ f(a, a) \simeq \Psi_1(a, a) $ (g je ORF a tím pádem je $ \Psi_1(a, a) $ jistě definováno). No a tedy je $ g(a) \simeq 1 - \Psi_1(a, a) \simeq \Psi_1(a, a) $, což asi pro každé kódování zvládnout nejde.

Predikát o konvergenci univerzální funkce

  • Predikát $ \Psi_k(e, x_1, x_2, ..., x_k)\uparrow $ není RSP
  • Predikát $ \Psi_k(e, x_1, x_2, ..., x_k)\downarrow $ je RSP, ale není ORP

Důkaz: (je uveden pouze pro dvě proměnné, nikoli pro více) Pro spor přepdokládejme, že je RSP. Pak jeho charakteristická funkce je ČRF (označmě ji $ \alpha $), která je definována právě když $ \Psi_k(e, x_1, x_2,..., x_k)\uparrow $. Tato ČRF má ale gödelovo číslo a, a tedy $ \alpha(x) \simeq \Psi_k(a, x) $. No a teď zas ten specielní případ, $ \alpha(a) \simeq \Psi_k(a, a) $. To je ale spor, protože $ \alpha(x) \simeq \Psi_k(x, x) $ je definováno právě když $ \Psi_k(x, x) $ není definováno ($ \Psi_k(x, x)\uparrow $) (Mimochodem, tohle je ukázka Cantorovy diagonální metody, na diagonále jsou $ \Psi_k(z, z) $)

Kdyby $ \Psi_k(e, x_1, x_2, ..., x_k)\downarrow $ byl ORP, musela by i jeho charakteristická funkce být ORF, tj definovaná pro všechny vstupy, tj musela bz být definovaná i pro úseky, kde $ \Psi_k(e, x_1, x_2, ..., x_k)\uparrow $ a to by byla ČRF, což podle předchozího není.

Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti

see wen:Recursive set, wen:Recursively enumerable set

Základní definice

  • Predikáty ("vlastnost" - např. x < y, nebo x je elementem M)
  • predikát je obecně rekurzivní (ORP), resp. primitivně rekurzivní (PRP), jestliže jeho charakteristická funkce je taková (ORF, resp. PRF)
    • ORP jsou právě ty, které jsou efektivně rozhodnutelné
  • predikát je rekurzivně spočetný (RSP), jestliže jeho obor pravdivosti je definičním oborem nějaké ČRF
    • tam, kde P neplatí, tam program není definován
  • množina M je rekurzivní, jestliže její charakteristická fce je ORF
    • rekurzivní množina je taková, že o každém prvku dokážeme efektivně zjistit, zda do množiny patří či nikoliv
    • Rekurzivní množina je právě efektivně (algoritmicky) rozhodnutelná
  • množina M je rekurzivně spočetná, jestliže je definičním oborem nějaké ČRF
    • rekurzivně spočetné množiny se nějaký program pouze zastaví, když prvek do množiny patří, jinak nic nevíme

Věta o selektoru

Pro každý RSP $ Q $ k+1 proměnných existuje ČRF $ \varphi $ k proměnných, pro kterou platí

  • $ \varphi(x_1,...,x_k)\downarrow \Leftrightarrow \exists y Q(x_1,...,x_k,y) $
  • $ \varphi(x_1,...,x_k)\downarrow \Rightarrow Q\Big(x_1,...,x_k,\varphi(x_1,...,x_k)\Big) $.

Druhá řádka říká, že pro každý RSP $ Q $ umíme zkonstruovat takovou ČRF $ \varphi $, která lze dosadit za poslední proměnnou $ Q $ (respektive její výsledek y) a pokud $ \varphi $ konverguje, tak $ Q $ platí. První řádka říká, že $ \varphi $ "se snaží seč může", tedy pokud nějaké y existuje, tak ho najde. (Nebýt této podmínky, šlo by za $ \varphi $ zvolit třeba prázdnou funkci.)

Predikát $ Q $ k+1 proměnných si můžeme představit jako relaci či graf (grafem se zde rozumí množina bodů, žádné hrany a vrcholy) v k+1 rozměrném prostoru (přirozených čísel ovšem, jak jinak). Predikát $ Q(x_1,...,x_k,x_{k+1})\! $ určuje, zda bod $ (x_1,...,x_k,x_{k+1}) $ je v grafu, či nikoli. $ \varphi $ můžeme chápat jako funkci na k rozměrném prostoru takovou, že v grafu vybere v poslední proměnné právě jeden bod (pokud existuje). Celý tento odstavec je tu jen proto, aby vysvětlil název věta (či lemma) o selektoru a proč se říká, že ČRF mají RS graf. Klidně na něj zatím zapomeňte.

Důkaz: Pro RSP $ Q $ existuje TS $ T $, který se zastaví v přijímacím stavu, pokud $ Q(x_1,...,x_k,y) $.

Definujme ORF $ \beta(x_1,...,x_k,y,j) = 0 \Leftrightarrow T\mbox{ přijme vstup }x_1,...,x_k,y\mbox{ za }j\mbox{ kroků} $

Požadovaná ČRF je pak:

$ \varphi(x_1,...,x_k) = \mu_{<y,j>}\beta(x_1,...,x_k,y,j) $

Pokud totiž pro $ x_1,...,x_k $ nějaké $ y $, takové že platí $ Q(x_1,...,x_k,y) $ existuje, tak se odpovídající TS zastaví nejvýše po $ j $ krocích, a my to zjistíme v $ <y,j> $-té iteraci minimalizační funkce $ \mu_{<y,j>} $.

$ W_x \mbox{ (x-tá rekurzivně spočetná množina) } $

$ W_x \mbox{ (x-tá rekurzivně spočetná množina) } = dom(\varphi_x) = \{ y:\varphi_x(y)\downarrow \} $

  • Ty y, pro která konverguje x tá univerzální funkce.

$ K = \{ x:x \in W_x \} = \{x:\varphi_x(x) \downarrow \} = \{ x:\Psi_1(x,x) \downarrow \} $

  • $ K $ je množina (indexů) funkcí, co konvergují na tom svém indexu.

Věta: Množina $ K $ je rekurzivně spočetná, není rekurzivní, $ \overline K $ není rekurzivně spočetná.

Důkaz: Z definice je $ K = \{x \in W_x\} = \{y: \varphi_y(y) \downarrow \} = \{y: \Psi_1(y, y) \downarrow \} $. Univerzální funkce je ČRF, y je v jejím definičním oboru a tedy je rekursivně spočetná.
Kdyby $ K $ byla rekursivní, tak bychom mohli sestavit ORF $ \alpha $ takovou, že $ \alpha(x)\downarrow \Leftrightarrow \Psi_1(x,x)\uparrow $. Tato $ \alpha $ by měla gödelovo číslo a a podle Kleeneho věty o NF by $ \alpha(x) \simeq \Psi_1(a,x) $. Speciálně by bylo $ \alpha(a) \simeq \Psi_1(a,a) $. A to je spor, protože podle definice je buď $ \Psi_1(a,a) $ nezkonverguje, pak ale $ \alpha(a) $ zkonverguje. Druhá možnost je, že $ \Psi_1(a,a) $ zkonverguje ale $ \alpha(a) $ pak nekonverguje.
Kdyby $ \overline K $ byla rekurzivně spočetná, měla by index $ x_0 $ ($ \overline K = W_{x_0} $), což vede ke sporu $ x_0 \in \overline K \Leftrightarrow x_0 \in W_{x_0} \Leftrightarrow x_0 \in K $

1-převeditelnost, m-převeditelnost

  • Množina $ A $ je 1-převeditelná na $ B $ (značíme $ A \leq_1 B $), jestliže existuje prostá ORF taková, že $ x \in A \Leftrightarrow f(x) \in B $.
    • Množina M je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převeditelná.
  • Množina $ A $ je m-převeditelná na $ B $ (značíme $ A \leq_m B $), jestliže existuje (ne nutně prostá) ORF taková, že $ x \in A \Leftrightarrow f(x) \in B $.
    • Množina M je m-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina na ni je m-převeditelná.

1-úplnost K

Věta: K je 1-úplná.

Důkaz: Chceme ukázat, že pro každou rekursivně spočetnou množinu $ W_x $ je je $ W_x \leq_1 K $, to jest, že exituje prostá ORF h taková, že $ y \in W_x \Leftrightarrow h(x) \in K $. Mějme libovolnou rekurzivně spočetnou množinu $ W_x $ a ČRF $ \alpha(y,x,w) $, která ji popisuje.
Tedy $ \alpha(y,x,w)\downarrow \Leftrightarrow^* y \in W_x \Leftrightarrow \Psi_1(x,y)\downarrow \Leftrightarrow \varphi_x(y)\downarrow $ (na $ w $ hodnota $ \alpha $ nezávisí)
Ze s-m-n dostáváme $ \alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w) $ (**)
Označíme-li $ h(y,x) = s_2(a,y,x) $ ($ s_2 $ je PRF a tedy i ORF), máme $ y \in W_x \Leftrightarrow^* \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 $
  • *** -- můžeme předpokládat $ h(y,x) = w $, hodnota $ \alpha $ a tudíž ani $ h $ na $ w $ nezáleží.
Tedy $ W_x \leq_1 K $ pomocí funkce $ \lambda y.h(y,x) $.

Také platí

  • $ K_0 = \{ \langle y,x \rangle : y \in W_x \} $ je 1-úplná.
  • $ K \leq_1 K_0 $ a $ K $ je 1-úplná.
Poznámka: To vlastně říká, že halting problém je vzhledem k 1- převeditelnosti nejtěžší problém mezi rekursivně spočetnými problémy($ K_0 = \{ \langle y,x \rangle : y \in W_x \} $ je definice halting problému)

Další vztahy

  1. Relace $ \leq_1 $ a $ \leq_m $ jsou tranzitivní a reflexivní.
  2. $ A \leq_1 B \Rightarrow A \leq_m B $
  3. $ B \mbox{ rekurzivní}, A \leq_m B \Rightarrow A \mbox{ rekurzivní} $
    • Složením funkce dokazující $ \leq_m $ s procedurou, která rozhoduje o $ x \in B $ dostaneme proceduru rozhodující o $ A $. ($ c_A(x) = c_B(f(x)) $
  4. $ B \mbox{ rekurzivně spočetná}, A \leq_m B \Rightarrow A \mbox{ rekurzivně spočetná} $
    Důsledek: $ K $ a $ \overline K $ jsou m-nesrovnatelné.

Rekurzivní permutace

  • Rekurzivní permutace je permutace na $ \mathbb{N} $, která je ORF.
  • Množiny $ A $ a $ B $ jsou rekurzivně izomorfní, jestliže existuje rekurzivní permutace p taková, že $ p(A) = B $. Značíme $ A \equiv B $.
  • $ A \equiv_1 B $, jestliže $ A \leq_1 B \And B \leq_1 A $
  • $ A \equiv_m B $, jestliže $ A \leq_m B \And B \leq_m A $

Myhillova věta

$ A \equiv B \Leftrightarrow A \equiv_1 B $ Důkaz je ve Strojilovi na straně 5, zprava doleva spočívá v postupném generování grafu $ h $ tak, aby v kroku $ n $ platilo $ \{0, ..., n\} \subseteq dom(h) $ a $ \{0,...,n\} \subseteq rng(h) $.

Důsledek: $ K \equiv K_0 $, neboť $ K \equiv_1 K_0 $

Rekurzivně spočetné predikáty

  • Je-li $ Q $ ORF, pak $ \exists y Q $ je rekurzivně spočetný predikát. (nema Q v predpokladech byt spis predikat, nez funkce?)
    $ \mu_y Q $ je ČRF, její definiční obor je $ \exists y Q $.
  • Predikát $ \exists y T_k(e,x_1,... ,x_k,y) $ je univerzální RSP pro třídu RSP $ k $ proměnných.
    $ T_k $ je predikát z Kleeneho věty o normální formě, co říká že funkce $ e $ má při $ y_0 $ krocích od konce mezivýsledek $ y_1 $. ($ y=\langle y_0, y_1 \rangle $). Důkaz tvrzení plyne z Kleeneho věty.
  • Doplněk nezachovává rekursivní spočenost (důkaz už byl)
  • Konjunkce a disjunkce zachovávají rekurzivní spočetnost. (Průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.)
    Pro sjednocení spustíme oba programy současně a čekáme až se jeden zastaví. Pro průnik čekáme, až se zastaví oba.
    Důkaz pro průnik: $ x \in A, x \in B $ jsou RSP. Pomocí Kleeneho T Predikátu jde každý predikát zapsat v univerzálním tvaru $ \exists z, T_k(a, x_1, .., x_k, z) $, kde a je gödelovo číslo predikátu. Tak zapíšeme$ x \in A, x \in B $ pomocí obecného T predikátu: $ \exists z_1, T_k(a, x, z_1) \and \exists z_2, T_k(b, x, z_2) $. Nyní $ z_1, z_2 $ zakódujeme do dvojice: $ \exists w, T_k(a, x, l(w)) \and T_k(b, x, r(w)) $. Jelikož T predikár je PRP, můžeme to přepsat jako $ \exists z, T_{k+2}(e, a, b, x, z) $. A teď se použije s-m-n věta. $ \exists z, T_k(s(e, a, b), x, z) $. Obdobně pro sjednocení.
  • Omezená kvantifikace $ (\forall y)_{y \leq t} $ a existenční kvantifikace (pro $ k \geq 2 $) zachovávají rekurzivní spočetnost.
    Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem, existenční kvantifikátor je rozveden ve Strojilovi na straně 6.

Postova věta a ostatní věty o RSM

Věta (Postova): Množina $ M $ je rekurzivní právě když $ M $ i $ \overline M $ jsou rekurzivně spočetné. Predikát $ Q $ je ORP právě když $ Q $ i $ \neg Q $ jsou RSP.

Důkaz: Zleva doprava triviální – přímo z definice. Zprava doleva intuitivně: $ M = dom(P_1), \overline M = dom(P_2) $. Pustíme oba programy současně a čekáme, který se zastaví. Formálně pomocí věty o selektoru: $ Q(x, y) = (x \in M \and y=1) \or (x \notin M \and y=0) $. Selektor je ČRF, která vždy konverguje (vždy existuje y, je buď jedna, nebo nula). A máme charakteristickou funkci.

Věta:Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.

Důkaz: Máme dánu x-tou RSM. Vytvoříme množinu dvojic $ R = \{ \langle z,y \rangle : z \in W_x \And y = z \} $ (Predikát $ Q(z, y) = z \in W_x \And y = z $). Množina R je rekurzivně spočetná, tedy má ČRF selektor $ \varphi $, platí $ dom(\varphi) = rng(\varphi) = W_x $. Myšlenka důkazu je, že body, kde $ \varphi_x $ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude současně oborem hodnot.

Věta:Každý obor hodnot ČRF je rekurzivně spočetná množina.

Důkaz: Myšlenka: zkonstruujeme pseudoinverzní funkci k ČRF $ \varphi $. Dána $ M = rng(\varphi_x) $, kde $ \varphi_x $ je ČRF. Definujme predikát $ Q(z, y) = \varphi_x(y) \simeq z $. Pak Q je RSP a jeho selektor je ČRF jejíž je M doménou.

Věta: Množina je rekursivní <=> je oborem hodnot nějaké rostoucí úsekové ČRF. (úseková funkce je taková, jejímž def. oborem je počáční úsek $ \mathbb{N} $)

Důkaz:
"=>": U ČRF jsme použili selektor, jehož doménou byla doména charakteristické funkce množiny. Pokud víme, že je tato množina rekursivní, můžeme prvky seřadit do posloupnosti (až do vyčerpání množiny bude tato posloupnost všude definovaná). A dál použijeme minimalizaci: $ \varphi(0) \simeq \mu_y(y \in M), \varphi(n+1) \simeq \mu_y(y>\varphi(n) \and y \in M) $. Pak $ M = rng(\varphi) $.
"<=": Nechť $ \varphi $ je rostouci useková ČRF, $ M = rng(\varphi) $. Patří-li y do M, pak $ \exists x $ takové, že $ \varphi(x) = y $, protože y je z oboru hodnot $ \varphi $. Navíc víme, že $ x \leq y $, to proto, že x, y jsou $ \in \mathbb{N} $ a funkce je rostoucí, a v $ \mathbb{N} $ "stoupání musí být větší, než diagonála". Při dotazu, jestli $ y \in M $ stačí projít všechny $ x \leq y $, pak víme, že mezi těmi většimi ho už nenajdeme a tak máme definovanou ČRF charakteristickou funkci.

Věta: Množina je r.s. <=> je oborem hodnot prosté úsekové ČRF.

Důkaz:
"<=" Obor jakékoli ČRF je r.s. množina z definice.
"=>" Z předchozí věty víme, že RM jsou generovány rostoucími úsekovými funkcemi. Vezměme množinu $ B= \{<x,s>: \varphi(x)\downarrow za\;presne\;s\;kroku\} $, $ \varphi(x) $ je ČRF pro kterou $ dom(\varphi) = M $. Tato množina je rukursivní, pro každou dvojici lze rozhodnout, jestli $ \varphi(x) $ zkonverguje po s krocích. Funkce generující B je přitom rostoucí (z předchozí věty, B je rekursivní) a ze l(f) je v M. Formálně můžeme definovat $ g(x) = (f(x))_{2,1} $, pak g je ČRF, $ rng(g) = M $ a g je prostá (růst záležel na kódování dvojice <x,s>, f však nemůže vygenerovat x dvakrát, bylo řečeno přesně s kroků)

Produktivní a kreativní množiny

  • Definice: Množina A je produktivní, pokud existuje ČRF φ tž. $ W_x\subseteq A\implies\varphi(x)\downarrow \and \varphi(x)\in A\setminus W_x $
  • Definice: Množina B je kreativní, pokud je r.s. a $ \bar{B} $ je produktivní.
  • Příklady
    • K je kreativní - je RS a $ \bar{K} $ je produktivní, za φ se zvolí identita
  • Vlastnosti
    • Ke každé produktivní množině A existuje produktivní ORF f, f=φ(g(x)) - g(x) spočítá index 'podobného' programu, který je navíc totální pro jazyky mimo A
    • Ke každé produktivní množině A existuje produktivní ORF bijekce φ (dá se sestrojit s pomocí původní produktivní ORF)
    • Každá produktivní množina A obsahuje nekonečnou RSM - prázdná množina patří do A a φ nám vrátí vždy nový prvek z A, který se dá přidat k výchozí podmnožině A, atd.
  • Ekvivalence
    • A je produktivní, $ \bar{K} $ je 1-převeditelná na A, $ \bar{K} $ je m-převeditelná na A
    • B je kreativní, B je 1-úplná, B je m-úplná

Imunní a prosté množiny

  • Definice: Množina B je imunní, pokud je nekonečná a neobsahuje nekonečou r.s. množinu.
  • Definice: Množina B je prostá, pokud je r.s. a její dplněk je imunní mnoyžina.

Věta: Existuje prostá množina

Algoritmicky nerozhodnutelné problémy

Definice

see wen:List of undecidable problems

Uvažujme rozhodovací problémy - odpověď je buď ANO nebo NE. Instance tohoto problému nechť jsou kódována v abecedě $ \Sigma = \{0, 1\} $ Definujme jazyk kladných a záporných instancí problému. O jazyku řekneme, že rekursivní, pokud ho řeší nějaký (deterministický) turingův stroj. Slovem řešit problém budeme popisovat situaci, kdy se stroj pro všechny kladné instance zastaví v koncovém stavu, kde přijímá a pro všechny ostatní instance problému se zastaví ve stavu, kde odmítá.

Definice: Problém je algoritmicky rozhodnutelný, pokud je jazyk jeho kladných instancí rekursivní. Jazyk, který není algoritmicky rozhodnutelný je algoritmicky nerozhodnutelný.


Halting problém

  • Halting problém, z Johančiných pohádek
Připomenu definici: neexistuje algoritmus, který by pro daný turináč a daný vstup dokázal rozhodnout, zda se turingáč na tomto vstupu zastaví. Pro důkaz použijeme pár myšlenek, které je dobré si zapamatovat, protože se s nimi nevidíme naposled. První z nich je (překvapivě) myšlenka UTS, druhou je otázka zastavení algoritmu na jeho vlastním kódu a třetí myšlenkou je přiřadit výsledky něčeho úmyslně opačně - nelogicky: když se něco povede, 0, když nepovede, 1. Z tohohle všeho dohromady kouká nějaký slibný spor, tak teď si to konečně aplikujeme na náš konkrétní úkol.
Důkaz (pomocí UTS): provedeme sporem, předpokládáme, že existuje algoritmus H(M,K), co mu předhodíme turingáč M a vstup K a on řekne, jestli tenhle vztah má budoucnost :). Tedy vždy se zastaví a řekne 0 (nemá), nebo 1 (má). Pomocí něj sestrojíme kapku brutálnější algoritmus Alg(K), který se nad daným kódem programu zastaví právě tehdy, když se tento program sám se na svém vlastním kódu nezastaví. Tedy Alg(K) zastaví <=> U(K,K) nezastaví. Prostě algoritmus Alg říká: mně se líbí program, co nesežere svůj vlastní vstup, a tak se na něm zastavím, naopak program, co svůj vlastní vstup sežere, se mi nelíbí, takže se na něm třeba zacyklím a prostě trucuju :). Alg(K) definujeme podle výsledku výše zmíněného algoritmu H (který se vždy zastaví a něco řekne, takže my ho provedem a podle toho, co řekl, se rozhodnem): H(U(K,K),K) = 0 => Alg(K) zastaví, H(U(K,K),K) = 1 => Alg(K) zacyklí. Celá tahle prasárna jde provést právě proto, co jsme si na začátku definovali, tedy že algoritmus H existuje a vždy se zastaví. No a teď už asi nikoho nepřekvapí, že po tak ďábelské definici algoritmu Alg snadno vykouzlíme spor - pustíme ho na jeho vlastním kódu. Potom Alg(Alg) zastaví <=> U(Alg,Alg) nezastaví <=> Alg(Alg) nezastaví. Tohle ukazuje, že původní algoritmus H (který rozhoduje o zastavení) je zvrácený a nemůže existovat :).
Důkaz (pomocí ČRF): Z kleeneho věty víme, že existuje efektivní očíslování pro třídu ČRF a její univerzální funkce. vezměme množinu $ K = \{x: \varphi_x(x)\downarrow\} = \{x: \Psi(x, x)\downarrow\} $. Ta není rekursivní (pokud by byla, tak bychom mohli dodefinovat funkci $ \alpha $ takovou, že $ \alpha \downarrow \Leftrightarrow \varphi_x(x) \uparrow $. Ta by byla r.s. a měla gödelovo číslo e, takže $ \varphi_e(e) \simeq \alpha(e) $ takže $ \alpha(e) \downarrow \Leftrightarrow \varphi_e(e) \uparrow \Leftrightarrow \alpha(e) \uparrow $). No a tím spíš není rekursivní $ K_0 = \{<x, y>: \varphi_x(y)\downarrow \} $, protože $ K \leq_1 K_0 $.

Ostatní problémy

  • Je jazyk přijímaný daným TS prázný/neprázný/konečný?
  • Riceova věta
  • Postův korespondeční problém PKP (i s omezením na iniciální řešení IPKP).
Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:
$ S = \{ (\alpha_1,\beta_1),\,...,\,(\alpha_k,\beta_k) \} $, kde $ k \geq 1 $ a $ \alpha_i, \beta_i $ jsou řetězce nad nějakou abecedou.
Řešením Postova systému je každá neprázdná posloupnost přirozených čísel I:
$ I = \{ i_1,\,...,\,i_m \} $, kde $ 1 \leq i_j \leq k $ a $ m \geq 1 $, pro kterou platí $ \alpha_{i_1}...\alpha_{i_m} = \beta_{i_1}...\beta_{i_m} $.
Postův korespondenční problém zní: Existuje pro daný Postův systém řešení?
Příklad: Systém $ S_1 = \{ (b,bbb),\,(babbb,ba),\,(ba, a) \} $ má řešení $ I = \{ 2,\,1,\,1,\,3 \} $: babbb b b ba = ba bbb bbb a.
Systém $ S_2 = \{ (ab,abb),\,(a,ba),\,(b,bb) \} $ řešení nemá.
Lze ukázaat IPKP <=> TS zastaví nad slovem u.
  • Pro bezkontextové gramatiky G1,G2 je algoritmicky nerozhodnutelné zda L(G1)∩L(G2)={}.
Důkaz: převedeme PKP na daný problém máme PKP [u1,v1],..., [un,vn]
zvolíme nové terminály a1,…,an pro kódy indexů
G1: S→ uiSai | uiai generuje slova ui1... uikaik... ai1
G2: S→ viSai | viai generuje slova vi1... vikaik... ai1
PKP má řešení právě když L(G1) ∩L(G2)≠{}
u-část = v-část + složky ai< zajišťují stejné pořadí
  • Je algoritmicky nerozhodnutelné, zda je bezkontextová gramatika víceznačná.
Důkaz:
S → S1 | S2
S1 → uiS1ai | uiai
S2 → viS2ai | viai
PKP má řešení právě když je gramatika víceznačná
  • přičinlivý bobr a tak.

Věty o rekurzi a jejich aplikace

  • Ladova skripta str.11, o pevnem bode,
  • pouziti v logice, godelovy vety
  • paradox lhare
  • veta o rekurzi (o existenci pevneho bodu) s dukazem
  • Veto o nekonečném počtu pevnych bodu
  • Aplikace vět o rekurzi:
    • Důkaz Riceovy věty
    • Nerozhodnutelnost minimality Turingova stroje
    • Ekvivalenci dvou programů nelze rozhodnout algoritimicky (důsledek věty Rice)

Věty o rekurzi

Věta (o rekursi): Jestliže $ f $ je ČRF jedné proměnné, potom existuje $ a $ takové, ze $ \varphi_{f(a)}(x) \simeq \varphi_a (x) $ pro každé $ x $.

Říká, že existuje pevný bod zobrazení $ f $. ($ \varphi $ je zřejmě univerzální funkce jedné proměnné)
Důkaz:$ \varphi_{f(s_1(z,z))}(x) \simeq \Psi_2( f(s_1(z,z)),x) \simeq \Psi_2(e,z,x) \simeq^{smn} \Psi_1(s_1(e,z), x) \simeq \varphi_{s_1(e,z)}(x) $
  • $ s_1(z,z) $ je funkce se s-m-n věty, která dělá totéž co z, ale má první parametr fixovaný na hodnotu z
  • e je index programu, který počítá výraz vlevo (tj. $ s_1(z,z) $, pak $ f(s_1(z,z)) $, a vzniklou funkci aplikuje na x)
Pak položíme $ z=e $ a $ a=s_1(e,e) $ a máme ten pevný bod.
Na přednášce bylo rozebíráno, jak vypadají jednotlivé programy pro a a pro f(a), hlavně, který počítá rychleji. A to je pěkná otázka ke státnici. Z odvození v důkazu je vidět, že program s pořadovým číslem a spustí univerzální funkci na vstup (a, x). Tím univerzální funkce nejprve spočte s_1(e,e), tedy a, následně spočte f(a) a potom simuluje hlavní program.
Výpočet jde tedy v pořadí: $ \Psi_1(a, x) \simeq \Psi_2(e, e, x) \simeq \Psi_2(f(s_1(e,e)),e,x) $. Program s pořadovým číslem a tedy počítá déle než ten s f(a).

Věta (o rekursi v závislosti na parametrech): Nechť $ f(x, y_1, y_2, ...y_m) $ je ČRF m+1 proměnných. Pak existuje PRF $ g(y_1, y_2, ...y_m) $ m proměnných taková, že $ \varphi_{g(y_1, y_2, ...y_m)}(x) \simeq \varphi_{f(g(y_1, y_2, ...y_m), y_1, y_2, ...y_m)}(x) $

Důkaz: Obdobně jako základní věta o rekursi. $ \varphi_{f(s_{m+1}(z, z, \overrightarrow{y}),\overrightarrow{y})}(x) \simeq \Psi_{m+2}(e, z, \overrightarrow{y}, x) \simeq^{smn} \Psi_1(s_{m+1}(e,z, \overrightarrow{y}), x) \simeq \varphi_{s_{m+1}(e,z, \overrightarrow{y})}(x) $. A teď položíme $ g(\overrightarrow{y})=s_{m+1}(e,e, \overrightarrow{y}) $.

Věta (o generování pevných bodů): Pro každou částečně rekurzivní funkci $ f $ existuje prostá rostoucí PRF $ g $ taková, že platí $ \varphi_{f(g(j))}(x) \simeq \varphi_{g(j)}(x) $.

Tedy $ g $ rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce $ f $.
Důkaz:$ \varphi_{f(s_2(z,z,j))}(x) \simeq \Psi_3(e,z,j,x) \simeq \Psi_1(s_2(e,z,j), x) \simeq \varphi_{s_2(e,z,j)}(x) $
  • $ e $ podobně jako u věty o rekurzi schválně počítá levou stranu
Zvolíme $ g(j) = s_2(e,e,j) $.
V předchozích větách jsme hledali pro ČRF zobrazení jeden pevný bod, pak pro vícerozměrné zobrazení parametrizovaný pevný bod. Tahle věta říká, že pro dané zobrazení můžou pevné body generovat prosto funkci.

Věta (o programu co vypíše sám sebe - Quine): Nechť $ f(x, y_1, y_2, ... ,y_m) $ je ČRF. Pak existuje a takové, že $ \varphi_a(y_1, y_2, ..,y_m) \simeq f(a, y_1, y_2, ..., y_m) $.

Důkaz: Jelikož f je ČRF, platí $ f(x, y_1, y_2, ... ,y_m) \simeq \Psi(e, x, y_1, y_2, ... ,y_m) \simeq^{s-m-n} \Psi(s_1(e, x), y_1, y_2, ... ,y_m) \simeq \varphi_{s_1(e,x)}(y_1, y_2, ..,y_m) $. Použijeme větu o rekursi na $ s_1(e,x) $ v proměnné x a dostáváme $ \varphi_{s(e,a)}(x) \simeq \varphi_a(x) $ pro nějaký pevný bod a.
Pomocí této věty jde snadno najít program, co vypíše sám sebe. Vezměme funkci $ f(x, y) \simeq x $. Pak podle předchozí věty najdeme a takové, že $ \varphi_a(y) \simeq f(a, y) $, jenže z definice je $ f(a, y) \simeq a $, tedy máme $ \varphi_a(y) \simeq a $. To je program, který pro libovolný vstup vypíše svůj kód

Riceova věta

Věta (Riceova): Jestliže $ \mathcal{A} $ je třída ČRF (jedné proměnné), ktera je netriviální (není prázdná, ani neobsahuje všechny ČRF), potom $ A_{\mathcal{A}} = \{ x : \varphi_x \in \mathcal{A} \} $ není rekurzivní.

Důkaz: Dokazuje se sporem. Nechť $ A_{\mathcal{A}} $ je rekurzivní. Potom lze vytvořit ORF $ f $ takovou, že všechny prvky z $ A $ zobrazí na nějaký prvek $ b \notin A $ a všechny prvky mimo $ A $ zobrazí na nějaký prvek $ a \in A $. Existence $ a $ a $ b $ je zaručena požadavkem na neprázdnost a neúplnost. Podle věty o rekurzi existuje pro $ f $ (je ORF) nějaký pevný bod $ u_0 $, že platí $ \varphi_{u_0} = \varphi_{f(u_0)} $.
Tedy $ u_0 \in A \Rightarrow f(u_0) = b \notin A $ a $ u_0 \notin A \Rightarrow f(u_0) = a \in A $. Což je ovšem spor s tím, že čísla $ u_0 $ a $ f(u_0) $ buď v $ A $ leží obě nebo jsou obě mimo – jsou to indexy stejné funkce.
Nejedná se o třídu programů, ale funkcí. Tedy i pro jednoprvkovou $ \mathcal{A} $ bude $ A_{\mathcal{A}} $ nekonečná a nerekurzivní (každá funkce je vyčíslována nekonečně mnoha programy a rozhodnout o jejich ekvivalenci efektivně nelze).
Tato věta vlastně říká, že každá netriviální vlastnost ČRF je algoritmicky nerozhodnutelná.

Gödelovy věty

rekurzivní neoddělitelnost
Dvojice množin A, B ($ A \cap B = \emptyset $) je rekurzivně neoddělitelná, jestliže neexistuje rekurzivní množina M taková, že $ A \subseteq M, M \cap B = \emptyset $ (tj. $ B \subseteq \overline{M} $)
efektivní neoddělitelnost
Dvojice množin A, B ($ A \cap B = \emptyset $) je efektivně neoddělitelná, jestliže existuje ČRF $ \varphi $ taková, že
$ \begin{matrix} A \subseteq W_x \\ B \subseteq W_y \\ W_x \cap W_y = \emptyset \end{matrix} \Bigg \} \Rightarrow \varphi(x,y)\downarrow \and \varphi(x,y)\notin W_x \cup W_y $
Tj. z indexů aproximace A a B se dá efektivně najít další bod, který leží mimo tu aproximaci.
Gödelova věta o neúplnosti (1. část)
V rozumných teoriích je množina dokazatelných a vyvratitelných formulí efektivně neoddělitelná dvojice.

Gödelova věta o neúplnosti

Základní aritmerická síla: Jazyk prvního řádu

  • numerály pro nulu a jedničku
  • funkční symboly + a ×
  • konečně mnoho axiomů

Teorie T je axiomatizovatelná, jestliže množina dokazatelných formulí v T je rekurzivně spočetná.

Věta: Jestliže teorie T 1. řádu má základní aritmetickou sílu a je bezesporná, pak

  1. množina formulí dokazatelných v T není rekurzivní
    Vezmu r.s. efektivně neoddělitelné A,B tž. $ x\in A\implies\vdash_T G(\bar{x}) $ a $ x\in B\implies\vdash_T \neg G(\bar{x}) $.
    Vezmeme $ A_1=\{x;\vdash_T G(\bar{x})\} $, $ B_1=\{x;\vdash_T \neg G(\bar{x})\} $ ($ A\subseteq A_1 $, $ B\subseteq B_1 $). Z bezespornosti A1 a B1 disjunktní a nejsou rekurzivní (separovaly by).
  2. je-li T navíc axiomatizovatelná, pak
    • existuje uzavřená formule v F taková, že F je nerozhodnutelná v T (tj. z T nevyplývá ani F, ani $ \neg F $)
    Množiny A1 a B1 z bodu (1) jsou nyní r.s. a umím tedy efektivně určit bod mimo ně (číslo fle nedokazatelne ani nevyvratitelné v T).
    • v T nelze dokázat vlastní bezespornost (za o něco silnějších předpokladů o teorii T -- např. $ \Sigma_1-\mbox{indukce} $)

Materiály

  • Pohádky z vyčíslitelnosti – velmi neformální úvod do problematiky
  • Wiki skripta z vyčíslitelnosti – neúplná, ale podrobná
  • Vyčíslitelnost I – stránka předmětu na wiki, obsahuje odkazy na další materiály
  • Pavliska V., Vyčíslitelnost a Složitost 1 a 2, Ostravská Univerzita, [2] a [3]
  • Demuth O., R. Kryl R., Kučera A., Teorie algoritmů I a II, skripta MFF-UK
  • Češka M., Vojnar T., Smrčka A., Teoretická informatika, VUT Brno [4]