\documentclass{ib102}
\usepackage[shorthands=off,czech]{babel}

% vim: fo+=t tw=80 spell spelllang=cs
% gen: ready

\assignment{11}
\exercise{1}
\points{2}
\duedate{12. 12. 2016}

%%% ZDE NAPISTE SVOJE UCO, JMENO A SKUPINU
\name{}
\group{}
\uco{}


\begin{document}
\begin{zadani}
    Dokažte, že problém určit, zda stav $q$ Turingova stroje $\mathcal{M}$ je
    dosažitelný, je nerozhodnutelný. Jinými slovy, dokažte, že jazyk
    \[
        \text{USEFUL}= \{ \langle \mathcal{M}, q \rangle \mid \text{stav } q
        \text{ Turingova stroje } \mathcal{M} \text{ je
        dosažitelný} \}
    \]
	není rekurzivní. Stav $q$ Turingova stroje $\mathcal{M}$ nazveme
    dosažitelným, pokud existuje vstup, na kterém se výpočet stroje
    $\mathcal{M}$ dostane do stavu $q$.

    \bigskip
    \noindent
    Návod: Ukažte, že platí vztah $N \leq_m \text{USEFUL}$, kde $N$ je vhodný
    nerekurzivní jazyk. Zdůvodněte, proč tudíž jazyk USEFUL nemůže být rekurzivní.
\end{zadani}

\begin{reseni}
%%% SEM PISTE SVE RESENI
\end{reseni}

\end{document}
