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 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 kde :
je konečná množina vnitřních stavů
je konečná abeceda symbolů a znaků
je počáteční stav
je symbol reprezentující prázdný symbol ( neni součástí vstupní abecedy přijímaného řetězce)
je množina koncových stavů
přechodová funkce, kde:
znamená posun čtecí hlavy vlevo
znamená posun čtecí hlavy vpravo
znamená neposunutí čtecí hlavy
Pro srovnání, nedeterministický stroj se liší jen tím, že 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<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ů:
jump (M,N)
continue,
kde L je návěští (má tvar "k:", k přirozené, je nepovinné), 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 o jedničku
sníží se hodnota v poli o jedničku
test na hodnotu v poli ; 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 . Pokud je fce pro tuto n-tici definovaná, RAM program skončí a v registru 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 .
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 , která vypočte kód stavu stroje startujíciho ze stavu odpovídajícímu kódu po krocích. Pak už jen pomocí while cyklu přes to celé nalezneme posloupnost kroků do konečného stavu, tj.
. Formálně by to šlo zapsat tak, že pro každý turingův stroj TS existuje ČRF taková, že pro libovolnou konfiguraci platí .
:: 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 . Problém je, že jsme si nezavedli nulární funkce (a tou by f byla).
Zvolme tedy , což znamená, že (na první proměnné nezáleží). Pak máme , dohromady tedy
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)
##definuje se třída funkcí obsahující PR-programy hloubky nejvýše ##fce je z ( \ ) - je na ní potřeba aspoň vnořených for-cyklů (s méně to nejde)
##sjednocení všech je PRF ##teď se na nahlídne jako na množinu funkcí a dokáže se, že není z žádného
## je rostoucí na obou proměnných ##jakákoliv fce z <jakákoliv fce z (síla vnořených cyklů je menší než síla vnořených cyklů)
##sporem, nechť je z PRF, pak je z nějakého , tedy musí být , pro SPOR
Primitivně a částečně rekurzivní funkce
:see wen:Primitive%20recursive%20function, wen:μ-recursive%20function
Částečně rekurzivní funkce
Základní funkce
nulová funkce
function nulova(x) { return 0; }
následník
function succ(x) { return x+1; }
vydělení j-té složky
function selekce<j>() { return ; }
Operátory
Všechny tři operátory mají v dolním indexu n, což značí, že výsledná funkce bude funkcí n proměnných.
substituce
, 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
::
::
::