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
obraz a vzor množiny
Definice (obraz a vzor množiny)
Pro f: Nk N a množiny A c a 6 c N definujeme obraz množiny A při zobrazení f jako množinu
f (A) = {ŕ(a) | ae ctom(0nd}
a vzor množiny B při zobrazení f jako množinu
r1 (B) = {a | a g ctom(0 a ŕ(a) g 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
2/15
uzáverové vlastnosti rekurzivních množin
Třída rekurzivních množin je uzavřená na u, n a doplněk.
Věta
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 r.e. množin
Existuje totálně vyčíslitelné funkce f: N2 N taková, že pro každou vyčíslitelnou funkci (pj a každou r.e. množinu Wj platí
<Pi(Wj)= Wf{iJy
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 6/15
uzáverové vlastnosti r.e. množin
Existuje totálně vyčíslitelné funkce g : N2 N taková, že pro každou vyčíslitelnou funkci (pj a každou r.e. množinu Wj platí
Důkaz: cp- 1 (Wf) = {a | a e domfoi) a ^,(a) e 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
7/15
projekce a řez relace
Definice (projekce a řez)	
Necht R c Nk je k-ární relace pro k > 2. Množina	
{(ai,..., a/_!, a/+1,..., ak) | 3a,- g N řa/c, že (ai,..	., ak) g fí}
se nazývá i-tá projekce relace R. Množina	
{(a-i,..., a,-_i, a/_|_i,..., ak) (a-i,..., a,-_i, £>, a/+-|,.	.., ak) g fí}
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
8/15
uzavřenost na projekce a řezy
Věta
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 9/15
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 10/15
věta o projekci
Věta (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
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 12/15
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 13/15
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 14/15
10. Hilbertův problém
Definice (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 15/15