Státnice - Informatika - Vyčíslitelnost

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.

• Text P. Kučery – Podle mě super srozumitelný materiál, který pokrývá vše kromě Gödela!

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

Turingův stroj, definice

(Deterministický) 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

Pro srovnání, nedeterministický stroj se liší jen tím, že $ \delta: \{Q - q_f \in F\}\times\Gamma \rightarrow $ má jako obor hodnot množinu stavů, mezi kterými si automat nedeterministicky vybere..

ČRF, definice

Viz níž Státnice_-_Informatika_-_Vyčíslitelnost#Částečně rekurzivní funkce

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 v₁, v₂, . . . v_n

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

ČRF => TS (každá ČRF je turingovsky vyčíslitelná)

Důkaz indukcí podle konstrukce ČRF

• Základní f-ce jsou turingovsky vyčíslitelné
• Operátory zachovávají T-vyčíslitelnost:
  • Substituce: Vyčíslím podfunkce g_i (pomocí m pásek), dám to dohromady a vyčíslím na tom f.
  • Primitivní rekurze: Vyhodnotím f a pak y-krát "otočím" g za použití vstupních parametrů, počítadla cyklů a výsledku z predcházejícího výpočtu.
  • Minimalizace: Opakovaně vyčísluji f na vstupních parametrech a zvětšujícím se počítadle cyklů. Když f poprvé vrátí 0 skončím a vrátím hodnotu počítadla.

TS => ČRF

Výpočet TS se dá chápat jako posloupnost konfigurací (obsah pásky, stav řídící jednotky, pozice hlavy). Tyto konfigurace jde zakódovat do kódu, a výpočet TS chápat jako posloupnost těchto kódů. Kódujeme tzv. Postova slova UqsV do $ \mathbb{N} $.

Jeden krok TS představuje lokální změnu v Postově slově a jistě tedy existuje funkce na kódech, která charakterizuje. Tato funkce vlastně obsahuje jenom rozhodovací strom odpovídající přechodové funkci našeho TS a na to nám stačí prostředky PRF (na if podmínku použijeme operátor primitivní rekurze).

Pomocí for cyklu (primitivní rekurze) pak můžeme sestavit funkci $ Comp(x,s) $, která vypočte kód stavu stroje startujíciho ze stavu odpovídajícímu kódu $ x $ po $ s $ krocích. Pak už jen pomocí while cyklu přes to celé nalezneme posloupnost kroků do konečného stavu, tj. $ Comp(x,\mu_s(\textrm{stroj}\;\textrm{je}\;\textrm{za}\;\textrm{s}\;\textrm{kroku}\;\textrm{v}\;\textrm{konfiguraci}\;q_f) $. Formálně by to šlo zapsat tak, že pro každý turingův stroj TS existuje ČRF $ g $ taková, že pro libovolnou konfiguraci $ k $ platí $ kod(TS(k)) \simeq g(kod(k)) $.

Víc 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 k proměnných (numerace)

funkce U je univerzální pro spočetnou tří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) $

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>} $.

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á. (Pozn.: Nemá být nekonečná? Jak může být 1prvková množina převoditelná na dvojprvkovou?)
• 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: Plán: v krocích budeme generovat graf $ h $ tak, že v kroce $ n $ bude platit

$ \{0,\ldots,n\} \subseteq dom(h), \qquad \{0,\ldots,n\} \subseteq rng(h) $.

Z toho plyne, že $ h $ bude definovaná na celém $ \mathbb{N} $ a bude na. Současně zajistíme, že $ h $ bude prostá.

Navíc budeme chtít, aby platilo $ y \in A \Leftrightarrow h(y) \in B $, tedy aby $ h $ převáděla $ A $ na $ B $.

Indukce: Začneme v bodě 0 a položíme $ h(0)=f(0) $. Rozlišíme následující případy:

• $ f(0)=0 $: vše je v pořádku, $ h(0)=f(0)=0 $ a $ 0 \in A \Leftrightarrow 0 \in B $, pokračujeme dalším prvkem.
• $ f(0) \neq 0 $: rozlišíme dva podpřípady
  • $ g(0)\neq 0 $: vše v pořádku, definujeme $ h(g(0))=0 $. Tedy $ 0 \in dom(h) \cap rng(h) $.
  • $ g(0)=0 $: nemůžeme použít $ h(g(0))=0 $, protože v bodě 0 je již $ h $ definována jako $ f(0) $. Najdeme tedy volný bod. Definujme $ h(g(f(0)))=0 $. Určitě $ g(f(0))\neq 0 $, protože $ g $ je prostá a $ f(0)\neq 0 $.

Tímto jsme opět dostali bod 0 do definičního oboru $ h $ i oboru hodnot. Zároveň funkci $ h $ definujeme podle $ f $ a $ g $, tedy převádí vzájemně $ A $ na $ B $.

Indukční krok: nechť v kroce $ k $ je $ z $ první volný prvek. Všechna čísla menší jak $ z $ máme v $ dom(h)\cap rng(h) $. Podíváme se, zda je $ f(z) $ volný. Jestliže ano, položíme $ h(z)=f(z) $. Jestliže $ f(z) $ není volný, hledám zig-zag další volný. Maximálně $ z $ prvků je blokovaných.

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

Rekurzivně spočetné predikáty

• Je-li $ Q $ ORP, pak $ \exists y Q $ je rekurzivně spočetný predikát (RSP).

  $ \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 ORF 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 $. Množina B je rekurzivní, 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ů)

Důsledek: Množina M je nekonečná, pak M je rekurzivní <=> lze generovat rostoucí ORF.

Důsledek: Množina M je nekonečná, pak M je r.s. <=> lze generovat prostou ORF.

Věta: Každá nekonečná r.s. množina obsahuje nekonečnou rekurzivní podmnožinu.

Důkaz:

$ f $ je prostá ORF, $ range(f) = M $, vyber rostoucí podposloupnost $ h(0) \simeq 0 $, $ h(n+1) \simeq f(\mu_y(f(y) > h(n))) $, $ h $ je ORF, roste, $ range(h)=A \subseteq M $

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í doplněk je imunní množ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 [u₁,v₁],..., [u_n,v_n]

zvolíme nové terminály a1,…,an pro kódy indexů

G1: S→ u_iSa_i | u_ia_i generuje slova u_i1... u_ika_ik... a_i1

G2: S→ v_iSa_i | v_ia_i generuje slova v_i1... v_ika_ik... a_i1

PKP má řešení právě když L(G1) ∩L(G2)≠{}

u-část = v-část + složky a_i< zajišťují stejné pořadí

• Je algoritmicky nerozhodnutelné, zda je bezkontextová gramatika víceznačná.

Důkaz:

S → S1 | S2

S1 → u_iS1a_i | u_ia_i

S2 → v_iS2a_i | v_ia_i

PKP má řešení právě když je gramatika víceznačná

Věty o rekurzi a jejich aplikace, Riceova věta

Matfyz Wiki: Věty o rekurzi

TODO, chybělo jako podotázka

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 A₁ a B₁ 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 A₁ a B₁ 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

• Text P. Kučery – Podle mě super srozumitelný materiál, který pokrývá vše kromě Gödela!
• 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]