Státnice - Informatika - Vyčíslitelnost: Porovnání verzí

Z ωικι.matfyz.cz
Přejít na: navigace, hledání
m (Reurzivně spočetné predikáty: typo)
(1-převeditelnost, m-převeditelnost: pozn.)
 
(Není zobrazeno 221 mezilehlých verzí od 70 dalších uživatelů.)
Řádka 1: Řádka 1:
== Algoritmicky vyčíslitelné funkce, jejich vlastnosti ==
+
''Tento souhrn slouží pro přípravu k magisterským [[Státnice|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 [http://www.mff.cuni.cz/studium/bcmgr/ok/i3b4.htm oficiálních] státnicových otázek pro studijní obory [[Státnice - Informatika - I1: Teoretická informatika|Teoretická informatika]] a [[Státnice - Informatika - I4: Diskrétní modely a algoritmy|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.
 +
* [http://ktiml.mff.cuni.cz/~kucerap/NTIN090/ Text P. Kučery] – Podle mě super srozumitelný materiál, který pokrývá vše kromě Gödela!
 +
Studijní obory [[Státnice - Informatika - I2: Softwarové systémy|Softwarové systémy]] a [[Státnice - Informatika - I3: Matematická lingvistika|Matematická lingvistika]] mají okruhy [[Státnice - Informatika - Složitost|Složitost]] a [[Státnice - Informatika - Vyčíslitelnost|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]]''
 
:''see [[wen:Computable function]]''
  
Postova věta ([[wen:Post's theorem]], WTF?), a uzavřenost PRF, ORF a ČRF na doplněk (ČRF ne), sjednocení, průnik, omezená kvantifikace, kvantifikace
+
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(<tt>H</tt>)''). Zastavovacímu symbolu (kro transparentnost) je přiřazeno slovo následovně: ''P(<tt>H</tt>)'' = ''<tt>'H'</tt>'', ikdyž to nehraje roli.
 +
<code>
 +
<pre>
 +
2-tag system (m=2)
 +
    m=2
 +
    Alphabet: {a,b,c,H}
 +
    Production rules:
 +
        a  -->  ccbaH
 +
        b  -->  cca
 +
        c  -->  cc
 +
 
 +
# Computation: 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>
 +
</code>
 +
 
 +
==== 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 ) ∈ Λ
 +
 
 +
 
 +
<tt>0 := λ ''f'' ''x''. ''x''</tt>
 +
<tt>1 := λ ''f'' ''x''. ''f'' ''x''</tt>
 +
<tt>2 := λ ''f'' ''x''. ''f'' (''f'' ''x'')</tt>
 +
<tt>3 := λ ''f'' ''x''. ''f'' (''f'' (''f'' ''x''))</tt>
 +
 +
<tt>SUCC := λ ''n'' ''f'' ''x''. ''f'' (''n'' ''f'' ''x'')</tt>
 +
<tt>PLUS := λ ''m'' ''n'' ''f'' ''x''. ''n'' ''f'' (''m'' ''f'' ''x'')</tt>
 +
 
 +
==== 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ů:
 +
# <math>L R_i <- R_i + 1</math>
 +
# <math>L R_i <- R_i - 1</math>
 +
# <math>L R_i</math> jump (M,N)
 +
# 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:
 +
# zvýší se hodnota v poli <math>R_i</math> o jedničku
 +
# sníží se hodnota v poli <math>R_i</math> o jedničku
 +
# 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.
 +
# 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>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 <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 - [[TIN064_ČRF,_ORF,_PRF#V.C3.BDpo.C4.8Detn.C3.AD_s.C3.ADla_TS_a_.C4.8CRF_je_ekvivalentn.C3.AD|ekvivalence]], [[TIN064_Prerekvizity#Univerz.C3.A1ln.C3.AD_TS|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)
 +
### <math>hl(s)=hl(o) = hl(I^j_n) = 0</math>
 +
### <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>
 +
### <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 ===
 
=== Částečně rekurzivní funkce ===
Tři základní funkce:
+
==== Základní funkce ====
# nula - o(x) = 0
+
* nulová funkce
# následník - s(x) = x+1
+
<math>\mathbf{o}(x) = 0 \quad (\forall x)</math>
# projekce - I_n^j; 1<=j<=n (z n cisel vydelim j-té cislo)
+
  
Tři základní operátory (odvozovací pravidla):
+
function nulova(x) { return 0; }
# S_n^m - substituce (volani podprogramu) - vstup vice fci, vystup jedna funkce
+
 
# R_n - primitivni rekurze - odpovida forcyklu
+
* následník
# M_n - minimalizace - odpovida while cyklu
+
<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<br>
 +
<math>\mathbf{h}(x_1,...,x_n) \simeq \mathbf{f}(\mathbf{g_1}(x_1,...,x_n),...,\mathbf{g_m}(x_1,...,x_n))</math>
 +
 
 +
Z uvedené definice je zřejmé, že <math>\mathbf{f}</math> je funkce m proměnných a všechny <math>\mathbf{g_i}</math> jsou funkce n proměnných.
 +
Pokud zavedeme konvenci, že <math>\vec x = (x_1,...,x_n)</math>, tak můžeme zjednodušeně psát
 +
<math>\mathbf{h}(\vec x) \simeq \mathbf{f}(\mathbf{g_1}(\vec x),...,\mathbf{g_m}(\vec x))</math>.
 +
 
 +
operator <math>S^m_n</math><<math>\mathbf{f},\mathbf{g_1},...,\mathbf{g_m}</math>>(<math>x_1,...,x_n</math>){
 +
  return <math>\mathbf{f}(\mathbf{g_1}</math>(<math>x_1,...,x_n</math>), ... , <math>\mathbf{g_m}</math>(<math>x_1,...,x_n</math>));
 +
}
 +
 
 +
Operátor substituce je základní prvek programování (v lib. prog. jazyce, co znám) &mdash; jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.
 +
 
 +
* primitivní rekurze
 +
<math>R_n(\mathbf{f},\mathbf{g})=\mathbf{h}</math>, kde<br>
 +
<math>\mathbf{h}(0,x_2,...,x_n) \simeq \mathbf{f}(x_2,...,x_n)</math><br>
 +
<math>\mathbf{h}(i+1,x_2,...,x_n) \simeq \mathbf{g}(i,\mathbf{h}(i,x_2,...,x_n),x_2,...,x_n)</math>
 +
 
 +
Z uvedené definice je zřejmé, že <math>\mathbf{f}</math> je funkce n-1 proměnných a <math>\mathbf{g}</math> je funkce n+1 proměnných.
 +
 
 +
operator <math>R_n\!</math><<math>\mathbf{f},\mathbf{g}</math>>(<math>x_1,x_2,...,x_n</math>){
 +
  pom := <math>\mathbf{f}</math>(<math>x_2,...,x_n</math>);
 +
  for i := 1 to <math>x_1</math> do
 +
    pom := <math>\mathbf{g}</math>(i-1, pom, <math>x_2,...,x_n</math>);
 +
  return pom;
 +
}
 +
 
 +
Je vidět, že operátor primitivní rekurze má sílu for-cyklu.
 +
 
 +
Proměnná <math>x_1</math> má zvláštní význam &mdash; slouží jako čítač.
 +
 
 +
Na přednášce se uváděl vysvětlující příklad na primitivní rekurzi pro n=1. Pak h(0)=konstanta a h(i+1)=g(i,h(i)). Malý problém je v tom, že jsme si nedefinovali nulární funkce a f by v tomto případě musela mít n-1=0 proměnných.
 +
 
 +
* minimalizace
 +
<math>M_n(\mathbf{f})=\mathbf{h}</math>, kde<br>
 +
<math>\mathbf{h}(x_1,...,x_n)\downarrow = z \iff \big(\mathbf{f}(x_1,...,x_n,z)\downarrow = 0 \And \forall j<z:  \mathbf{f}(x_1,...,x_n,j)\downarrow \ne 0\big)</math>
 +
 
 +
Z uvedené definice je zřejmé, že <math>\mathbf{f}</math> je funkce n+1 proměnných.
 +
 
 +
operator <math>M_n\!</math><<math>\mathbf{f}</math>>(<math>x_1,...,x_n</math>){
 +
  i:=0;
 +
  while (<math>\mathbf{f}</math>(<math>x_1,...,x_n</math>, i) != 0) do i++;
 +
  return i;
 +
}
 +
 
 +
Je vidět, že operátor minimalizace má sílu while-cyklu.
 +
Poslední proměnná ve funkci f (v pseudokódu označená jako <tt>i</tt>) má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší <tt>i</tt> takové, aby f vracela nulu.
 +
 
 +
Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná (výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostali na vstupu totální funkce, vrátili také totální funkci.
 +
 
 +
Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.
 +
 
 +
 
 +
Příklad: sčítání dvou čísel
 +
<math>R_2(I^1_1,S^1_3(s,I^2_3))</math><br>
 +
Příklad: <math>x_1=2; x_2=3;</math><br>
 +
<math>h(0,x_2)=I^1_1(x_2)=I^1_1(3)=3</math><br>
 +
<math>h(1,x_2)=s(I^2_3(0,h(0,x_2),x_2))=s(I^2_3(0,3,3))=s(3)=4</math><br>
 +
<math>h(2,x_2)=s(I^2_3(1,h(1,x_2),x_2))=s(I^2_3(1,4,3))=s(4)=5</math>
  
 
;Def Odvozeni funkce: posloupnost funkcí f0 .. fn = f, kde kazda funkce je bud základní funkce nebo vznikne použitím operátoru na predchozi funkce
 
;Def Odvozeni funkce: posloupnost funkcí f0 .. fn = f, kde kazda funkce je bud základní funkce nebo vznikne použitím operátoru na predchozi funkce
 
;Def Totální funkce: funkce je totální, pokud funkce (program) skončí na každem vstupu
 
;Def Totální funkce: funkce je totální, pokud funkce (program) skončí na každem vstupu
;Def Částečne rekurzivní funkce: funkce je částečně rekurzivní (ČRF), pokud ma odvození, obecně rekurzivní (ORF), pokud je ČRF a je totální, primitivně rekurzivní (PRF), pokud ma odvození pouze s použitím operatorů S_n^m a R_n (bez while)
+
;Def Částečne rekurzivní funkce (ČRF): funkce je částečně rekurzivní (ČRF), pokud odvození.
 +
;Def Obecně rekurzivní funkce (ORF): pokud je ČRF a je totální.
 +
;Def Primitivně rekurzivní (PRF): pokud ma odvození pouze s použitím operatorů S_n^m a R_n (bez minimalizace, tj bez while cyklu)
  
 
<math>PRF \subset ORF \subset CRF</math>
 
<math>PRF \subset ORF \subset CRF</math>
* ORF, ale není PRF - ackermanova funkce (potřebuje while)
+
Důkaz výše.
* ČRF, ale není ORF - nedefinovaná funkce
+
  
=== Ekvivalence různých matematických definic ===
+
=== Univerzální funkce ===
* TS (Turing)
+
* ČRF (Kleene)
+
* Postovy systémy ([[wen:Tag system]])
+
* lambda funkce
+
  
== Primitivně a částečně rekurzivní funkce ==
+
* existuje univerzální ČRF pro každou třídu ČRF o k proměnných, která dostane na vstup kód fce (e) a k-proměnných a vydá výsledek e-té funkce (ta univerzální funkce je tvaru minimalizace PRP), viz Kleeneho věta.
:''see [[wen:Primitive recursive function]], [[wen:μ-recursive function]]''
+
* třída PRF má svoji univerzální funkci, která ale sama do třídy PRF nepatří
== Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti ==
+
důkaz sporem: Nechť ''U(x, x)'' je univerzální PRF, která počítá výstup ''x''-té PRF na vstupu ''x''. Pak ''U(x, x)'' + 1 je také PRF (použitím operátoru substituce a funkce následníka). Protože ''U'' je univerzální funkce, platí, že <math>U(x, x) + 1 \simeq U(x_0, x)</math> pro nějaké <math>x_0</math>. Nyní přichází klíčový krok důkazu, kdy za ''x'' dosadíme <math>x_0</math> (tzn. [[wcs:Cantorova diagonální metoda]]) a dostáváme <math>U(x_0, x_0) + 1 \simeq U(x_0, x_0)</math>, což je spor. Předpoklad, že ''U'' je primitivně rekurzivní funkce, byl tedy chybný.
 +
(TODO - na přednášce používal doc. Kučera operator "mínus s tečkou", definovaný jako ''x-y'' pro ''x>=y'', a 0 pro ''x<y'', nazývaný ''aritmetický rozdíl''. Tento operátor zachovává totálnost.)
 +
 
 +
;Def Univerzální funkce pro k proměnných (numerace): funkce ''U'' je univerzální pro spočetnou třídu aritmetických funkcí ''k'' proměnných ''A'', pokud
 +
* Pro každé <math> e\; \lambda_{x_1, ..., x_k} U(e, x_1,..., x_k) </math> patří do ''A''
 +
* Pro každé <math>f \in A</math> existuje ''e'' tak, že <math>f(x_1, x_2, ..., x_k) \simeq \lambda_{x_1, ..., x_k} U(e, x_1,..., x_k)</math>
 +
''e'' se nazývá index funkce
 +
 
 +
;Def Gödelovská univerzální funkce
 +
Univerzální funkce je gödelovská, jestliže
 +
* Je efektivně vyčíslitelná
 +
* index složené funkce funkce lze efektivně zjistit z indexů skládaných funkcí, tj. pokud existuje efektivně vyčístlitelná <math>\alpha</math>, taková, že
 +
<math>U(p, U(q, x))\simeq U(\alpha(p, q), x) \simeq p \circ q (x)</math>
 +
 
 +
=== Vlastnosti univerzální funkce (pro ČRF) ===
 +
* Je taky ČRF
 +
* Nelze rozšířit na ORF (nemůže být definovaná všude &ndash; numeruje i programy, které jsou smyčka)
 +
Formální důkaz toho, že nejde rozšířit na ORF: Předpokládejme, že ''f'' je rozšíření na ORF. Položme <math>g(x) \simeq 1 - f(x, x) </math>. Jelikož ''f'' je ORF je i ''g'' ORF. Funkce g má svoje gödelovo číslo ''a'' a tedy <math>g(x) \simeq \Psi_1(a,x)</math>. Specielní případ, pro <math>x=a</math>, kdy
 +
<math>g(a) \simeq \Psi_1(a,a)</math>. A to je spor: <math>g(a) \simeq 1 - f(a, a)</math>, a protože ''f'' je rozšíření <math>\Psi_1</math>,  platí že
 +
<math>f(a, a) \simeq \Psi_1(a, a)</math> (g je ORF a tím pádem je <math>\Psi_1(a, a)</math> jistě definováno). No a tedy je <math>g(a) \simeq 1 - \Psi_1(a, a) \simeq \Psi_1(a, a)</math>, což asi pro každé kódování zvládnout nejde.
 +
 
 +
=== Predikát o konvergenci univerzální funkce ===
 +
* Predikát <math>\Psi_k(e, x_1, x_2, ...,  x_k)\uparrow</math> není RSP
 +
* Predikát <math>\Psi_k(e, x_1, x_2, ...,  x_k)\downarrow</math> je RSP, ale není ORP
 +
 
 +
'''Důkaz''': (je uveden pouze pro dvě proměnné, nikoli pro více) Pro spor přepdokládejme, že je RSP. Pak jeho charakteristická funkce je ČRF (označmě ji <math>\alpha</math>), která je definována právě když
 +
<math>\Psi_k(e, x_1, x_2,...,  x_k)\uparrow</math>. Tato ČRF má ale gödelovo číslo ''a'',  a tedy <math>\alpha(x) \simeq \Psi_k(a, x)</math>. No a teď zas ten specielní případ, <math>\alpha(a) \simeq \Psi_k(a, a)</math>. To je ale spor, protože  <math>\alpha(x) \simeq \Psi_k(x, x)</math> je  definováno právě když <math>\Psi_k(x, x)</math> není definováno (<math>\Psi_k(x, x)\uparrow</math>) (Mimochodem, tohle je ukázka Cantorovy diagonální metody, na diagonále jsou <math>\Psi_k(z, z)</math>)
 +
 
 +
Kdyby <math>\Psi_k(e, x_1, x_2, ..., x_k)\downarrow</math> byl ORP, musela by i jeho charakteristická funkce být ORF, tj definovaná pro všechny vstupy, tj musela bz být definovaná i pro úseky, kde <math>\Psi_k(e, x_1, x_2, ..., x_k)\uparrow</math> a to by byla ČRF, což podle předchozího není.
 +
 
 +
== [[Státnice - Rekurzivní a rekurzivně spočetné množiny|Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti]] ==
 
:''see [[wen:Recursive set]], [[wen:Recursively enumerable set]]''
 
:''see [[wen:Recursive set]], [[wen:Recursively enumerable set]]''
  
* <math>W_x \mbox{ (x-rekurzivně spočetná množina) } = dom(\varphi_x) = \{ y:\varphi_x(y) \} \downarrow</math>
+
=== Základní definice ===
* <math>K = \{ x:x \in W_x \} = \{x:\varphi_x(x) \downarrow \} = \{ x:\Psi_1(x,x) \downarrow \}</math>
+
*Predikáty ("vlastnost" - např. x < y, nebo x je elementem M)
*: <math>K</math> je množina funkcí, co konvergují na svém indexu.
+
*predikát je '''obecně rekurzivní''' (ORP), resp. '''primitivně rekurzivní''' (PRP), jestliže jeho charakteristická funkce je taková (ORF, resp. PRF)
 +
**ORP jsou právě ty, které jsou efektivně rozhodnutelné
 +
*predikát je '''rekurzivně spočetný''' (RSP), jestliže jeho obor pravdivosti je definičním oborem nějaké ČRF
 +
**tam, kde P neplatí, tam program není definován
 +
*množina M je '''rekurzivní''', jestliže její charakteristická fce je ORF
 +
**rekurzivní množina je taková, že o každém prvku dokážeme efektivně zjistit, zda do množiny patří či nikoliv
 +
**Rekurzivní množina je právě efektivně (algoritmicky) rozhodnutelná
 +
*množina M je '''rekurzivně spočetná''', jestliže je definičním oborem nějaké ČRF
 +
**rekurzivně spočetné množiny se nějaký program pouze zastaví, když prvek do množiny patří, jinak nic nevíme
 +
 
 +
=== Věta o selektoru ===
 +
Pro každý RSP <math>Q</math> k+1 proměnných existuje ČRF <math>\varphi</math> k proměnných, pro kterou platí
 +
 
 +
* <math>\varphi(x_1,...,x_k)\downarrow \Leftrightarrow \exists y Q(x_1,...,x_k,y)</math>
 +
 
 +
* <math>\varphi(x_1,...,x_k)\downarrow \Rightarrow Q\Big(x_1,...,x_k,\varphi(x_1,...,x_k)\Big)</math>.
 +
 
 +
Druhá řádka říká, že pro každý RSP <math>Q</math> umíme zkonstruovat takovou ČRF <math>\varphi</math>, která lze dosadit za poslední proměnnou <math>Q</math> (respektive její výsledek y) a pokud <math>\varphi</math> konverguje, tak <math>Q</math> platí. První řádka říká, že <math>\varphi</math> "se snaží seč může", tedy pokud nějaké y existuje, tak ho najde. (Nebýt této podmínky, šlo by za <math>\varphi</math> zvolit třeba prázdnou funkci.)
 +
 
 +
Predikát <math>Q</math> k+1 proměnných si můžeme představit jako relaci či graf (grafem se zde rozumí množina bodů, žádné hrany a vrcholy) v k+1 rozměrném prostoru (přirozených čísel ovšem, jak jinak). Predikát <math>Q(x_1,...,x_k,x_{k+1})\!</math> určuje, zda bod <math>(x_1,...,x_k,x_{k+1})</math> je v grafu, či nikoli. <math>\varphi</math> můžeme chápat jako funkci na k rozměrném prostoru takovou, že v grafu ''vybere'' v poslední proměnné právě jeden bod (pokud existuje). Celý tento odstavec je tu jen proto, aby vysvětlil název ''věta (či lemma) o selektoru'' a proč se říká, že ČRF mají RS graf. Klidně na něj zatím zapomeňte.
 +
 
 +
'''Důkaz''':
 +
Pro RSP <math>Q</math> existuje TS <math>T</math>, který se zastaví v přijímacím stavu, pokud <math>Q(x_1,...,x_k,y)</math>.
 +
 
 +
Definujme ORF
 +
<math>\beta(x_1,...,x_k,y,j) = 0 \Leftrightarrow T\mbox{ přijme vstup }x_1,...,x_k,y\mbox{ za }j\mbox{ kroků}</math>
 +
 
 +
Požadovaná ČRF je pak:
 +
 
 +
<math>\varphi(x_1,...,x_k) = \mu_{<y,j>}\beta(x_1,...,x_k,y,j)</math>
  
Množina <math>K</math> je rekurzivně spočetná, není rekurzivní, <math>\overline K</math> není rekurzivně spočetná.
+
Pokud totiž pro <math>x_1,...,x_k</math> nějaké <math>y</math>, takové že platí <math>Q(x_1,...,x_k,y)</math> existuje, tak se odpovídající TS zastaví nejvýše po <math>j</math> krocích, a my to zjistíme v <math><y,j></math>-té iteraci minimalizační funkce <math>\mu_{<y,j>}</math>.
:Kdyby <math>\overline K</math> byla rekurzivně spočetná, měla by index <math>x_0</math> (<math>\overline K = W_{x_0}</math>), což vede ke sporu: <math>x_0 \notin W_{x_0} \Leftrightarrow^* x_0 \in \overline K \Leftrightarrow^{**} x_0 \in W_{x_0}</math>
+
: * - z definice <math>\overline K</math>
+
: ** - předpoklad pro spor <math>\overline K</math> má index (<math>\overline K = W_{x_0}</math>)
+
  
 
=== 1-převeditelnost, m-převeditelnost ===
 
=== 1-převeditelnost, m-převeditelnost ===
 
* Množina <math>A</math> je 1-převeditelná na <math>B</math> (značíme <math>A \leq_1 B</math>), jestliže existuje prostá ORF taková, že <math>x \in A \Leftrightarrow f(x) \in B</math>.
 
* Množina <math>A</math> je 1-převeditelná na <math>B</math> (značíme <math>A \leq_1 B</math>), jestliže existuje prostá ORF taková, že <math>x \in A \Leftrightarrow f(x) \in B</math>.
** Množina M je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná funkce je na ni 1-převeditelná.
+
** Množina M je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převeditelná. (Pozn.: Nemá být nekonečná? Jak může být 1prvková množina převoditelná na dvojprvkovou?)
 
* Množina <math>A</math> je m-převeditelná na <math>B</math> (značíme <math>A \leq_m B</math>), jestliže existuje (ne nutně prostá) ORF taková, že <math>x \in A \Leftrightarrow f(x) \in B</math>.
 
* Množina <math>A</math> je m-převeditelná na <math>B</math> (značíme <math>A \leq_m B</math>), jestliže existuje (ne nutně prostá) ORF taková, že <math>x \in A \Leftrightarrow f(x) \in B</math>.
 
** Množina M je m-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina na ni je m-převeditelná.
 
** Množina M je m-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina na ni je m-převeditelná.
  
 
==== 1-úplnost K ====
 
==== 1-úplnost K ====
K je 1-úplná.
+
'''Věta:''' K je 1-úplná.
: Mějme libovolnou rekurzivně spočetnou množinu <math>W_x</math> a ČRF <math>\alpha(y,x,w)</math>, která ji popisuje.
+
 
 +
:'''Důkaz:''' Chceme ukázat, že pro každou rekursivně spočetnou množinu <math>W_x</math> je je <math>W_x \leq_1 K</math>, to  jest,  že exituje prostá ORF ''h'' taková, že <math>y \in W_x \Leftrightarrow h(x) \in K</math>. Mějme libovolnou rekurzivně spočetnou množinu <math>W_x</math> a ČRF <math>\alpha(y,x,w)</math>, která ji popisuje.
 
: Tedy <math>\alpha(y,x,w)\downarrow \Leftrightarrow^* y \in W_x \Leftrightarrow \Psi_1(x,y)\downarrow \Leftrightarrow \varphi_x(y)\downarrow</math> (na <math>w</math> hodnota <math>\alpha</math> nezávisí)
 
: Tedy <math>\alpha(y,x,w)\downarrow \Leftrightarrow^* y \in W_x \Leftrightarrow \Psi_1(x,y)\downarrow \Leftrightarrow \varphi_x(y)\downarrow</math> (na <math>w</math> hodnota <math>\alpha</math> nezávisí)
 
: Ze s-m-n dostáváme <math>\alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w)</math> (**)
 
: Ze s-m-n dostáváme <math>\alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w)</math> (**)
: Označíme-li <math>h(y,x) = s_2(a,y,x)</math> (<math>s_2</math> je ČRF a tedy i ORF), máme <math>y \in W_x \Leftrightarrow^* \alpha(y,x,w)\downarrow \Leftrightarrow^{**} \varphi_{h(y,x)}(w)\downarrow \Leftrightarrow^{***} \varphi_{h(y,x)}(h(y,x))\downarrow \Leftrightarrow h(y,x) \in K</math>
+
: Označíme-li <math>h(y,x) = s_2(a,y,x)</math> (<math>s_2</math> je PRF a tedy i ORF), máme <math>y \in W_x \Leftrightarrow^* \alpha(y,x,w)\downarrow\Leftrightarrow^{**} \varphi_{h(y,x)}(w)\downarrow \Leftrightarrow^{***} \varphi_{h(y,x)}(h(y,x))\downarrow \Leftrightarrow h(y,x) \in K</math>  
:* *** -- můžeme předpokládat <math>h(y,x) = w</math>, hodnota <math>\alpha</math> a tudíž ani <math>h</math> n <math>w</math> nezáleží.
+
:* *** -- můžeme předpokládat <math>h(y,x) = w</math>, hodnota <math>\alpha</math> a tudíž ani <math>h</math> na <math>w</math> nezáleží.
 
: Tedy <math>W_x \leq_1 K</math> pomocí funkce <math>\lambda y.h(y,x)</math>.
 
: Tedy <math>W_x \leq_1 K</math> pomocí funkce <math>\lambda y.h(y,x)</math>.
  
<math>K_0 = \{ \langle y,x \rangle : y \in W_x \}</math> je 1-úplná.
+
Také platí
: <math>K \leq_1 K_0</math> a <math>K</math> je 1-úplná.
+
* <math>K_0 = \{ \langle y,x \rangle : y \in W_x \}</math> je 1-úplná.
 +
* <math>K \leq_1 K_0</math> a <math>K</math> je 1-úplná.
 +
 
 +
:'''Poznámka:''' To vlastně říká, že halting problém je vzhledem k 1- převeditelnosti nejtěžší problém mezi rekursivně spočetnými problémy(<math>K_0 = \{ \langle y,x \rangle : y \in W_x \}</math> je definice halting problému)
  
 
==== Další vztahy ====
 
==== Další vztahy ====
Řádka 77: Řádka 373:
 
==== Myhillova věta ====
 
==== Myhillova věta ====
 
<math>A \equiv B \Leftrightarrow A \equiv_1 B</math>
 
<math>A \equiv B \Leftrightarrow A \equiv_1 B</math>
:Důkaz je ve Strojilovi na straně 5, zprava doleva spočívá v postupném generování grafu <math>h</math> tak, aby v kroku <math>n</math> platilo <math>\{0, ..., n\} \subseteq dom(h)</math> a <math>\{0,...,n\} \subseteq rng(h)</math>.
+
 
 +
:'''Důkaz''': Plán: v krocích budeme generovat graf <math>h</math> tak, že v kroce <math>n</math> bude platit
 +
<math>\{0,\ldots,n\} \subseteq dom(h), \qquad \{0,\ldots,n\} \subseteq rng(h) </math>.
 +
 
 +
Z toho plyne, že <math>h</math> bude definovaná na celém <math>\mathbb{N}</math> a bude na. Současně zajistíme, že <math>h</math> bude prostá.
 +
 
 +
Navíc budeme chtít, aby platilo <math>y \in A \Leftrightarrow h(y) \in B</math>, tedy aby <math>h</math> převáděla <math>A</math> na <math>B</math>.
 +
 
 +
'''Indukce:'''
 +
Začneme v bodě 0 a položíme <math>h(0)=f(0)</math>. Rozlišíme následující případy:
 +
 
 +
* <math>f(0)=0</math>: vše je v pořádku, <math>h(0)=f(0)=0</math> a <math>0 \in A \Leftrightarrow 0 \in B</math>, pokračujeme dalším prvkem.
 +
* <math>f(0) \neq 0</math>: rozlišíme dva podpřípady
 +
** <math>g(0)\neq 0</math>: vše v pořádku, definujeme <math>h(g(0))=0</math>. Tedy <math>0 \in dom(h) \cap rng(h)</math>.
 +
** <math>g(0)=0</math>: nemůžeme použít <math>h(g(0))=0</math>, protože v bodě 0 je již <math>h</math> definována jako <math>f(0)</math>. Najdeme tedy volný bod. Definujme <math>h(g(f(0)))=0</math>. Určitě <math>g(f(0))\neq 0</math>, protože <math>g</math> je prostá a <math>f(0)\neq 0</math>.
 +
 
 +
Tímto jsme opět dostali bod 0 do definičního oboru <math>h</math> i oboru hodnot. Zároveň funkci <math>h</math> definujeme podle <math>f</math> a <math>g</math>, tedy převádí vzájemně <math>A</math> na <math>B</math>.
 +
 
 +
'''Indukční krok:''' nechť v kroce <math>k</math> je <math>z</math> první volný prvek. Všechna čísla menší jak <math>z</math> máme v <math>dom(h)\cap rng(h)</math>. Podíváme se, zda je <math>f(z)</math> volný. Jestliže ano, položíme <math>h(z)=f(z)</math>.
 +
Jestliže <math>f(z)</math> není volný, hledám zig-zag další volný. Maximálně <math>z</math> prvků je blokovaných.
 +
 
 +
 
 +
:'''Důsledek''': <math>K \equiv K_0</math>, neboť <math>K \equiv_1 K_0</math>
  
 
=== Rekurzivně spočetné predikáty ===
 
=== Rekurzivně spočetné predikáty ===
* Je-li Q ORF, pak <math>\exists y Q</math> je rekurzivně spočetný predikát.
+
* Je-li <math>Q</math> ORP, pak <math>\exists y Q</math> je rekurzivně spočetný predikát (RSP).
 +
*: <math>\mu_y Q</math> je ČRF, její definiční obor je <math>\exists y Q</math>.
 
* Predikát <math>\exists y T_k(e,x_1,... ,x_k,y)</math> je univerzální RSP pro třídu RSP <math>k</math> proměnných.
 
* Predikát <math>\exists y T_k(e,x_1,... ,x_k,y)</math> je univerzální RSP pro třídu RSP <math>k</math> proměnných.
*: T_k je predikát z Kleeneho věty o normální formě, co říká že funkce <math>e</math> má při <math>y_0</math> krocích od konce mezivýsledek <math>y_1</math>. (<math>y=\langle y_0, y_1 \rangle</math>) Důkaz tvrzení je taky z Kleeneho věty.
+
*: <math>T_k</math> je predikát z Kleeneho věty o normální formě, co říká že funkce <math>e</math> má při <math>y_0</math> krocích od konce mezivýsledek <math>y_1</math>. (<math>y=\langle y_0, y_1 \rangle</math>). Důkaz tvrzení plyne z Kleeneho věty.
 +
* Doplněk nezachovává rekursivní spočenost (důkaz už byl)
 
* Konjunkce a disjunkce zachovávají rekurzivní spočetnost. (Průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.)
 
* Konjunkce a disjunkce zachovávají rekurzivní spočetnost. (Průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.)
*: Pro průnik spustíme oba programy současně a čekáme až se jeden zastaví.
+
*: Pro sjednocení spustíme oba programy současně a čekáme až se jeden zastaví. Pro průnik čekáme, až se zastaví oba.
 +
*: Důkaz pro průnik: <math>x \in A, x \in B</math> jsou RSP. Pomocí Kleeneho T Predikátu jde každý predikát zapsat v univerzálním tvaru <math>\exists z, T_k(a, x_1, .., x_k, z)</math>, kde ''a'' je gödelovo číslo predikátu. Tak zapíšeme<math> x \in A, x \in B</math> pomocí obecného T predikátu: <math>\exists z_1, T_k(a, x, z_1) \and \exists z_2, T_k(b, x, z_2)</math>. Nyní <math>z_1, z_2</math> zakódujeme do dvojice:  <math>\exists w, T_k(a, x, l(w)) \and T_k(b, x, r(w))</math>. Jelikož T predikár je PRP, můžeme to přepsat jako <math>\exists z, T_{k+2}(e, a, b, x, z)</math>. A teď se použije s-m-n věta. <math>\exists z, T_k(s(e, a, b), x, z)</math>. Obdobně pro sjednocení.
 
* Omezená kvantifikace <math>(\forall y)_{y \leq t}</math> a existenční kvantifikace (pro <math>k \geq 2</math>) zachovávají rekurzivní spočetnost.
 
* Omezená kvantifikace <math>(\forall y)_{y \leq t}</math> a existenční kvantifikace (pro <math>k \geq 2</math>) zachovávají rekurzivní spočetnost.
 
*: Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem, existenční kvantifikátor je rozveden ve Strojilovi na straně 6.
 
*: Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem, existenční kvantifikátor je rozveden ve Strojilovi na straně 6.
  
==== Postova věta ====
+
=== Postova věta a ostatní věty o RSM ===
Množina <math>M</math> je rekurzivní právě když <math>M</math> i <math>\overline M</math> jsou rekurzivně spočetné. Predikát <math>Q</math> je ORP právě když <math>Q</math> i <math>\neg Q</math> jsou RSP.
+
'''Věta (Postova)''': Množina <math>M</math> je rekurzivní právě když <math>M</math> i <math>\overline M</math> jsou rekurzivně spočetné. Predikát <math>Q</math> je ORP právě když <math>Q</math> i <math>\neg Q</math> jsou RSP.
: Důkaz: Zleva doprava triviální, zprava doleva intuitivně: <math>M = dom(P_1), \overline M = dom(P_2)</math>. Pustíme oba programy současně a čekáme, který se zastaví.
+
:'''Důkaz''': Zleva doprava triviální &ndash; přímo z definice. Zprava doleva intuitivně: <math>M = dom(P_1), \overline M = dom(P_2)</math>. Pustíme oba programy současně a čekáme, který se zastaví. Formálně pomocí věty o selektoru: <math>Q(x, y) = (x \in M \and y=1) \or (x \notin M \and y=0) </math>. Selektor je ČRF, která vždy konverguje (vždy existuje ''y'', je buď jedna, nebo nula). A máme charakteristickou funkci.
 +
 
 +
'''Věta''':Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.
 +
:'''Důkaz''': Máme dánu x-tou RSM. Vytvoříme množinu dvojic <math>R = \{ \langle z,y \rangle : z \in W_x \And y = z \}</math> (Predikát <math>Q(z, y) = z \in W_x \And y = z</math>). Množina R je rekurzivně spočetná, tedy má ČRF selektor <math>\varphi</math>, platí <math>dom(\varphi) = rng(\varphi) = W_x</math>. Myšlenka důkazu je, že body, kde <math>\varphi_x</math> konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude současně oborem hodnot.
 +
 
 +
'''Věta''':Každý obor hodnot ČRF je rekurzivně spočetná množina.
 +
:'''Důkaz''': Myšlenka: zkonstruujeme pseudoinverzní funkci k ČRF <math>\varphi</math>. Dána <math> M = rng(\varphi_x)</math>, kde <math>\varphi_x</math> je ČRF. Definujme predikát <math>Q(z, y) = \varphi_x(y) \simeq z</math>. Pak Q je RSP a jeho selektor je ČRF jejíž je M doménou.
 +
 
 +
'''Věta''': Množina je rekursivní <=> je oborem hodnot nějaké rostoucí úsekové ČRF. (úseková funkce je taková, jejímž def. oborem je počáční úsek <math>\mathbb{N}</math>)
 +
:'''Důkaz''':
 +
: "=>": U ČRF jsme použili selektor, jehož doménou byla doména charakteristické funkce množiny. Pokud víme, že je tato množina rekursivní, můžeme prvky seřadit do posloupnosti (až do vyčerpání množiny bude tato posloupnost všude definovaná). A dál použijeme minimalizaci: <math>\varphi(0) \simeq \mu_y(y \in M), \varphi(n+1) \simeq \mu_y(y>\varphi(n) \and y \in M)</math>. Pak <math>M = rng(\varphi)</math>.
 +
: "<=": Nechť <math>\varphi</math> je rostouci useková ČRF, <math>M = rng(\varphi)</math>. Patří-li y do M, pak <math>\exists x</math> takové, že  <math>\varphi(x) = y</math>, protože y je z oboru hodnot <math>\varphi</math>. Navíc víme, že <math>x \leq y</math>, to proto, že x, y jsou <math>\in \mathbb{N}</math> a funkce je rostoucí, a v <math>\mathbb{N}</math> "stoupání musí být větší, než diagonála". Při dotazu, jestli <math>y \in M</math> stačí projít všechny <math>x \leq y</math>, pak víme, že mezi těmi většimi ho už nenajdeme a tak máme definovanou ORF charakteristickou funkci.
 +
 
 +
'''Věta''': Množina je r.s. <=> je oborem hodnot prosté úsekové ČRF.
 +
:'''Důkaz''':
 +
: "<=" Obor jakékoli ČRF je r.s. množina z definice.
 +
: "=>" Z předchozí věty víme, že RM jsou generovány rostoucími úsekovými funkcemi. Vezměme množinu <math>B= \{<x,s>: \varphi(x)\downarrow za\;presne\;s\;kroku\}</math>, <math>\varphi(x)</math> je ČRF pro kterou <math>dom(\varphi) = M</math>. Množina B je rekurzivní, pro každou dvojici lze rozhodnout, jestli <math>\varphi(x)</math> zkonverguje po s krocích. Funkce generující B je přitom rostoucí (z předchozí věty, B je rekursivní) a ze l(f) je v M. Formálně můžeme definovat <math>g(x) = (f(x))_{2,1}</math>, pak g je ČRF, <math>rng(g) = M</math> a ''g'' je prostá (růst záležel na kódování dvojice <x,s>, ''f'' však nemůže vygenerovat ''x'' dvakrát, bylo řečeno ''přesně s kroků'')
 +
 
 +
'''Důsledek''': Množina M je nekonečná, pak M je rekurzivní <=> lze generovat rostoucí ORF.
 +
 
 +
'''Důsledek''': Množina M je nekonečná, pak M je r.s. <=> lze generovat prostou ORF.
 +
 
 +
'''Věta''': Každá nekonečná r.s. množina obsahuje nekonečnou rekurzivní podmnožinu.
 +
:'''Důkaz''':
 +
: <math>f</math> je prostá ORF, <math>range(f) = M</math>, vyber rostoucí podposloupnost <math>h(0) \simeq 0</math>, <math>h(n+1) \simeq f(\mu_y(f(y) > h(n)))</math>, <math>h</math> je ORF, roste, <math>range(h)=A \subseteq M</math>
 +
 
 +
==== Produktivní a kreativní množiny ====
 +
* '''Definice''': Množina A je ''produktivní'', pokud existuje ČRF &phi; tž. <math>W_x\subseteq A\implies\varphi(x)\downarrow \and \varphi(x)\in A\setminus W_x</math>
 +
* '''Definice''': Množina B je ''kreativní'', pokud je r.s. a <math>\bar{B}</math> je produktivní.
 +
* Příklady
 +
** K je kreativní - je RS a <math>\bar{K}</math> je produktivní, za &phi; se zvolí identita
 +
* Vlastnosti
 +
** Ke každé ''produktivní'' množině A existuje ''produktivní'' ORF f, f=&phi;(g(x)) - g(x) spočítá index 'podobného' programu, který je navíc totální pro jazyky mimo A
 +
** Ke každé ''produktivní'' množině A existuje ''produktivní'' ORF bijekce &phi; (dá se sestrojit s pomocí původní ''produktivní'' ORF)
 +
** Každá ''produktivní'' množina A obsahuje nekonečnou RSM - prázdná množina patří do A a &phi; nám vrátí vždy nový prvek z A, který se dá přidat k výchozí podmnožině A, atd.
 +
* Ekvivalence
 +
** A je ''produktivní'', <math>\bar{K}</math> je 1-převeditelná na A, <math>\bar{K}</math> je m-převeditelná na A
 +
** B je ''kreativní'', B je 1-úplná, B je m-úplná
  
Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.
+
==== Imunní a prosté množiny ====
: Důkaz: Vytvoříme množinu dvojic <math>R = \{ \langle z,y \rangle : z \in W_x \And y = z \}</math>. Množina R je rekurzivně spočetná, tedy má ČRF selektor <math>\varphi</math>, platí <math>dom(\varphi) = rng(\varphi) = W_x</math>. Myšlenka důkazu je, že body, kde <math>\varphi_x</math> konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude současně oborem hodnot.
+
* '''Definice''': Množina B je ''imunní'', pokud je nekonečná a neobsahuje nekonečou r.s. množinu.
 +
* '''Definice''': Množina B je ''prostá'', pokud je r.s. a její doplněk je imunní množina.
 +
'''Věta''': Existuje prostá množina
  
Každý obor hodnot ČRF je rekurzivně spočetná množina.
+
== [[Státnice - Algoritmicky nerozhodnutelné problémy|Algoritmicky nerozhodnutelné problémy]] ==
: Důkaz: Zkonstruujeme pseudoinverzní funkci <math>h</math> k ČRF <math>\varphi</math>.
+
  
== Algoritmicky nerozhodnutelné problémy ==
+
=== Definice ===
 
:''see [[wen:List of undecidable problems]]''
 
:''see [[wen:List of undecidable problems]]''
 +
Uvažujme rozhodovací problémy - odpověď je buď ''ANO'' nebo ''NE''. Instance tohoto problému nechť jsou kódována v abecedě <math>\Sigma = \{0, 1\}</math> Definujme jazyk kladných a záporných instancí problému. O jazyku řekneme, že ''rekursivní'', pokud ho řeší nějaký (deterministický) turingův stroj. Slovem ''řešit problém'' budeme popisovat situaci, kdy se stroj pro všechny kladné instance zastaví v koncovém stavu, kde přijímá a pro všechny ostatní instance problému se zastaví ve stavu, kde odmítá.
  
Halting problém, přičinlivý bobr a tak.
+
'''Definice''': Problém je ''algoritmicky rozhodnutelný'', pokud je jazyk jeho kladných instancí rekursivní. Jazyk, který není algoritmicky rozhodnutelný je ''algoritmicky nerozhodnutelný''.
  
== Věty o rekurzi a jejich aplikace ==
 
* Ladova skripta str.11, o pevnem bode,
 
  
* pouziti v logice, godelovy vety?
+
=== Halting problém ===
* paradox lhare
+
* Halting problém, z Johančiných pohádek
* riceova veeta je aplikaci v. o rekurzi
+
:Připomenu definici: neexistuje algoritmus, který by pro daný turináč a daný vstup dokázal rozhodnout, zda se turingáč na tomto vstupu zastaví. Pro důkaz použijeme pár myšlenek, které je dobré si zapamatovat, protože se s nimi nevidíme naposled. První z nich je (překvapivě) myšlenka UTS, druhou je otázka zastavení algoritmu na jeho vlastním kódu a třetí myšlenkou je přiřadit výsledky něčeho úmyslně opačně - nelogicky: když se něco povede, 0, když nepovede, 1. Z tohohle všeho dohromady kouká nějaký slibný spor, tak teď si to konečně aplikujeme na náš konkrétní úkol.
* veta o rekurzi (o \E pevneho bodu) s dukazem
+
* Veto o \Inf pevnych bodu
+
  
=== Věta o rekurzi ===
+
:'''Důkaz (pomocí UTS)''': provedeme sporem, předpokládáme, že existuje algoritmus H(M,K), co mu předhodíme turingáč M a vstup K a on řekne, jestli tenhle vztah má budoucnost :). Tedy vždy se zastaví a řekne 0 (nemá), nebo 1 (má). Pomocí něj sestrojíme kapku brutálnější algoritmus Alg(K), který se nad daným kódem programu zastaví právě tehdy, když se tento program sám se na svém vlastním kódu nezastaví. Tedy Alg(K) zastaví <=> U(K,K) nezastaví. Prostě algoritmus Alg říká: mně se líbí program, co nesežere svůj vlastní vstup, a tak se na něm zastavím, naopak program, co svůj vlastní vstup sežere, se mi nelíbí, takže se na něm třeba zacyklím a prostě trucuju :). Alg(K) definujeme podle výsledku výše zmíněného algoritmu H (který se vždy zastaví a něco řekne, takže my ho provedem a podle toho, co řekl, se rozhodnem): H(U(K,K),K) = 0 => Alg(K) zastaví, H(U(K,K),K) = 1 => Alg(K) zacyklí. Celá tahle prasárna jde provést právě proto, co jsme si na začátku definovali, tedy že algoritmus H existuje a vždy se zastaví. No a teď už asi nikoho nepřekvapí, že po tak ďábelské definici algoritmu Alg snadno vykouzlíme spor - pustíme ho na jeho vlastním kódu. Potom Alg(Alg) zastaví <=> U(Alg,Alg) nezastaví <=> Alg(Alg) nezastaví. Tohle ukazuje, že původní algoritmus H (který rozhoduje o zastavení) je zvrácený a nemůže existovat :).
Jestliže f je ČRF jedné proměnné, potom existuje <math>a</math> takové, ze <math>\varphi_{f(a)}(x) \simeq \varphi_a (x)</math> pro každé <math>x</math>.
+
: Říká, ze existuje pevny bod zobrazeni f. (<math>\varphi</math> je asi univerzální funkce jedné proměnné)
+
  
Důkaz:
+
:'''Důkaz (pomocí ČRF)''': Z kleeneho věty víme, že existuje efektivní očíslování pro třídu ČRF a její univerzální funkce. vezměme množinu <math>K = \{x: \varphi_x(x)\downarrow\} = \{x: \Psi(x, x)\downarrow\}</math>. Ta není rekursivní (pokud by byla, tak bychom mohli dodefinovat funkci <math>\alpha</math> takovou, že <math>\alpha \downarrow \Leftrightarrow \varphi_x(x) \uparrow</math>. Ta by byla r.s. a měla gödelovo číslo e, takže <math>\varphi_e(e) \simeq \alpha(e)</math> takže <math>\alpha(e) \downarrow \Leftrightarrow \varphi_e(e) \uparrow \Leftrightarrow \alpha(e) \uparrow</math>). No a tím spíš není rekursivní <math>K_0 = \{<x, y>: \varphi_x(y)\downarrow \}</math>, protože <math>K \leq_1 K_0</math>.
:<math>\varphi_{f(s_1(z,z))}(x) \simeq \Psi_2(e,z,x) \simeq^{smn} \Psi_1(s_1(e,z), x) \simeq \varphi_{s_1(e,z)}(x)</math>
+
:*<math>s_1(z,z)</math> je funkce se s-m-n věty, která dělá totéž co z, ale má první parametr fixovaný na hodnotu z
+
:*e je index programu, který počítá výraz vlevo (tj. <math>s_1(z,z)</math>, pak <math>f(s_1(z,z))</math>, a vzniklou funkci aplikuje na x)
+
:Pak položíme <math>z=e</math> a <math>a=s_1(e,e)</math> a máme to.
+
  
=== Riceova věta ===
+
=== Ostatní problémy ===
Jestliže <math>\mathcal{A}</math> je třída ČRF (jedné proměnné), ktera je netriviální, potom <math>A_{\mathcal{A}} = \{ x : \varphi_x \in \mathcal{A} \}</math> je nerekurzivní.
+
  
:Dokazuje se sporem. Nechť <math>A</math> je rekurzivní. Potom lze vytvořit ORF <math>f</math> takovou, že všechny prvky z <math>A</math> zobrazí na nějaký prvek <math>b \notin A</math> a všechny prvky mimo a zobrazí na nějaký prvek <math>a \in A</math>. Podle věty o rekurzi existuje nějaký pevný bod <math>f</math> <math>u_0</math>, že platí <math>\varphi_{u_0} = \varphi_{f(u_0)}</math>.
+
* Je jazyk přijímaný daným TS prázný/neprázný/konečný?
:Tedy <math>u_0 \in A \Rightarrow f(u_0) = b \notin A</math> a <math>u_0 \notin A \Rightarrow f(u_0) = a \in A</math>. Což je ovšem spor, protože <math>u_0</math> a <math>f(u_0)</math> jsou indexy stejné funkce, takže obě čísla buď v <math>A</math> leží nebo neleží.
+
* Riceova věta
 +
* Postův korespondeční problém PKP (i s omezením na iniciální řešení IPKP).  
 +
:Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:
 +
:<math>S = \{ (\alpha_1,\beta_1),\,...,\,(\alpha_k,\beta_k) \}</math>, kde <math>k \geq 1</math> a <math>\alpha_i, \beta_i</math> jsou řetězce nad nějakou [[abeceda|abecedou]].
  
Nejedná se o třídu programů, ale funkcí. Tedy i pro jednoprvkovou <math>\mathcal{A}</math> bude <math>A_{\mathcal{A}}</math> nekonečná a nerekurzivní. (Každá funkce je vyčíslována nekonečně mnoha programy a rozhodnout o jejich ekvivalenci efektivně nelze.)
+
:Řešením Postova systému je každá neprázdná posloupnost přirozených čísel I:
 +
:<math>I = \{ i_1,\,...,\,i_m \}</math>, kde <math>1 \leq i_j \leq k</math> a <math>m \geq 1</math>, pro kterou platí <math>\alpha_{i_1}...\alpha_{i_m} = \beta_{i_1}...\beta_{i_m}</math>.
  
=== Věta o generování pevných bodů ===
+
:Postův korespondenční problém zní: ''Existuje pro daný Postův systém řešení?''
Pro každou částečně rekurzivní funkci <math>f</math> existuje prostá rostoucí PRF <math>g</math> taková, že platí <math>\varphi_{f(g(j))}(x) \simeq \varphi_{g(j)}(x)</math>.
+
  
:Tedy <math>g</math> rostoucím způsobem generuje nekonečně mnoho pevných bodů funkce <math>f</math>.
+
:Příklad: Systém <math>S_1 = \{ (b,bbb),\,(babbb,ba),\,(ba, a) \}</math> má řešení <math>I = \{ 2,\,1,\,1,\,3 \}</math>: <code>babbb b b ba = ba bbb bbb a</code>.
 +
:Systém <math>S_2 = \{ (ab,abb),\,(a,ba),\,(b,bb) \}</math> řešení nemá.
  
Důkaz:
+
:Lze ukázaat IPKP <=> TS zastaví nad slovem ''u''.
:<math>\varphi_{f(s_2(z,z,j))}(x) \simeq \Psi_3(e,z,j,x) \simeq \Psi_1(s_2(e,z,j), x) \simeq \varphi_{s_2(e,z,j)}(x)</math>
+
 
:* <math>e</math> podobně jako u věty o rekurzi schválně počítá levou stranu
+
* Pro bezkontextové gramatiky G1,G2 je algoritmicky nerozhodnutelné zda L(G1)∩L(G2)={}.
:Zvolíme <math>g(j) = s_2(e,e,j)</math>.
+
:Důkaz: převedeme PKP na daný problém máme PKP [u<sub>1</sub>,v<sub>1</sub>],..., [u<sub>n</sub>,v<sub>n</sub>]
 +
:zvolíme nové terminály a1,,an pro kódy indexů
 +
:G1: S→ u<sub>i</sub>Sa<sub>i</sub> | u<sub>i</sub>a<sub>i</sub> generuje slova u<sub>i<sub>1</sub></sub>... u<sub>i<sub>k</sub></sub>a<sub>i<sub>k</sub></sub>... a<sub>i<sub>1</sub></sub>
 +
:G2: S→ v<sub>i</sub>Sa<sub>i</sub> | v<sub>i</sub>a<sub>i</sub> generuje slova v<sub>i<sub>1</sub></sub>... v<sub>i<sub>k</sub></sub>a<sub>i<sub>k</sub></sub>... a<sub>i<sub>1</sub></sub>
 +
:PKP má řešení právě když L(G1) ∩L(G2)≠{}
 +
:u-část = v-část + složky a<sub>i<</sub> zajišťují stejné pořadí
 +
*Je algoritmicky nerozhodnutelné, zda je bezkontextová gramatika víceznačná.
 +
:Důkaz:
 +
:S → S1 | S2
 +
:S1 → u<sub>i</sub>S1a<sub>i</sub> | u<sub>i</sub>a<sub>i</sub>
 +
:S2 → v<sub>i</sub>S2a<sub>i</sub> | v<sub>i</sub>a<sub>i</sub>
 +
:PKP má řešení právě když je gramatika víceznačná
 +
 
 +
== [[Státnice - Věty o rekurzi|Věty o rekurzi a jejich aplikace, Riceova věta]] ==
 +
 
 +
[http://wiki.matfyz.cz/index.php?title=TIN064_V%C4%9Bty_o_rekurzi Matfyz Wiki: Věty o rekurzi]
 +
 
 +
TODO, chybělo jako podotázka
  
 
== Gödelovy věty ==
 
== Gödelovy věty ==
Řádka 147: Řádka 517:
 
B \subseteq W_y \\
 
B \subseteq W_y \\
 
W_x \cap W_y = \emptyset
 
W_x \cap W_y = \emptyset
\end{matrix} \Bigg \} \Rightarrow \varphi(x,y)\downarrow \and \varphi(x,y)\notin W_x \cup W_y</math><br>Tj. z indexů aproximace A a B se dá efektivně najít další box, který leží mimo tu aproximaci.
+
\end{matrix} \Bigg \} \Rightarrow \varphi(x,y)\downarrow \and \varphi(x,y)\notin W_x \cup W_y</math><br>Tj. z indexů aproximace A a B se dá efektivně najít další bod, který leží mimo tu aproximaci.
  
 
;Gödelova věta o neúplnosti (1. část)
 
;Gödelova věta o neúplnosti (1. část)
Řádka 162: Řádka 532:
 
Věta: Jestliže teorie T 1. řádu má základní aritmetickou sílu a je bezesporná, pak
 
Věta: Jestliže teorie T 1. řádu má základní aritmetickou sílu a je bezesporná, pak
 
# množina formulí dokazatelných v T není rekurzivní
 
# množina formulí dokazatelných v T není rekurzivní
 +
#:Vezmu r.s. efektivně neoddělitelné A,B tž. <math>x\in A\implies\vdash_T G(\bar{x})</math> a <math>x\in B\implies\vdash_T \neg G(\bar{x})</math>.
 +
#:Vezmeme <math>A_1=\{x;\vdash_T G(\bar{x})\}</math>, <math>B_1=\{x;\vdash_T \neg G(\bar{x})\}</math> (<math>A\subseteq A_1</math>, <math>B\subseteq B_1</math>). Z bezespornosti A<sub>1</sub> a B<sub>1</sub> disjunktní a nejsou rekurzivní (separovaly by).
 
# je-li T navíc axiomatizovatelná, pak
 
# je-li T navíc axiomatizovatelná, pak
 
#* existuje uzavřená formule v F taková, že F je nerozhodnutelná v T (tj. z T nevyplývá ani F, ani <math>\neg F</math>)
 
#* existuje uzavřená formule v F taková, že F je nerozhodnutelná v T (tj. z T nevyplývá ani F, ani <math>\neg F</math>)
 +
#::Množiny A<sub>1</sub> a B<sub>1</sub> z bodu (1) jsou nyní r.s. a umím tedy efektivně určit bod mimo ně (číslo fle nedokazatelne ani nevyvratitelné v T).
 
#* v T nelze dokázat vlastní bezespornost (za o něco silnějších předpokladů o teorii T -- např. <math>\Sigma_1-\mbox{indukce}</math>)
 
#* v T nelze dokázat vlastní bezespornost (za o něco silnějších předpokladů o teorii T -- např. <math>\Sigma_1-\mbox{indukce}</math>)
 +
 +
== Materiály ==
 +
* [http://ktiml.mff.cuni.cz/~kucerap/NTIN090/ Text P. Kučery] &ndash; Podle mě super srozumitelný materiál, který pokrývá vše kromě Gödela!
 +
* [http://atrey.karlin.mff.cuni.cz/~johanka/vyuka/pohadky_vycislitelnost.html Pohádky z vyčíslitelnosti] &ndash; velmi neformální úvod do problematiky
 +
* [[TIN064_wiki-skripta|Wiki skripta z vyčíslitelnosti]] &ndash; neúplná, ale podrobná
 +
* [[Vyčíslitelnost I]] &ndash; stránka předmětu na wiki, obsahuje odkazy na další materiály
 +
* Pavliska V., Vyčíslitelnost a Složitost 1 a 2, Ostravská Univerzita, [http://www1.osu.cz/home/habibal/kurzy/vysl1.pdf] a [http://www1.osu.cz/home/habibal/kurzy/vysl2.pdf]
 +
* Demuth O., R. Kryl R., Kučera A., Teorie algoritmů I a II, skripta MFF-UK
 +
* Češka M., Vojnar T., Smrčka A., Teoretická informatika, VUT Brno [http://www.fit.vutbr.cz/study/courses/TIN/public/Texty/oporaTIN.pdf]
 +
 +
[[Category: Státnice Informatika Mgr.]]

Aktuální verze z 10. 6. 2015, 21:09

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[editovat | editovat zdroj]

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 [1]. 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.

Algoritmicky vyčíslitelné funkce, jejich vlastnosti[editovat | editovat zdroj]

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 $ 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[editovat | editovat zdroj]

wen:Turing machine equivalents

Turingův stroj, definice[editovat | editovat zdroj]

(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[editovat | editovat zdroj]

Viz níž Státnice_-_Informatika_-_Vyčíslitelnost#Částečně rekurzivní funkce

Postovy systémy, definice[editovat | editovat zdroj]

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.

2-tag system (m=2)
    m=2
    Alphabet: {a,b,c,H} 
    Production rules:
         a  -->  ccbaH
         b  -->  cca
         c  -->  cc

# Computation: 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).

Lambda kalkulus, definice[editovat | editovat zdroj]

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

  1. Pokud x je proměnná, pak x ∈ Λ
  2. Pokud x je proměnná a M ∈ Λ, pak ( λ x . M ) ∈ Λ
  3. 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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

ČRF => TS (každá ČRF je turingovsky vyčíslitelná)[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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í[editovat | editovat zdroj]

Na přednášce nebylo...

Vlastnosti efektivně vyčístlitelných funkcí[editovat | editovat zdroj]

Postova věta[editovat | editovat zdroj]

(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[editovat | editovat zdroj]

Neostré inkluze[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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ě)
  1. A(x,y) je ORF
    1. A je totální (je všude definovaná na všech dvojicích ordinálních čísel omega^2)
    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čí
    3. je A ČRF? (nějaký čachry s minimalizací)
  2. A není PRF
    1. definuje se "strukturální" složitost PR programů (nechť PR programy jsou PR termy - tj. základní fce, substituce, primitivní rekurze)
    2. 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 $
      2. $ hl(S^m_n(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)) $
    3. definuje se třída funkcí $ R_i $ obsahující PR-programy hloubky nejvýše $ i $
    4. 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)
    5. sjednocení všech $ R_i $ je PRF
    6. 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 $
    7. $ A(x,y) $ je rostoucí na obou proměnných
    8. 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ů)
    9. 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[editovat | editovat zdroj]

see wen:Primitive recursive function, wen:μ-recursive function

Částečně rekurzivní funkce[editovat | editovat zdroj]

Základní funkce[editovat | editovat zdroj]

  • 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[editovat | editovat zdroj]

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
$ \mathbf{h}(x_1,...,x_n) \simeq \mathbf{f}(\mathbf{g_1}(x_1,...,x_n),...,\mathbf{g_m}(x_1,...,x_n)) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce m proměnných a všechny $ \mathbf{g_i} $ jsou funkce n proměnných. Pokud zavedeme konvenci, že $ \vec x = (x_1,...,x_n) $, tak můžeme zjednodušeně psát $ \mathbf{h}(\vec x) \simeq \mathbf{f}(\mathbf{g_1}(\vec x),...,\mathbf{g_m}(\vec x)) $.

operator $ S^m_n $<$ \mathbf{f},\mathbf{g_1},...,\mathbf{g_m} $>($ x_1,...,x_n $){
  return $ \mathbf{f}(\mathbf{g_1} $($ x_1,...,x_n $), ... , $ \mathbf{g_m} $($ x_1,...,x_n $));
}

Operátor substituce je základní prvek programování (v lib. prog. jazyce, co znám) — jednoduše úlohu, kterou mám řešit, vyřeším pomocí funkcí, které už naprogramoval někdo dřív.

  • primitivní rekurze

$ R_n(\mathbf{f},\mathbf{g})=\mathbf{h} $, kde
$ \mathbf{h}(0,x_2,...,x_n) \simeq \mathbf{f}(x_2,...,x_n) $
$ \mathbf{h}(i+1,x_2,...,x_n) \simeq \mathbf{g}(i,\mathbf{h}(i,x_2,...,x_n),x_2,...,x_n) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce n-1 proměnných a $ \mathbf{g} $ je funkce n+1 proměnných.

operator $ R_n\! $<$ \mathbf{f},\mathbf{g} $>($ x_1,x_2,...,x_n $){
  pom := $ \mathbf{f} $($ x_2,...,x_n $);
  for i := 1 to $ x_1 $ do
    pom := $ \mathbf{g} $(i-1, pom, $ x_2,...,x_n $);
  return pom;
}

Je vidět, že operátor primitivní rekurze má sílu for-cyklu.

Proměnná $ x_1 $ má zvláštní význam — slouží jako čítač.

Na přednášce se uváděl vysvětlující příklad na primitivní rekurzi pro n=1. Pak h(0)=konstanta a h(i+1)=g(i,h(i)). Malý problém je v tom, že jsme si nedefinovali nulární funkce a f by v tomto případě musela mít n-1=0 proměnných.

  • minimalizace

$ M_n(\mathbf{f})=\mathbf{h} $, kde
$ \mathbf{h}(x_1,...,x_n)\downarrow = z \iff \big(\mathbf{f}(x_1,...,x_n,z)\downarrow = 0 \And \forall j<z: \mathbf{f}(x_1,...,x_n,j)\downarrow \ne 0\big) $

Z uvedené definice je zřejmé, že $ \mathbf{f} $ je funkce n+1 proměnných.

operator $ M_n\! $<$ \mathbf{f} $>($ x_1,...,x_n $){
  i:=0;
  while ($ \mathbf{f} $($ x_1,...,x_n $, i) != 0) do i++;
  return i;
}

Je vidět, že operátor minimalizace má sílu while-cyklu. Poslední proměnná ve funkci f (v pseudokódu označená jako i) má zvláštní význam. Snažíme se ji minimalizovat, to jest najít nejmenší i takové, aby f vracela nulu.

Pokud se jako f předá funkce, která nikdy nevrací nulu, tak operátor minimalizace vytvoří funkci, která nebude nikde definovaná (výše uvedený pseudokód se zacyklí). To se u předchozích operátorů stát nemohlo: pokud dostali na vstupu totální funkce, vrátili také totální funkci.

Pokud nechceme zavádět nulární funkce, je nutné definici operátoru minimalizace doplnit o podmínku, že f je funkce alespoň dvou proměnných.


Příklad: sčítání dvou čísel

$ R_2(I^1_1,S^1_3(s,I^2_3)) $
Příklad: $ x_1=2; x_2=3; $
$ h(0,x_2)=I^1_1(x_2)=I^1_1(3)=3 $
$ h(1,x_2)=s(I^2_3(0,h(0,x_2),x_2))=s(I^2_3(0,3,3))=s(3)=4 $
$ h(2,x_2)=s(I^2_3(1,h(1,x_2),x_2))=s(I^2_3(1,4,3))=s(4)=5 $
Def Odvozeni funkce
posloupnost funkcí f0 .. fn = f, kde kazda funkce je bud základní funkce nebo vznikne použitím operátoru na predchozi funkce
Def Totální funkce
funkce je totální, pokud funkce (program) skončí na každem vstupu
Def Částečne rekurzivní funkce (ČRF)
funkce je částečně rekurzivní (ČRF), pokud má odvození.
Def Obecně rekurzivní funkce (ORF)
pokud je ČRF a je totální.
Def Primitivně rekurzivní (PRF)
pokud ma odvození pouze s použitím operatorů S_n^m a R_n (bez minimalizace, tj bez while cyklu)

$ PRF \subset ORF \subset CRF $ Důkaz výše.

Univerzální funkce[editovat | editovat zdroj]

  • existuje univerzální ČRF pro každou třídu ČRF o k proměnných, která dostane na vstup kód fce (e) a k-proměnných a vydá výsledek e-té funkce (ta univerzální funkce je tvaru minimalizace PRP), viz Kleeneho věta.
  • třída PRF má svoji univerzální funkci, která ale sama do třídy PRF nepatří

důkaz sporem: Nechť U(x, x) je univerzální PRF, která počítá výstup x-té PRF na vstupu x. Pak U(x, x) + 1 je také PRF (použitím operátoru substituce a funkce následníka). Protože U je univerzální funkce, platí, že $ U(x, x) + 1 \simeq U(x_0, x) $ pro nějaké $ x_0 $. Nyní přichází klíčový krok důkazu, kdy za x dosadíme $ x_0 $ (tzn. wcs:Cantorova diagonální metoda) a dostáváme $ U(x_0, x_0) + 1 \simeq U(x_0, x_0) $, což je spor. Předpoklad, že U je primitivně rekurzivní funkce, byl tedy chybný. (TODO - na přednášce používal doc. Kučera operator "mínus s tečkou", definovaný jako x-y pro x>=y, a 0 pro x<y, nazývaný aritmetický rozdíl. Tento operátor zachovává totálnost.)

Def Univerzální funkce pro k proměnných (numerace)
funkce U je univerzální pro spočetnou třídu aritmetických funkcí k proměnných A, pokud
  • Pro každé $ e\; \lambda_{x_1, ..., x_k} U(e, x_1,..., x_k) $ patří do A
  • Pro každé $ f \in A $ existuje e tak, že $ f(x_1, x_2, ..., x_k) \simeq \lambda_{x_1, ..., x_k} U(e, x_1,..., x_k) $

e se nazývá index funkce

Def Gödelovská univerzální funkce

Univerzální funkce je gödelovská, jestliže

  • Je efektivně vyčíslitelná
  • index složené funkce funkce lze efektivně zjistit z indexů skládaných funkcí, tj. pokud existuje efektivně vyčístlitelná $ \alpha $, taková, že

$ U(p, U(q, x))\simeq U(\alpha(p, q), x) \simeq p \circ q (x) $

Vlastnosti univerzální funkce (pro ČRF)[editovat | editovat zdroj]

  • Je taky ČRF
  • Nelze rozšířit na ORF (nemůže být definovaná všude – numeruje i programy, které jsou smyčka)

Formální důkaz toho, že nejde rozšířit na ORF: Předpokládejme, že f je rozšíření na ORF. Položme $ g(x) \simeq 1 - f(x, x) $. Jelikož f je ORF je i g ORF. Funkce g má svoje gödelovo číslo a a tedy $ g(x) \simeq \Psi_1(a,x) $. Specielní případ, pro $ x=a $, kdy $ g(a) \simeq \Psi_1(a,a) $. A to je spor: $ g(a) \simeq 1 - f(a, a) $, a protože f je rozšíření $ \Psi_1 $, platí že $ f(a, a) \simeq \Psi_1(a, a) $ (g je ORF a tím pádem je $ \Psi_1(a, a) $ jistě definováno). No a tedy je $ g(a) \simeq 1 - \Psi_1(a, a) \simeq \Psi_1(a, a) $, což asi pro každé kódování zvládnout nejde.

Predikát o konvergenci univerzální funkce[editovat | editovat zdroj]

  • Predikát $ \Psi_k(e, x_1, x_2, ..., x_k)\uparrow $ není RSP
  • Predikát $ \Psi_k(e, x_1, x_2, ..., x_k)\downarrow $ je RSP, ale není ORP

Důkaz: (je uveden pouze pro dvě proměnné, nikoli pro více) Pro spor přepdokládejme, že je RSP. Pak jeho charakteristická funkce je ČRF (označmě ji $ \alpha $), která je definována právě když $ \Psi_k(e, x_1, x_2,..., x_k)\uparrow $. Tato ČRF má ale gödelovo číslo a, a tedy $ \alpha(x) \simeq \Psi_k(a, x) $. No a teď zas ten specielní případ, $ \alpha(a) \simeq \Psi_k(a, a) $. To je ale spor, protože $ \alpha(x) \simeq \Psi_k(x, x) $ je definováno právě když $ \Psi_k(x, x) $ není definováno ($ \Psi_k(x, x)\uparrow $) (Mimochodem, tohle je ukázka Cantorovy diagonální metody, na diagonále jsou $ \Psi_k(z, z) $)

Kdyby $ \Psi_k(e, x_1, x_2, ..., x_k)\downarrow $ byl ORP, musela by i jeho charakteristická funkce být ORF, tj definovaná pro všechny vstupy, tj musela bz být definovaná i pro úseky, kde $ \Psi_k(e, x_1, x_2, ..., x_k)\uparrow $ a to by byla ČRF, což podle předchozího není.

Rekurzivní a rekurzivně spočetné množiny a jejich vlastnosti[editovat | editovat zdroj]

see wen:Recursive set, wen:Recursively enumerable set

Základní definice[editovat | editovat zdroj]

  • Predikáty ("vlastnost" - např. x < y, nebo x je elementem M)
  • predikát je obecně rekurzivní (ORP), resp. primitivně rekurzivní (PRP), jestliže jeho charakteristická funkce je taková (ORF, resp. PRF)
    • ORP jsou právě ty, které jsou efektivně rozhodnutelné
  • predikát je rekurzivně spočetný (RSP), jestliže jeho obor pravdivosti je definičním oborem nějaké ČRF
    • tam, kde P neplatí, tam program není definován
  • množina M je rekurzivní, jestliže její charakteristická fce je ORF
    • rekurzivní množina je taková, že o každém prvku dokážeme efektivně zjistit, zda do množiny patří či nikoliv
    • Rekurzivní množina je právě efektivně (algoritmicky) rozhodnutelná
  • množina M je rekurzivně spočetná, jestliže je definičním oborem nějaké ČRF
    • rekurzivně spočetné množiny se nějaký program pouze zastaví, když prvek do množiny patří, jinak nic nevíme

Věta o selektoru[editovat | editovat zdroj]

Pro každý RSP $ Q $ k+1 proměnných existuje ČRF $ \varphi $ k proměnných, pro kterou platí

  • $ \varphi(x_1,...,x_k)\downarrow \Leftrightarrow \exists y Q(x_1,...,x_k,y) $
  • $ \varphi(x_1,...,x_k)\downarrow \Rightarrow Q\Big(x_1,...,x_k,\varphi(x_1,...,x_k)\Big) $.

Druhá řádka říká, že pro každý RSP $ Q $ umíme zkonstruovat takovou ČRF $ \varphi $, která lze dosadit za poslední proměnnou $ Q $ (respektive její výsledek y) a pokud $ \varphi $ konverguje, tak $ Q $ platí. První řádka říká, že $ \varphi $ "se snaží seč může", tedy pokud nějaké y existuje, tak ho najde. (Nebýt této podmínky, šlo by za $ \varphi $ zvolit třeba prázdnou funkci.)

Predikát $ Q $ k+1 proměnných si můžeme představit jako relaci či graf (grafem se zde rozumí množina bodů, žádné hrany a vrcholy) v k+1 rozměrném prostoru (přirozených čísel ovšem, jak jinak). Predikát $ Q(x_1,...,x_k,x_{k+1})\! $ určuje, zda bod $ (x_1,...,x_k,x_{k+1}) $ je v grafu, či nikoli. $ \varphi $ můžeme chápat jako funkci na k rozměrném prostoru takovou, že v grafu vybere v poslední proměnné právě jeden bod (pokud existuje). Celý tento odstavec je tu jen proto, aby vysvětlil název věta (či lemma) o selektoru a proč se říká, že ČRF mají RS graf. Klidně na něj zatím zapomeňte.

Důkaz: Pro RSP $ Q $ existuje TS $ T $, který se zastaví v přijímacím stavu, pokud $ Q(x_1,...,x_k,y) $.

Definujme ORF $ \beta(x_1,...,x_k,y,j) = 0 \Leftrightarrow T\mbox{ přijme vstup }x_1,...,x_k,y\mbox{ za }j\mbox{ kroků} $

Požadovaná ČRF je pak:

$ \varphi(x_1,...,x_k) = \mu_{<y,j>}\beta(x_1,...,x_k,y,j) $

Pokud totiž pro $ x_1,...,x_k $ nějaké $ y $, takové že platí $ Q(x_1,...,x_k,y) $ existuje, tak se odpovídající TS zastaví nejvýše po $ j $ krocích, a my to zjistíme v $ <y,j> $-té iteraci minimalizační funkce $ \mu_{<y,j>} $.

1-převeditelnost, m-převeditelnost[editovat | editovat zdroj]

  • Množina $ A $ je 1-převeditelná na $ B $ (značíme $ A \leq_1 B $), jestliže existuje prostá ORF taková, že $ x \in A \Leftrightarrow f(x) \in B $.
    • Množina M je 1-úplná, jestliže je rekurzivně spočetná a každá rekurzivně spočetná množina je na ni 1-převeditelná. (Pozn.: Nemá být nekonečná? Jak může být 1prvková množina převoditelná na dvojprvkovou?)
  • Množina $ A $ je m-převeditelná na $ B $ (značíme $ A \leq_m B $), jestliže existuje (ne nutně prostá) ORF taková, že $ x \in A \Leftrightarrow f(x) \in B $.
    • Množina M je m-úplná, jestliže M je rekurzivně spočetná a každá rekurzivně spočetná množina na ni je m-převeditelná.

1-úplnost K[editovat | editovat zdroj]

Věta: K je 1-úplná.

Důkaz: Chceme ukázat, že pro každou rekursivně spočetnou množinu $ W_x $ je je $ W_x \leq_1 K $, to jest, že exituje prostá ORF h taková, že $ y \in W_x \Leftrightarrow h(x) \in K $. Mějme libovolnou rekurzivně spočetnou množinu $ W_x $ a ČRF $ \alpha(y,x,w) $, která ji popisuje.
Tedy $ \alpha(y,x,w)\downarrow \Leftrightarrow^* y \in W_x \Leftrightarrow \Psi_1(x,y)\downarrow \Leftrightarrow \varphi_x(y)\downarrow $ (na $ w $ hodnota $ \alpha $ nezávisí)
Ze s-m-n dostáváme $ \alpha(y,x,w) \simeq \Psi_3(a,y,x,w) \simeq \Psi_1(s_2(a,y,x),w) \simeq \varphi_{s_2(a,y,x)}(w) $ (**)
Označíme-li $ h(y,x) = s_2(a,y,x) $ ($ s_2 $ je PRF a tedy i ORF), máme $ y \in W_x \Leftrightarrow^* \alpha(y,x,w)\downarrow\Leftrightarrow^{**} \varphi_{h(y,x)}(w)\downarrow \Leftrightarrow^{***} \varphi_{h(y,x)}(h(y,x))\downarrow \Leftrightarrow h(y,x) \in K $
  • *** -- můžeme předpokládat $ h(y,x) = w $, hodnota $ \alpha $ a tudíž ani $ h $ na $ w $ nezáleží.
Tedy $ W_x \leq_1 K $ pomocí funkce $ \lambda y.h(y,x) $.

Také platí

  • $ K_0 = \{ \langle y,x \rangle : y \in W_x \} $ je 1-úplná.
  • $ K \leq_1 K_0 $ a $ K $ je 1-úplná.
Poznámka: To vlastně říká, že halting problém je vzhledem k 1- převeditelnosti nejtěžší problém mezi rekursivně spočetnými problémy($ K_0 = \{ \langle y,x \rangle : y \in W_x \} $ je definice halting problému)

Další vztahy[editovat | editovat zdroj]

  1. Relace $ \leq_1 $ a $ \leq_m $ jsou tranzitivní a reflexivní.
  2. $ A \leq_1 B \Rightarrow A \leq_m B $
  3. $ B \mbox{ rekurzivní}, A \leq_m B \Rightarrow A \mbox{ rekurzivní} $
    • Složením funkce dokazující $ \leq_m $ s procedurou, která rozhoduje o $ x \in B $ dostaneme proceduru rozhodující o $ A $. ($ c_A(x) = c_B(f(x)) $
  4. $ B \mbox{ rekurzivně spočetná}, A \leq_m B \Rightarrow A \mbox{ rekurzivně spočetná} $
    Důsledek: $ K $ a $ \overline K $ jsou m-nesrovnatelné.

Rekurzivní permutace[editovat | editovat zdroj]

  • Rekurzivní permutace je permutace na $ \mathbb{N} $, která je ORF.
  • Množiny $ A $ a $ B $ jsou rekurzivně izomorfní, jestliže existuje rekurzivní permutace p taková, že $ p(A) = B $. Značíme $ A \equiv B $.
  • $ A \equiv_1 B $, jestliže $ A \leq_1 B \And B \leq_1 A $
  • $ A \equiv_m B $, jestliže $ A \leq_m B \And B \leq_m A $

Myhillova věta[editovat | editovat zdroj]

$ A \equiv B \Leftrightarrow A \equiv_1 B $

Důkaz: Plán: v krocích budeme generovat graf $ h $ tak, že v kroce $ n $ bude platit

$ \{0,\ldots,n\} \subseteq dom(h), \qquad \{0,\ldots,n\} \subseteq rng(h) $.

Z toho plyne, že $ h $ bude definovaná na celém $ \mathbb{N} $ a bude na. Současně zajistíme, že $ h $ bude prostá.

Navíc budeme chtít, aby platilo $ y \in A \Leftrightarrow h(y) \in B $, tedy aby $ h $ převáděla $ A $ na $ B $.

Indukce: Začneme v bodě 0 a položíme $ h(0)=f(0) $. Rozlišíme následující případy:

  • $ f(0)=0 $: vše je v pořádku, $ h(0)=f(0)=0 $ a $ 0 \in A \Leftrightarrow 0 \in B $, pokračujeme dalším prvkem.
  • $ f(0) \neq 0 $: rozlišíme dva podpřípady
    • $ g(0)\neq 0 $: vše v pořádku, definujeme $ h(g(0))=0 $. Tedy $ 0 \in dom(h) \cap rng(h) $.
    • $ g(0)=0 $: nemůžeme použít $ h(g(0))=0 $, protože v bodě 0 je již $ h $ definována jako $ f(0) $. Najdeme tedy volný bod. Definujme $ h(g(f(0)))=0 $. Určitě $ g(f(0))\neq 0 $, protože $ g $ je prostá a $ f(0)\neq 0 $.

Tímto jsme opět dostali bod 0 do definičního oboru $ h $ i oboru hodnot. Zároveň funkci $ h $ definujeme podle $ f $ a $ g $, tedy převádí vzájemně $ A $ na $ B $.

Indukční krok: nechť v kroce $ k $ je $ z $ první volný prvek. Všechna čísla menší jak $ z $ máme v $ dom(h)\cap rng(h) $. Podíváme se, zda je $ f(z) $ volný. Jestliže ano, položíme $ h(z)=f(z) $. Jestliže $ f(z) $ není volný, hledám zig-zag další volný. Maximálně $ z $ prvků je blokovaných.


Důsledek: $ K \equiv K_0 $, neboť $ K \equiv_1 K_0 $

Rekurzivně spočetné predikáty[editovat | editovat zdroj]

  • Je-li $ Q $ ORP, pak $ \exists y Q $ je rekurzivně spočetný predikát (RSP).
    $ \mu_y Q $ je ČRF, její definiční obor je $ \exists y Q $.
  • Predikát $ \exists y T_k(e,x_1,... ,x_k,y) $ je univerzální RSP pro třídu RSP $ k $ proměnných.
    $ T_k $ je predikát z Kleeneho věty o normální formě, co říká že funkce $ e $ má při $ y_0 $ krocích od konce mezivýsledek $ y_1 $. ($ y=\langle y_0, y_1 \rangle $). Důkaz tvrzení plyne z Kleeneho věty.
  • Doplněk nezachovává rekursivní spočenost (důkaz už byl)
  • Konjunkce a disjunkce zachovávají rekurzivní spočetnost. (Průnik a sjednocení rekurzivně spočetných množin je rekurzivně spočetná množina. Stejně pro predikáty.)
    Pro sjednocení spustíme oba programy současně a čekáme až se jeden zastaví. Pro průnik čekáme, až se zastaví oba.
    Důkaz pro průnik: $ x \in A, x \in B $ jsou RSP. Pomocí Kleeneho T Predikátu jde každý predikát zapsat v univerzálním tvaru $ \exists z, T_k(a, x_1, .., x_k, z) $, kde a je gödelovo číslo predikátu. Tak zapíšeme$ x \in A, x \in B $ pomocí obecného T predikátu: $ \exists z_1, T_k(a, x, z_1) \and \exists z_2, T_k(b, x, z_2) $. Nyní $ z_1, z_2 $ zakódujeme do dvojice: $ \exists w, T_k(a, x, l(w)) \and T_k(b, x, r(w)) $. Jelikož T predikár je PRP, můžeme to přepsat jako $ \exists z, T_{k+2}(e, a, b, x, z) $. A teď se použije s-m-n věta. $ \exists z, T_k(s(e, a, b), x, z) $. Obdobně pro sjednocení.
  • Omezená kvantifikace $ (\forall y)_{y \leq t} $ a existenční kvantifikace (pro $ k \geq 2 $) zachovávají rekurzivní spočetnost.
    Neformálně: omezený kvantifikátor lze zkontrolovat for cyklem, existenční kvantifikátor je rozveden ve Strojilovi na straně 6.

Postova věta a ostatní věty o RSM[editovat | editovat zdroj]

Věta (Postova): Množina $ M $ je rekurzivní právě když $ M $ i $ \overline M $ jsou rekurzivně spočetné. Predikát $ Q $ je ORP právě když $ Q $ i $ \neg Q $ jsou RSP.

Důkaz: Zleva doprava triviální – přímo z definice. Zprava doleva intuitivně: $ M = dom(P_1), \overline M = dom(P_2) $. Pustíme oba programy současně a čekáme, který se zastaví. Formálně pomocí věty o selektoru: $ Q(x, y) = (x \in M \and y=1) \or (x \notin M \and y=0) $. Selektor je ČRF, která vždy konverguje (vždy existuje y, je buď jedna, nebo nula). A máme charakteristickou funkci.

Věta:Každá rekurzivně spočetná množina je oborem hodnot nějaké ČRF.

Důkaz: Máme dánu x-tou RSM. Vytvoříme množinu dvojic $ R = \{ \langle z,y \rangle : z \in W_x \And y = z \} $ (Predikát $ Q(z, y) = z \in W_x \And y = z $). Množina R je rekurzivně spočetná, tedy má ČRF selektor $ \varphi $, platí $ dom(\varphi) = rng(\varphi) = W_x $. Myšlenka důkazu je, že body, kde $ \varphi_x $ konverguje, vyneseme na diagonálu a vytvoříme selektor. Jeho definiční obor bude současně oborem hodnot.

Věta:Každý obor hodnot ČRF je rekurzivně spočetná množina.

Důkaz: Myšlenka: zkonstruujeme pseudoinverzní funkci k ČRF $ \varphi $. Dána $ M = rng(\varphi_x) $, kde $ \varphi_x $ je ČRF. Definujme predikát $ Q(z, y) = \varphi_x(y) \simeq z $. Pak Q je RSP a jeho selektor je ČRF jejíž je M doménou.

Věta: Množina je rekursivní <=> je oborem hodnot nějaké rostoucí úsekové ČRF. (úseková funkce je taková, jejímž def. oborem je počáční úsek $ \mathbb{N} $)

Důkaz:
"=>": U ČRF jsme použili selektor, jehož doménou byla doména charakteristické funkce množiny. Pokud víme, že je tato množina rekursivní, můžeme prvky seřadit do posloupnosti (až do vyčerpání množiny bude tato posloupnost všude definovaná). A dál použijeme minimalizaci: $ \varphi(0) \simeq \mu_y(y \in M), \varphi(n+1) \simeq \mu_y(y>\varphi(n) \and y \in M) $. Pak $ M = rng(\varphi) $.
"<=": Nechť $ \varphi $ je rostouci useková ČRF, $ M = rng(\varphi) $. Patří-li y do M, pak $ \exists x $ takové, že $ \varphi(x) = y $, protože y je z oboru hodnot $ \varphi $. Navíc víme, že $ x \leq y $, to proto, že x, y jsou $ \in \mathbb{N} $ a funkce je rostoucí, a v $ \mathbb{N} $ "stoupání musí být větší, než diagonála". Při dotazu, jestli $ y \in M $ stačí projít všechny $ x \leq y $, pak víme, že mezi těmi většimi ho už nenajdeme a tak máme definovanou ORF charakteristickou funkci.

Věta: Množina je r.s. <=> je oborem hodnot prosté úsekové ČRF.

Důkaz:
"<=" Obor jakékoli ČRF je r.s. množina z definice.
"=>" Z předchozí věty víme, že RM jsou generovány rostoucími úsekovými funkcemi. Vezměme množinu $ B= \{<x,s>: \varphi(x)\downarrow za\;presne\;s\;kroku\} $, $ \varphi(x) $ je ČRF pro kterou $ dom(\varphi) = M $. Množina B je rekurzivní, pro každou dvojici lze rozhodnout, jestli $ \varphi(x) $ zkonverguje po s krocích. Funkce generující B je přitom rostoucí (z předchozí věty, B je rekursivní) a ze l(f) je v M. Formálně můžeme definovat $ g(x) = (f(x))_{2,1} $, pak g je ČRF, $ rng(g) = M $ a g je prostá (růst záležel na kódování dvojice <x,s>, f však nemůže vygenerovat x dvakrát, bylo řečeno přesně s kroků)

Důsledek: Množina M je nekonečná, pak M je rekurzivní <=> lze generovat rostoucí ORF.

Důsledek: Množina M je nekonečná, pak M je r.s. <=> lze generovat prostou ORF.

Věta: Každá nekonečná r.s. množina obsahuje nekonečnou rekurzivní podmnožinu.

Důkaz:
$ f $ je prostá ORF, $ range(f) = M $, vyber rostoucí podposloupnost $ h(0) \simeq 0 $, $ h(n+1) \simeq f(\mu_y(f(y) > h(n))) $, $ h $ je ORF, roste, $ range(h)=A \subseteq M $

Produktivní a kreativní množiny[editovat | editovat zdroj]

  • Definice: Množina A je produktivní, pokud existuje ČRF φ tž. $ W_x\subseteq A\implies\varphi(x)\downarrow \and \varphi(x)\in A\setminus W_x $
  • Definice: Množina B je kreativní, pokud je r.s. a $ \bar{B} $ je produktivní.
  • Příklady
    • K je kreativní - je RS a $ \bar{K} $ je produktivní, za φ se zvolí identita
  • Vlastnosti
    • Ke každé produktivní množině A existuje produktivní ORF f, f=φ(g(x)) - g(x) spočítá index 'podobného' programu, který je navíc totální pro jazyky mimo A
    • Ke každé produktivní množině A existuje produktivní ORF bijekce φ (dá se sestrojit s pomocí původní produktivní ORF)
    • Každá produktivní množina A obsahuje nekonečnou RSM - prázdná množina patří do A a φ nám vrátí vždy nový prvek z A, který se dá přidat k výchozí podmnožině A, atd.
  • Ekvivalence
    • A je produktivní, $ \bar{K} $ je 1-převeditelná na A, $ \bar{K} $ je m-převeditelná na A
    • B je kreativní, B je 1-úplná, B je m-úplná

Imunní a prosté množiny[editovat | editovat zdroj]

  • Definice: Množina B je imunní, pokud je nekonečná a neobsahuje nekonečou r.s. množinu.
  • Definice: Množina B je prostá, pokud je r.s. a její doplněk je imunní množina.

Věta: Existuje prostá množina

Algoritmicky nerozhodnutelné problémy[editovat | editovat zdroj]

Definice[editovat | editovat zdroj]

see wen:List of undecidable problems

Uvažujme rozhodovací problémy - odpověď je buď ANO nebo NE. Instance tohoto problému nechť jsou kódována v abecedě $ \Sigma = \{0, 1\} $ Definujme jazyk kladných a záporných instancí problému. O jazyku řekneme, že rekursivní, pokud ho řeší nějaký (deterministický) turingův stroj. Slovem řešit problém budeme popisovat situaci, kdy se stroj pro všechny kladné instance zastaví v koncovém stavu, kde přijímá a pro všechny ostatní instance problému se zastaví ve stavu, kde odmítá.

Definice: Problém je algoritmicky rozhodnutelný, pokud je jazyk jeho kladných instancí rekursivní. Jazyk, který není algoritmicky rozhodnutelný je algoritmicky nerozhodnutelný.


Halting problém[editovat | editovat zdroj]

  • Halting problém, z Johančiných pohádek
Připomenu definici: neexistuje algoritmus, který by pro daný turináč a daný vstup dokázal rozhodnout, zda se turingáč na tomto vstupu zastaví. Pro důkaz použijeme pár myšlenek, které je dobré si zapamatovat, protože se s nimi nevidíme naposled. První z nich je (překvapivě) myšlenka UTS, druhou je otázka zastavení algoritmu na jeho vlastním kódu a třetí myšlenkou je přiřadit výsledky něčeho úmyslně opačně - nelogicky: když se něco povede, 0, když nepovede, 1. Z tohohle všeho dohromady kouká nějaký slibný spor, tak teď si to konečně aplikujeme na náš konkrétní úkol.
Důkaz (pomocí UTS): provedeme sporem, předpokládáme, že existuje algoritmus H(M,K), co mu předhodíme turingáč M a vstup K a on řekne, jestli tenhle vztah má budoucnost :). Tedy vždy se zastaví a řekne 0 (nemá), nebo 1 (má). Pomocí něj sestrojíme kapku brutálnější algoritmus Alg(K), který se nad daným kódem programu zastaví právě tehdy, když se tento program sám se na svém vlastním kódu nezastaví. Tedy Alg(K) zastaví <=> U(K,K) nezastaví. Prostě algoritmus Alg říká: mně se líbí program, co nesežere svůj vlastní vstup, a tak se na něm zastavím, naopak program, co svůj vlastní vstup sežere, se mi nelíbí, takže se na něm třeba zacyklím a prostě trucuju :). Alg(K) definujeme podle výsledku výše zmíněného algoritmu H (který se vždy zastaví a něco řekne, takže my ho provedem a podle toho, co řekl, se rozhodnem): H(U(K,K),K) = 0 => Alg(K) zastaví, H(U(K,K),K) = 1 => Alg(K) zacyklí. Celá tahle prasárna jde provést právě proto, co jsme si na začátku definovali, tedy že algoritmus H existuje a vždy se zastaví. No a teď už asi nikoho nepřekvapí, že po tak ďábelské definici algoritmu Alg snadno vykouzlíme spor - pustíme ho na jeho vlastním kódu. Potom Alg(Alg) zastaví <=> U(Alg,Alg) nezastaví <=> Alg(Alg) nezastaví. Tohle ukazuje, že původní algoritmus H (který rozhoduje o zastavení) je zvrácený a nemůže existovat :).
Důkaz (pomocí ČRF): Z kleeneho věty víme, že existuje efektivní očíslování pro třídu ČRF a její univerzální funkce. vezměme množinu $ K = \{x: \varphi_x(x)\downarrow\} = \{x: \Psi(x, x)\downarrow\} $. Ta není rekursivní (pokud by byla, tak bychom mohli dodefinovat funkci $ \alpha $ takovou, že $ \alpha \downarrow \Leftrightarrow \varphi_x(x) \uparrow $. Ta by byla r.s. a měla gödelovo číslo e, takže $ \varphi_e(e) \simeq \alpha(e) $ takže $ \alpha(e) \downarrow \Leftrightarrow \varphi_e(e) \uparrow \Leftrightarrow \alpha(e) \uparrow $). No a tím spíš není rekursivní $ K_0 = \{<x, y>: \varphi_x(y)\downarrow \} $, protože $ K \leq_1 K_0 $.

Ostatní problémy[editovat | editovat zdroj]

  • Je jazyk přijímaný daným TS prázný/neprázný/konečný?
  • Riceova věta
  • Postův korespondeční problém PKP (i s omezením na iniciální řešení IPKP).
Postův systém je tvořen neprázdným seznamem S dvojic neprázdných řetězců:
$ S = \{ (\alpha_1,\beta_1),\,...,\,(\alpha_k,\beta_k) \} $, kde $ k \geq 1 $ a $ \alpha_i, \beta_i $ jsou řetězce nad nějakou abecedou.
Řešením Postova systému je každá neprázdná posloupnost přirozených čísel I:
$ I = \{ i_1,\,...,\,i_m \} $, kde $ 1 \leq i_j \leq k $ a $ m \geq 1 $, pro kterou platí $ \alpha_{i_1}...\alpha_{i_m} = \beta_{i_1}...\beta_{i_m} $.
Postův korespondenční problém zní: Existuje pro daný Postův systém řešení?
Příklad: Systém $ S_1 = \{ (b,bbb),\,(babbb,ba),\,(ba, a) \} $ má řešení $ I = \{ 2,\,1,\,1,\,3 \} $: babbb b b ba = ba bbb bbb a.
Systém $ S_2 = \{ (ab,abb),\,(a,ba),\,(b,bb) \} $ řešení nemá.
Lze ukázaat IPKP <=> TS zastaví nad slovem u.
  • Pro bezkontextové gramatiky G1,G2 je algoritmicky nerozhodnutelné zda L(G1)∩L(G2)={}.
Důkaz: převedeme PKP na daný problém máme PKP [u1,v1],..., [un,vn]
zvolíme nové terminály a1,…,an pro kódy indexů
G1: S→ uiSai | uiai generuje slova ui1... uikaik... ai1
G2: S→ viSai | viai generuje slova vi1... vikaik... ai1
PKP má řešení právě když L(G1) ∩L(G2)≠{}
u-část = v-část + složky ai< zajišťují stejné pořadí
  • Je algoritmicky nerozhodnutelné, zda je bezkontextová gramatika víceznačná.
Důkaz:
S → S1 | S2
S1 → uiS1ai | uiai
S2 → viS2ai | viai
PKP má řešení právě když je gramatika víceznačná

Věty o rekurzi a jejich aplikace, Riceova věta[editovat | editovat zdroj]

Matfyz Wiki: Věty o rekurzi

TODO, chybělo jako podotázka

Gödelovy věty[editovat | editovat zdroj]

rekurzivní neoddělitelnost
Dvojice množin A, B ($ A \cap B = \emptyset $) je rekurzivně neoddělitelná, jestliže neexistuje rekurzivní množina M taková, že $ A \subseteq M, M \cap B = \emptyset $ (tj. $ B \subseteq \overline{M} $)
efektivní neoddělitelnost
Dvojice množin A, B ($ A \cap B = \emptyset $) je efektivně neoddělitelná, jestliže existuje ČRF $ \varphi $ taková, že
$ \begin{matrix} A \subseteq W_x \\ B \subseteq W_y \\ W_x \cap W_y = \emptyset \end{matrix} \Bigg \} \Rightarrow \varphi(x,y)\downarrow \and \varphi(x,y)\notin W_x \cup W_y $
Tj. z indexů aproximace A a B se dá efektivně najít další bod, který leží mimo tu aproximaci.
Gödelova věta o neúplnosti (1. část)
V rozumných teoriích je množina dokazatelných a vyvratitelných formulí efektivně neoddělitelná dvojice.

Gödelova věta o neúplnosti[editovat | editovat zdroj]

Základní aritmerická síla: Jazyk prvního řádu

  • numerály pro nulu a jedničku
  • funkční symboly + a ×
  • konečně mnoho axiomů

Teorie T je axiomatizovatelná, jestliže množina dokazatelných formulí v T je rekurzivně spočetná.

Věta: Jestliže teorie T 1. řádu má základní aritmetickou sílu a je bezesporná, pak

  1. množina formulí dokazatelných v T není rekurzivní
    Vezmu r.s. efektivně neoddělitelné A,B tž. $ x\in A\implies\vdash_T G(\bar{x}) $ a $ x\in B\implies\vdash_T \neg G(\bar{x}) $.
    Vezmeme $ A_1=\{x;\vdash_T G(\bar{x})\} $, $ B_1=\{x;\vdash_T \neg G(\bar{x})\} $ ($ A\subseteq A_1 $, $ B\subseteq B_1 $). Z bezespornosti A1 a B1 disjunktní a nejsou rekurzivní (separovaly by).
  2. je-li T navíc axiomatizovatelná, pak
    • existuje uzavřená formule v F taková, že F je nerozhodnutelná v T (tj. z T nevyplývá ani F, ani $ \neg F $)
    Množiny A1 a B1 z bodu (1) jsou nyní r.s. a umím tedy efektivně určit bod mimo ně (číslo fle nedokazatelne ani nevyvratitelné v T).
    • v T nelze dokázat vlastní bezespornost (za o něco silnějších předpokladů o teorii T -- např. $ \Sigma_1-\mbox{indukce} $)

Materiály[editovat | editovat zdroj]

  • Text P. Kučery – Podle mě super srozumitelný materiál, který pokrývá vše kromě Gödela!
  • Pohádky z vyčíslitelnosti – velmi neformální úvod do problematiky
  • Wiki skripta z vyčíslitelnosti – neúplná, ale podrobná
  • Vyčíslitelnost I – stránka předmětu na wiki, obsahuje odkazy na další materiály
  • Pavliska V., Vyčíslitelnost a Složitost 1 a 2, Ostravská Univerzita, [2] a [3]
  • Demuth O., R. Kryl R., Kučera A., Teorie algoritmů I a II, skripta MFF-UK
  • Češka M., Vojnar T., Smrčka A., Teoretická informatika, VUT Brno [4]