Archiv/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 http://groups.yahoo.com/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 Státnice%20-%20Informatika%20-%20I1:%20Teoretická%20informatika a Státnice%20-%20Informatika%20-%20I4:%20Diskrétní%20modely%20a%20algoritmy:

:: 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 Státnice%20-%20Informatika%20-%20I2:%20Softwarové%20systémy a Státnice%20-%20Informatika%20-%20I3:%20Matematická%20lingvistika 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%20function

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%20machine%20equivalents

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.

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

$L R_i <- R_i + 1$
$L R_i <- R_i - 1$
$L R_i$ jump (M,N)
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:

zvýší se hodnota v poli $R_i$ o jedničku
sníží se hodnota v poli $R_i$ o jedničku
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.
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 gi (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%20theorem), 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

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 1: \̲m̲b̲o̲x̲{PRF} \subseteq…

Ostré inkluze

Platí:

ParseError: KaTeX parse error: Undefined control sequence: \mbox at position 1: \̲m̲b̲o̲x̲{PRF} \subsetne…

Č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ě) #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)

$hl(s)=hl(o) = hl(I^j_n) = 0$
$hl(S^m_n(f, g_1, g_2, ..., g_m)) = max(hl(f), hl(g_1), hl(g_2), ... hl(g_m))$
$hl(R^n_n(f, g)) = max(hl(f), hl(g) + 1))$

##definuje se třída funkcí $R_i$ obsahující PR-programy hloubky nejvýše $i$ ##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)

##sjednocení všech $R_i$ je PRF ##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$

## $A(x,y)$ je rostoucí na obou proměnných ##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ů)

##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%20recursive%20function, wen:μ-recursive%20function

Čá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

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

:: ::