*Tento souhrn slouží pro přípravu k magisterským [státnicím](Státnice). Detailní informace o předmětu hledej na stránkách [Vyčíslitelnost  I](Vyčíslitelnost%20%20I) a [Vyčíslitelnost  II](Vyčíslitelnost%20%20II).*

## 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](http://www.mff.cuni.cz/studium/bcmgr/ok/i3b4.htm) státnicových otázek pro studijní obory [Teoretická informatika](Státnice%20-%20Informatika%20-%20I1:%20Teoretická%20informatika) a [Diskrétní modely a algoritmy](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](http://ktiml.mff.cuni.cz/%7Ekucerap/NTIN090/) – Podle mě super srozumitelný materiál, který pokrývá vše kromě Gödela!

Studijní obory [Softwarové systémy](Státnice%20-%20Informatika%20-%20I2:%20Softwarové%20systémy) a [Matematická lingvistika](Státnice%20-%20Informatika%20-%20I3:%20Matematická%20lingvistika) mají okruhy [Složitost](Státnice%20-%20Informatika%20-%20Složitost) a [Vyčíslitelnost](Státnice%20-%20Informatika%20-%20Vyčí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](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 machine equivalents](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](Státnice_-_Informatika_-_Vyčíslitelnost#Částečně%20rekurzivní%20funkce)

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

1. 
1. 

`<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 v<sub>1</sub>, v<sub>2</sub>, . . . v<sub>n</sub>
: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. $L R_i <- R_i + 1$
1. $L R_i <- R_i - 1$
1. $L R_i$ jump (M,N)
1. 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
1. sníží se hodnota v poli $R_i$ o jedničku
1. 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.
1. 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 <em>g<sub>i</sub></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 $\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](TIN064_ČRF%2C_ORF%2C_PRF#V.C3.BDpo.C4.8Detn.C3.AD_s.C3.ADla_TS_a_.C4.8CRF_je_ekvivalentn.C3.AD), [UTS](TIN064_Prerekvizity#Univerz.C3.A1ln.C3.AD_TS).

#### Důkazy ostatních definicí ####

Na přednášce nebylo...

### Vlastnosti efektivně vyčístlitelných funkcí ###

#### Postova věta ####

([wen:Post's theorem](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 $\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ě)
#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. $hl(s)=hl(o) = hl(I^j_n) = 0$
1. $hl(S^m_n(f, g_1, g_2, ..., g_m)) = max(hl(f), hl(g_1), hl(g_2), ... hl(g_m))$
1. $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 recursive function](wen:Primitive%20recursive%20function), [wen:μ-recursive function](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 ####

1. 
1. 
1. 
    * 
1. 
        :: 

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

* 
* 
* 

1. 

1. 
    * 

* 

## Materiály ##

* 
* 
* 
* 
* 
* 
*