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 N* a S c N definujeme obraz množiny A při zobrazení f jako množinu
f (A) = {f (a) | a g dom(f) n ^1}
a i/zor množiny B při zobrazení f jako množinu
r1 (6) = {a a g dom(0 a /(a) e S}.
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 je rekurzivní množina af\Nk^Nje totáně vyčíslitelná funkce. Pak ŕ~1 (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 3/15
uzáverové vlastnosti r.e. množin
W, = dom(ipi)
Pro každé k,l>\ existuje totálně vyčíslitelná funkce h :N2 -^N taková, že pro libovolné r.e. množiny Wf c Nk a
HA(/) c N' platí
W{k) x W{l) = w£+J}
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
4/15
uzáverové vlastnosti r.e. množin ^^^^^^^^^^^^^^^^
Existují totálně vyčíslitelné funkce hA, h2 : N2 N řa/cové, že pro /caždé r.e. množiny 1/1/,, l/l/y p/aří:
D   W/U W/= ^ (/,;)
□ W,. n Wj = Wmj) Důkaz:
n WiUWj = whÁU)
w,nWj = wmj)
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
Věta
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)= wfUjy Důkaz: ^/(l/l/y) = {^/(a) | a e domfai) n Wj}
Vime, že existuje tot. vyčíslitelná funkce t: N    N taková, že
range{<pk) = dom(<pm).
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 g : N2 N taková, že pro každou vyčíslitelnou funkci p\ a každou r.e. množinu Wj platí
Důkaz: cp- 1 (Wj) = {a | a e domfoj) a ^,(a) g Wj}
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/_-i, a/+1,..., ak) | 3a, e N fa/c, že (ai,...,	a/c) e R}
se nazývá i-tá projekce relace R. Množina	
{(a-i,..., a,_i,     ,..., a/c) (a-i,..., a,-_i, £>, a,-+i,...	, 5/c) 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
O Libovolný řez rekurzivní množiny je rekurzivní množina.
B Libovolný řez re. množiny je re. množina.
B Libovolná projekce re. množiny je re. 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
uzavřenost na projekce a řezy
Tvrzení
D Projekce rekurzivní množiny nemusí být rekurzivní. q 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
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^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 11/15
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í f
■ řez
■ není uzavřená na:
■ projekce
■ obecně není uzavřená na:
■ obraz při totálně vyčíslitelném zobrazení f
■ 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áverové 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-i,...,//) 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 r.e., 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