\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 4},
  Thematik = {Berechenbarkeitstheorie},
  Referenz = 66115-2020-F.T2-A4,
  RelativerPfad = Examen/66115/2020/03/Thema-2/Aufgabe-4.tex,
  ZitatSchluessel = examen:66115:2020:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Berechenbarkeit},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 03,
  ThemaNr = 2,
  AufgabeNr = 4,
}

% Info_2021-05-07-2021-05-07_13.30.16.mp4
% 1h47min - 1h57min

\bAusdruck[A]{(M)}{M\text{ ist Turingmaschine, die bei Eingabe }101\text{ hält}}.
Dabei bezeichnet (M) die Gödelnummer der Turingmaschine $M$.
\index{Berechenbarkeit}
\footcite{examen:66115:2020:03}

\begin{enumerate}

%%
% (a)
%%

\item Zeigen Sie, dass $A$ unentscheidbar ist.

\begin{bAntwort}
Reduktionsbeweis von H 0 ≤ A:
TM U
\begin{enumerate}

\item Die zu 𝑀 ′ ∈ 𝐻 0 passende TM 𝑀 ∗ ∈ 𝐴 aus A suchen mit < 𝑀 ′ > = < 𝑀 ∗ >
\item 101 auf das Band schreiben
\item 𝑀 ∗ auf 101 starten
\end{enumerate}
Damit könnte U H 0 entscheiden, was aber ein Widerspruch zu H0 semi-
entscheidbar ist. Damit ist A ebenfalls semi-entscheidbar.
\end{bAntwort}

%%
% (b)
%%

\item Zeigen Sie, dass $A$ semi-entscheidbar ist.

\begin{bAntwort}
siehe a)
\end{bAntwort}

%%
% (c)
%%

\item Ist das Komplement $A^c$ von $A$ entscheidbar? Ist es semi-entscheidbar? Begründen
Sie Ihre Antworten.

Hinweis: Sie können die Aussagen aus Teilaufgabe a) und b) verwenden, auch wenn Sie sie
nicht bewiesen haben.

\begin{bAntwort}
Wenn $A$ unentscheidbar ist, dann kann entweder $A$ oder $A^c$
semi-entscheidbar sein. Wären beide semi-entscheidbar, dann wäre $A$
aber ebenfalls entscheidbar, was aber nach Voraussetzung ausgeschlossen
ist.
\footcite[Seite 52]{theo:fs:4}
\end{bAntwort}

\end{enumerate}
\end{document}