5.6 Pomocí Riceovy věty dokažte, že následující množiny nejsou rekurzívně spočetné.
(a)	A2 =	{i	(pij^ /}, kde / je pevná totálně vyčíslitelná funkce
(b)	A3 =	[i	<Pi = g}, kde g je pevná vyčíslitelná funkce
(c)	A~z =	{i	(pi ^ g}, kde g je pevná vyčíslitelná funkce
(d)	A4 =	{i	a G dom(<^)}, kde a G N je pevné
(e)	A5 =	{i	dom(v?i) = 0}
(f)	M =	{i	dom(^i) je konečná množina }
Cg)	— -	{i	a $ range(í^i)}7 kde a G N je pevné
(h)	A8 =	{i	range((/?j) je konečná množina}
(i)	A9 =	[i	dom(c^) Ý N}
0)	Am =	{i	\(pi]e prostá}
(k)	Au =	{i	| tfi není bijekce}
8-2: ^o^]
y/ A
£ sc.
j2
•f
r
J
A
-ti.
e * e1
t, &
^     6ä A. , ô^A.
ó .0
4í; t.
"L ,o ^
—5
l/S ft y   L^. lJlUÚ   ^ Kll^
7    ,   • ?
Je
Věta (1. Riceova věta)
t
Neprázdná vlastní podmnožina N (tedy A splňující $ ± A c NJ, Werá respektuje funkce, není rekurzivní.
■ /        u ^
o-^ -L *r ^ u.tc uvar (ja*.
-0
Oft u.
,4
'■ (
-L \vj   - í".
0.V ly
^ L ta y £*L
u
4
\ ^0       *\ l
(lu    \Jty ---■ ^
7) ° ^
5.5 Uvažujme následující množiny:
-(a)—{i | W2 je konečna] —(b)—{i | Wt je rekurzívní}
(c)   {z | Wi je rekurzívní, ale ani W% ani VF; není konečná} o ^
U každé z nich zjistěte, zda množina respektuje funkce, zda je rekurzívní, r.e. nebo není r.e. a zdůvodněte.
u-A A
A.
?
V. ~7 m
a
1      ^ty t
N = 0 Jí ji U
7 /
-k  0 éA
6a"
0 é
1 Jk