IB107 Vyčíslitelnost a složitost
uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*
Jan Strejček
Fakulta informatiky Masarykova univerzita
vlastnosti rekurzivních množin
Tvrzení
Každá nekonečná rekurzivní množina má jak nerekurzivní re. podmnožinu, tak i podmnožinu, kteří není re.
Důkaz:
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 2/16
uzáverové vlastnosti rekurzivních množin
Třída rekurzivních množin je uzavřená na u, n a doplněk.
Věta 8.2
D Nechí B c N y e rekurzivní množina af\Nk^Nje totáně vyčíslitelná funkce. Pak f~\B) je rekurzivní množina.
B Necht A c Nk a B c n' jsou rekurzivní množiny. Pak A x B c N/c+/ je rekurzivní množina.
Důkaz:
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*
uzáverové vlastnosti r.e. množin
W>J> = dom(tp)J>)
Pro každé k, I > 1 existuje totálně vyčíslitelná funkce h : n2 ->• n taková, že pro libovolné r.e. množiny W>k' c^a W}1' c n' platí
W{k) x W{l) = W{hk+']
Důkaz:
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*
uzáverové vlastnosti r.e. množin ^^^^^^^^^^^^^^^^
Existují totálně vyčíslitelné funkce hA, h2 : n2 -> n řatoué, že pra /caidé r.e. množiny W,, Wj platí:
D Wi U Wy = Wh (/,;) Q IV/ H Wy = W^/j)
Důkaz:
D Wi U Wy = Wftl (;,y)
Wi n n/y = whÁU)
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*
uzáverové vlastnosti rekurzivních a r.e. množin
Důsledek
Pro A, B c n^, jejichž symetrický rozdíl A + B je konečný, platí:
■ A je rekurzivní, právě když B je rekurzivní
■ A je re., právě když B je re.
Důkaz:
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 6/16
uzáverové vlastnosti r.e. množin
Věta 8.3
Existuje totálně vyčíslitelné funkce f: n2 -> n taková, že pro každou vyčíslitelnou funkci cpj a každou r.e. množinu Wj platí
Důkaz: cpj(Wj) = {^/(a) | a e domfaj) n l/l//}
Vime, že existuje tot. vyčíslitelná funkce t: n    n taková, že range{<pk) = dom(<pt{k)). M
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 7/16
uzáverové vlastnosti r.e. množin
Věta 8.3
Existuje totálně vyčíslitelné funkce g : N2 N taková, že pro každou vyčíslitelnou funkci^a každou r.e. množinu Wj platí
-i
Důkaz: cp- 1 (Wf) = {a | a g domfoi) a ^,(a) g l/l/y}
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*
projekce a řez relace
Definice 8.5 (projekce a řez)	
Necht R c Nk je k-ární relace pro k > 2. Množina	
{fa,..., a/_!, a/+1,..., ak) | 3a,- g N tak, že fa,..	., ak) g fí}
se nazývá i-tá projekce relace R. Množina	
{fa,..., a,_i,     ,..., a/c) fa,..., a,_i, £>, a,-+i,.	• •, a/c) g R}
se nazývá i-tý řez relace R pro pevně zvolené b e N.	
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 9/16
uzavřenost na projekce a řezy
Věta 8.7
D Libovolný řez rekurzivní množiny je rekurzivní množina.
B Libovolný řez r.e. množiny je r.e. množina.
Q Libovolná projekce r.e. množiny je r.e. množina.
Důkaz:
Předchozí tvrzení lze formulovat efektivně.
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 10/16
uzavřenost na projekce a řezy
Tvrzení
D Projekce rekurzivní množiny nemusí být rekurzivní. H Libovolná projekce rekurzivní množiny je r.e. množina.
Důkaz:
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*       11/16
věta o projekci
Věta 8.6 (věta o projekci, věta o existenčním kvantifikátoru)
Necht A c je r.e. množina. Pak existuje rekurzivní množina B c N/c+1 taková, že A je (k + 1)-níprojekcí množiny B.
Důkaz:
■ pro jednoduchost předpokládejme k = 1
■ pro vhodné / g N platí A= W, = domini)
Důsledek 8.8
Množina je r.e., právě když je projekcí rekurzivní relace.
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém*
aplikace
Příklad: Dokažte, že množina A = {e | 7 e range(cpe)} je r.e.
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 13/16
shrnutí uzáverových vlastností
třída rekurzivních množin
■ je uzavřená na:
■ u, n aplikované na relace stejné arity
■ doplněk, x, vzor při totálně vyčíslitelném zobrazení /
■ řez
■ není uzavřená na:
■ projekce
■ obecně není uzavřená na:
■ obraz při totálně vyčíslitelném zobrazení /
■ vzor při vyčíslitelném zobrazení g
třída r.e. množin
■ je uzavřená na:
■ u, n aplikované na relace stejné arity
■ x, obraz i vzor při vyčíslitelném zobrazení f
■ projekce, řez
■ není uzavřená na:
■ doplněk
IB107 Vyčíslitelnost a složitost: uzávěrové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 14/16
10. Hilbertův problém
10. Hilbertův problém (1900)
Nalezněte algoritmus, který rozhodne, zda polynomická rovnice s celočíselnými koeficienty má celočíselné řešení.
David Hilbert Diofantos Jurij Vladimirovič
z Alexandrie Matijasevič
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 15/16
10. Hilbertův problém
Definice 8.12 (diofantická relace)
Relace R cNk se nazývá diofantická, právě když existuje polynom P(x-|,..., xk, y^,...,//) s celočíselnými koeficienty a k + I proměnnými splňující:
(ai,..., Sk) g R <^>
3(Ď1,..., b i) g N' takové, že P(ai,..., a/c, Ďi,..., b i) = 0
Věta (Matijasevič, 1970)
Relace je re., právě když je diofantická.
IB107 Vyčíslitelnost a složitost: uzáverové vlastnosti rekurzivních a r.e. množin, věta o projekci, 10. Hilbertův problém* 16/16