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]]

: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 <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ů:

  1. <math>L R_i <- R_i + 1</math>

  2. <math>L R_i <- R_i - 1</math>

  3. <math>L R_i</math> jump (M,N)

  4. 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:

  1. zvýší se hodnota v poli <math>R_i</math> o jedničku

  2. sníží se hodnota v poli <math>R_i</math> o jedničku

  3. 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.

  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 <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)

  1. <math>hl(s)=hl(o) = hl(I^j_n) = 0</math>

  2. <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>

  3. <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

Materiály