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 group/mff-info/message/1777. 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.
[[Státnice - Algoritmicky vyčíslitelné funkce|Algoritmicky vyčíslitelné funkce, jejich vlastnosti]]
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 <math>f:\mathbb{N} \rightarrow \mathbb{N}</math> 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 <math>M=(Q, \Gamma, s, b, F, \delta)</math> kde :
<math>Q</math> je konečná množina vnitřních stavů
<math>\Gamma</math> je konečná abeceda symbolů a znaků
<math>s\in Q</math> je počáteční stav
<math>b\in \Gamma</math> je symbol reprezentující prázdný symbol ( <math>b</math> neni součástí vstupní abecedy přijímaného řetězce)
<math>F\subseteq Q</math> je množina koncových stavů
<math>\delta: \{Q - q_f \in F\}\times\Gamma\rightarrow Q\times\Gamma \times \{L,N,R\}</math> přechodová funkce, kde:
<math>L</math> znamená posun čtecí hlavy vlevo
<math>R</math> znamená posun čtecí hlavy vpravo
<math>N</math> znamená neposunutí čtecí hlavy
Pro srovnání, nedeterministický stroj se liší jen tím, že <math>\delta: \{Q - q_f \in F\}\times\Gamma \rightarrow </math> 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.
<pre>2-tag system (m=2) m=2 Alphabet: {a,b,c,H} Production rules: a --> ccbaH b --> cca c --> ccComputation: 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).</pre>
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ě:
#Pokud x je proměnná, pak x ∈ Λ #Pokud x je proměnná a M ∈ Λ, pak ( λ x . M ) ∈ Λ
#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ů:
<math>L R_i <- R_i + 1</math>
<math>L R_i <- R_i - 1</math>
<math>L R_i</math> jump (M,N)
continue,
kde L je návěští (má tvar "k:", k přirozené, je nepovinné), <math>R_i</math> 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:
zvýší se hodnota v poli <math>R_i</math> o jedničku
sníží se hodnota v poli <math>R_i</math> o jedničku
test na hodnotu v poli <math>R_i</math>; pro kladnou hodnotu skoč na instrukci s návěstím M, pro 0 instrukce s návěstím N.
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 <math>R_1,...,R_n</math>. Pokud je fce pro tuto n-tici definovaná, RAM program skončí a v registru <math>R_1</math> 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 <em>gi</em> (pomocí m pásek), dám to dohromady a vyčíslím na tom <em>f</em>.
Primitivní rekurze: Vyhodnotím <em>f</em> a pak y-krát "otočím" <em>g</em> za použití vstupních parametrů, počítadla cyklů a výsledku z predcházejícího výpočtu.
Minimalizace: Opakovaně vyčísluji <em>f</em> na vstupních parametrech a zvětšujícím se počítadle cyklů. Když <em>f</em> 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 <math>\mathbb{N}</math>.
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 <math>Comp(x,s)</math>, která vypočte kód stavu stroje startujíciho ze stavu odpovídajícímu kódu <math>x</math> po <math>s</math> krocích. Pak už jen pomocí while cyklu přes to celé nalezneme posloupnost kroků do konečného stavu, tj.
<math>Comp(x,\mu_s(\textrm{stroj}\;\textrm{je}\;\textrm{za}\;\textrm{s}\;\textrm{kroku}\;\textrm{v}\;\textrm{konfiguraci}\;q_f)</math>. Formálně by to šlo zapsat tak, že pro každý turingův stroj TS existuje ČRF <math>g</math> taková, že pro libovolnou konfiguraci <math>k</math> platí <math>kod(TS(k)) \simeq g(kod(k))</math>.
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 <math>\mbox{PRF} \subseteq \mbox{ORF} \subseteq \mbox{ČRF}</math>
Ostré inkluze
Platí: <math>\mbox{PRF} \subsetneq \mbox{ORF} \subsetneq \mbox{ČRF}</math>.
Č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 <math>f:=M_0(\mathbf{s})</math>. Problém je, že jsme si nezavedli nulární funkce (a tou by f byla).
Zvolme tedy <math>g:=S^1_2(\mathbf{s},\mathbf{I^2_2})</math>, což znamená, že <math>g(x,y)=y+1</math> (na první proměnné nezáleží). Pak máme <math>f:=M_1(g)</math>, dohromady tedy <math>f:=M_1\big(S^1_2(\mathbf{s},\mathbf{I^2_2})\big).</math>
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ě) #A(x,y) je ORF
##A je totální (je všude definovaná na všech dvojicích ordinálních čísel omega^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čí
##je A ČRF? (nějaký čachry s minimalizací) #A není PRF
##definuje se "strukturální" složitost PR programů (nechť PR programy jsou PR termy - tj. základní fce, substituce, primitivní rekurze) ##definuje se hloubka PR-termů - maximální počet do sebe zanořených for-cyklů (operátorů rekurze)
<math>hl(s)=hl(o) = hl(I^j_n) = 0</math>
<math>hl(S^m_n(f, g_1, g_2, ..., g_m)) = max(hl(f), hl(g_1), hl(g_2), ... hl(g_m))</math>
<math>hl(R^n_n(f, g)) = max(hl(f), hl(g) + 1))</math>
##definuje se třída funkcí <math>R_i</math> obsahující PR-programy hloubky nejvýše <math>i</math> ##fce <math>f_i</math> je z (<math>R_i</math> \ <math>R_{i-1}</math>) - je na ní potřeba aspoň <math>i</math> vnořených for-cyklů (s méně to nejde)
##sjednocení všech <math>R_i</math> je PRF ##teď se na <math>A(x,y)</math> nahlídne jako na množinu funkcí <math>f_x(y)</math> a dokáže se, že <math>f_x(x)</math> není z žádného <math>R_i</math>
##<math>A(x,y)</math> je rostoucí na obou proměnných ##jakákoliv fce z <math>R_i</math> <jakákoliv fce z <math>R_{i+1}</math> (síla <math>i</math> vnořených cyklů je menší než síla <math>i+1</math> vnořených cyklů)
##sporem, nechť <math>A(x,x)</math> je z PRF, pak je z nějakého <math>R_i</math>, tedy musí být <math>A(x,x) <f_{i+1}(x) < f_x(x)</math>, pro <math>x>i+1</math> SPOR
Primitivně a částečně rekurzivní funkce
:see wen:Primitive recursive function, wen:μ-recursive function
Částečně rekurzivní funkce
Základní funkce
nulová funkce
<math>\mathbf{o}(x) = 0 \quad (\forall x)</math>
function nulova(x) { return 0; }
následník
<math>\mathbf{s}(x) = x+1 \quad (\forall x)</math>
function succ(x) { return x+1; }
vydělení j-té složky
<math>\mathbf{I^j_n}(x_1,...,x_n) = x_j \quad (\forall j,n: 1 \le j \le n)</math>
function selekce<j>(<math>x_1,...,x_n</math>) { return <math>x_j</math>; }
Operátory
Všechny tři operátory mají v dolním indexu n, což značí, že výsledná funkce <math>\mathbf{h}</math> bude funkcí n proměnných.
substituce
<math>S^m_n(\mathbf{f},\mathbf{g_1},...,\mathbf{g_m})=\mathbf{h}</math>, kde
Univerzální funkce
Vlastnosti univerzální funkce (pro ČRF)
Predikát o konvergenci univerzální funkce
[[Státnice - Rekurzivní a rekurzivně spočetné množiny|Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti]]
Základní definice
Věta o selektoru
1-převeditelnost, m-převeditelnost
1-úplnost K
Další vztahy
Rekurzivní permutace
Myhillova věta
Rekurzivně spočetné predikáty
Postova věta a ostatní věty o RSM
Produktivní a kreativní množiny
Imunní a prosté množiny
[[Státnice - Algoritmicky nerozhodnutelné problémy|Algoritmicky nerozhodnutelné problémy]]
Definice
Halting problém
Ostatní problémy
[[Státnice - Věty o rekurzi|Věty o rekurzi a jejich aplikace, Riceova věta]]
Gödelovy věty
Gödelova věta o neúplnosti