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}\to \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 \to 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 \to$ 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 v₁, v₂, . . . v_n :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$

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 <em>g_i</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(\text{stroj}\text{je}\text{za}\text{s}\text{kroku}\text{v}\text{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_2^1(\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(S_2^1(\mathbf{s},{\mathbf{I}}_2^2)).$

• 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_n^j)=0$

2. $hl(S_n^m(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))$

##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(\forall x)$

function nulova(x) { return 0; }

• následník

$\mathbf{s}(x)=x+1(\forall x)$

function succ(x) { return x+1; }

• vydělení j-té složky

${\mathbf{I}}_{\mathbf{n}}^{\mathbf{j}}(x_1,...,x_n)=x_j(\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_n^m(\mathbf{f},{\mathbf{g}}_1,...,{\mathbf{g}}_{\mathbf{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

4.  :: 
   

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