IB107 Vyčíslitelnost a složitost
standardní numerace r.e. množin
Jan Strejček
Fakulta informatiky Masarykova univerzita
alternativní charakterizace r.e. množin
Věta
Množina Ac.Nje rekurzivně spočetná, právě když A = dom(g) pro nějakou vyčíslitelnou funkci g : N -> N.
Množina AQNje rekurzivně spočetná, právě když
A = range(g) pro nějakou vyčíslitelnou funkci g : N —^ N.
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
2/9
alternativní charakterizace r.e. množin
Důkaz:
A je r.e. <=^> 3 vyčíslitelná funkce g tak, že A = dom(g)
A = Q
A 7^ 0 je r.e., pak A = range(f) pro tot. vyčíslitelnou funkci f
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
3/9
alternativní charakterizace r.e. množin
A je r.e. <=^> 3 vyčíslitelná funkce g tak, že A = dom(g)
<==    ■ >4 = dom(g) = 0
■ >4 = dom(g) ^ 0, pak nechí a0 e A
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
4/9
alternativní charakterizace r.e. množin
A je r.e.        3 vyčíslitelná funkce g tak, že A = range(g)
■ A = $
■ A ^ 0 je r.e., pak A = range(f) pro tot. vyčíslitelnou funkci f
■ položíme g = f
■ A = range(g) = 0
■ A = range(g) ^ 0, pak nechí a0 e A
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
5/9
možné numerace r.e. množin
dom(ipo), dom(ipi), dom(ip2),... range{(f0), range(^), range{^2), ■ ■ ■
Věta
Existují totálně vyčíslitelné funkce f, g : N N takové, že pro všechna i e N platí vztahy:
□ dom((pi) = range{(pf(j))
□ range{(fi) = cfom(^g(/))
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
6/9
možne numerace r.e. množín
Důkaz:
D dom(ifi) = range{ipf{i))
rangem,) = dom((pg{i))
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
standardní numerace r.e. množin
Definice (standardní numerace r.e. množin)
Standardní n u merací r.e. množin nazveme funkci W : N -> {A c N I A je r.e.} definovanou vztahem
W(i) = dom(ipi).
Index r.e. množiny A c N je číslo i splňující A = W(i)
■ místo 1/1/(0), 1/1/(1),... píšeme W0lWi,...
■ množinu W, lze chápat jako akceptovanou programem P, program P, akceptuje hgN, jestliže P, zastaví pro vstup
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
r.e. relace a standardní numerace r.e. relací
Definice (rekurzivně spočetná relace)
Relace A c Ny je rekurzivně spočetná (r.e.), právě když existuje vyčíslitelná funkce f: Ny    N taková, že A = dom(f).
Definice (standardní numerace r.e. relací)
Standardní numeraci j-árnich r.e. relací nazveme funkci l/l/(y) ■ pj _^ {/\ c n7ř | A je r.e.} definovanou vztahem
|/|/0')(/) = dom((p]i]).
Index r.e. relace A c     je číslo i splňující A = W^(i).
Místo l/l/W (0), |/|/0')(1),... píšeme       w\j\ ....
IB107 Vyčíslitelnost a složitost: standardní numerace r.e. množin
9/9