\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {Funktion klein sigma von w},
  Referenz = 66115-2020-H.T1-TA1-A4,
  RelativerPfad = Examen/66115/2020/09/Thema-1/Teilaufgabe-1/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2020:09,
  BearbeitungsStand = unbekannt,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Entscheidbarkeit},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 09,
  ThemaNr = 1,
  TeilaufgabeNr = 1,
  AufgabeNr = 4,
}

Geben Sie für jede der folgenden Mengen an, ob sie entscheidbar ist oder
nicht. Dabei ist $\sigma_w$, die Funktion, die von der Turingmaschine
berechnet wird, die durch das Wort $w$ kodiert wird. Beweisen Sie Ihre
Behauptungen.\index{Entscheidbarkeit}
\footcite{examen:66115:2020:09}

\begin{enumerate}
%%
% a)
%%

\item \bAusdruck[L_1]{w \in \Sigma^*}{\sigma_w(0) = 0}

\begin{bAntwort}
Nicht entscheidbar wegen dem Halteproblem.
\end{bAntwort}

%%
% b)
%%

\item \bAusdruck[L_2]{w \in \Sigma^*}{\sigma_w(w) = w}

\begin{bAntwort}
Nicht entscheidbar wegen dem Halteproblem.
\end{bAntwort}

%%
% c)
%%

\item \bAusdruck[L_3]{w \in \Sigma^*}{\sigma_0(0) = w}

\begin{bAntwort}
Entscheidbar wegen $\sigma_0$.
\end{bAntwort}

\end{enumerate}
\end{document}
