6.1 Problém rozhodnout, zda program Pí zastaví na vstupu j, můžeme nazvat ojfecným problémem zastavení a ztotožnit jej s množinou , . - \ sy^ n>i -|- 0^
0Ä" =        | ví(j) je definováno}.
Připomeňme, že {■, ■) je párující funkce. Pomocí redukce dokažte, že tento problém není rozhodnutelný, ale je částečně rozhodnutelný.
6.3 Je dán jazyk
(a) Dokažt
(b) Jejazyl
(c) Je kom]
1/ ^ 0(C
^ ŕ
c.G>—
v é k ^ {(*) eo^
míro
Vy cv^ ■. (
/  ' * .    '   (jt -U ^'
r, « ■} 4 Ol ^ Ví) = i. * t A ^ ^
míro
6.3 Je dán jazyk A = {(M) | výpočet TM M na slově e je konečný}.
(a) Dokažte, že A není rekurzivní.
(b) Je jazyk A rekurzivně spočetný?
(c) Je komplement jazyka A rekurzivně spočetný?
°\) WíVrT' \(y\tiS) [ ^*j€,~lft Usy u^*^ ^\ J-^ ^
6.2 Rozhodněte,
(a) A <m 1
(b) A je rek
(c) A je rek
(d) A <m 1
(e) A je koi
(f) A je rek
(g) A je rek
f (i) j. H \
^ -f -4'
.....v ^
A
A
r i
6.2 Rozhodněte, zda následující implikace pro libovolné A, B C N. Své rozhodnutí zdůvodněte.
(a) A <m B       A <m B
(b) A je rekurzivně spočetná a A <m A => A je rekurzivní
(c) A je rekurzivně spočetná a A <m A => A je rekurzivní
(d) A <m B a A je rekurzivní => £? je rekurzivní
(e) ^4 je konečná => A <m {1}
(f) A je rekurzivní =>• A <m {1}
(g) A je rekurzivní => {1} <m A
CJ A y ^   A ^ ^ A je. *l ?
O AT
} fjt Mé.        i:i u^Ulw
1
niro
.<.) Mé. tó- í:J
A  "c   L^äJ.   = > A. s_
Á    r ^ ^ R c ^
miro