IB102 – úkol 10, příklad 1 Odevzdání: 14. 12. 2015
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém určit, zda Turingův stroj M akceptuje nekonečně
mnoho slov, je nerozhodnutelný. Jinými slovy, dokažte, že jazyk
L = { M | L(M) je nekonečný}
není rekurzivní.
Návod: Ukažte, že platí vztah N ≤m L, kde N je vhodný nerekurzivní jazyk. Zdůvodněte,
proč tudíž jazyk L nemůže být rekurzivní.