X- °\t>
60
			
<	l	c	
	<		
			
^ CH W
O * erb
A ^ (f)
3.1 Nechť A je nekonečná r.e. množina, pro jejíž nnmerující funkci / platí:
pro všechna n > 0 : f(2n + 3) > f(2n + 1) a^/(2n + 2) > f(2n)
Dokažte, že A musí být rekurzívní. litkí,
A
V
Sví
o
"i
(K
l.
tkOt/vA VÍC
1/
*—^
A
3 výZi'stU\^ JJ"
3
3.3 Použijte techniku "paralelního zpracování" k důkazu toho, že následující množiny jsou rekurzívně spočetné:
(a) {i | <pi    e}, kde e je prázná funkce, -=>
(b) {i | ipi není prostá},
(c) {z | ifi není konstantní funkce},
(d) {n | a € dom(y>„)}, pro pevné o G N,
(e) {n | a G range(<£>„)}, pro pevné a G N.
míro
^"vnW   / Ii- /"\
J /
[
I * 1 v/\
r
LU o