IB005 úkol 13, příklad 2 Odevzdání: 22. 5. 2020 12:00
Jméno: UČO:
list učo body
Oblast strojově snímaných informací. Své učo a číslo listu vyplňte
zleva dle vzoru číslic. Jinak do této oblasti nezasahujte.
2. [0,5 bodu] Dokažte, že problém určit, zda Turingův stroj M akceptuje slovo a, je nerozhodnutelný.
Jinými slovy, dokažte, že jazyk
HAS_A = { M | a ∈ L(M)}
není rekursivní.
Návod: Ukažte, že platí vztah N ≤m HAS_A, kde N je vhodný nerekursivní jazyk. Zdůvodněte,
proč tudíž jazyk HAS_A nemůže být rekursivní.
Oblast strojově snímaných informací, nezasahujte. Druhá strana se neskenuje. Zde jsou losi.