Redukce
12.1 Rozhodněte, zda platí následující implikace. Své rozhodnutí zdůvodněte.
a) A <m B =>• co—A <m co—B
b) A <m B a B je regulární => A je regulární
c) A je rekurzivně spočetná a co—A <m A => A je rekurzivní
d) A je rekurzivně spočetná a A <m co—A => A je rekurzivní
e) ^4 <m _B a A je rekurzivní => B je rekurzivní
f) A je rekurzivně spočetná =>• A <m HALT
12.2 Je dán jazyk A = {(M) \ výpočet TM M na slově e je konečný}.
Dokažte, že A není rekurzivní. (Návod: najděte redukci problému zastavení na A.)
Je jazyk A rekurzivně spočetný?
Je komplement jazyka A rekurzivně spočetný?
12.3 Nalezněte řešení následujícího Postova systému:
" aa~		' ab '		■b-		aha'
. a .	7	.abab.	7	.a.	7	i b \
12.4 Ukažte, že Postův korespondenční problém je nerozhodnutelný, i když se omezíme na abecedu {0,1}.
12.5 Ukažte, že problém ekvivalence dvou Turingových strojů
EQ = {(Mi, M2) | Mi a M2 jsou Turingovy stroje a L(M\) = L(M2)} je nerozhodnutelný.
22