IB102 – úkol 10, příklad 1 Odevzdání: 8. 12. 2014
Vypracoval(a): UČO:
Skupina:
1. [2 body] Dokažte, že problém určit, zda funkce popsaná zadaným Turingovým strojem
M má v oboru hodnot řetězec „redukce“, je nerozhodnutelný. Jinými slovy, dokažte, že
jazyk
L = { M | existuje slovo w, pro které platí M(w) = redukce}
není rekurzivní.
Návod: Ukažte, že platí vztah HALT ≤m L, a zdůvodněte, proč tudíž jazyk L nemůže
být rekurzivní.