\documentclass[a4paper, 12pt]{article}

% Deutsch
% \usepackage{ngerman}
% \usepackage[ansinew]{inputenc}
% \usepackage[T1]{fontenc}
% \usepackage{lmodern}
\usepackage[main=ngerman,british]{babel}

% Sonderzeichen
% \usepackage{bbold}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{stmaryrd}
\usepackage{mathtools}

% Zeilenumbruch
\usepackage{breqn}

% Brüche
\usepackage{xfrac}
% \newcommand\sfrac[2]{#1/#2}

% Aufzählungen
\usepackage{enumerate}
\usepackage{paralist}
\usepackage{multicol}

% Farbe (für Lösungen)
\usepackage{xcolor}
\definecolor{darkgray}{gray}{0.3}

% Footer / Header
\usepackage{fancyhdr}
\usepackage{lastpage}

% Für den Header
\usepackage[strict]{changepage}

% Seitenlayout und -stil
\usepackage[a4paper,top=15mm,bottom=25mm,left=25mm, right=25mm]{geometry}
\pagestyle{fancy}
\fancyhf{}
\renewcommand{\headrulewidth}{0.0pt}
\cfoot{(Seite \thepage \hspace{1pt} von \pageref{LastPage})}
\usepackage{adjustbox}

% zum Testen
% \overfullrule=2cm
\usepackage{lipsum}

\usepackage{graphicx}
\usepackage{tikz}
% \usetikzlibrary{calc,decorations.pathreplacing,shapes.geometric,arrows.meta}
\usetikzlibrary{calc,decorations.pathreplacing,shapes,arrows.meta,bending}
\usepackage{rotating}
\usepackage{caption}
\usepackage{subcaption}
\renewcommand{\figurename}{\footnotesize Abb.}

% Algorithmen
\usepackage{algorithm, comment}
\usepackage{algpseudocode}
\usepackage{listings}
\usepackage{lstautogobble}

% Sprachen
\lstdefinelanguage{goto}
	{morekeywords={GOTO,IF,THEN,HALT},
	sensitive=false,
	morecomment=[l]{//},
	morecomment=[s]{/*}{*/},
	morestring=[b]",
	moredelim=[is][\color{olive}]{@}{@},
	keywordstyle=\color{teal},
	commentstyle={\ttfamily\color{darkgray}},
	tabsize=2,
	basicstyle=\ttfamily
}
\lstdefinelanguage{pseudo}
	{morekeywords={function,if,then,else,fi,for,to,step,do,od,end,while,repeat,until,foreach,return},
	sensitive=false,
	morecomment=[l]{//},
	morecomment=[s]{/*}{*/},
	morestring=[b]",
	moredelim=[is][\color{olive}]{@}{@},
	keywordstyle=\bfseries\color{teal},
	commentstyle={\ttfamily\color{darkgray}},
	tabsize=2,
	basicstyle=\ttfamily,
	mathescape=true,
	numbers=left,
	numbersep=5pt,
	numberstyle=\small\color{darkgray},
	frame=leftline,
	rulecolor=\color{darkgray}
}

% foreach
\algnewcommand\algorithmicforeach{\textbf{foreach}}
\algdef{S}[FOR]{ForEach}[1]{\algorithmicforeach\ #1\ \algorithmicdo}

% loop
\algrenewcommand\algorithmicloop{\textbf{loop}}
\algdef{S}[WHILE]{LoopX}[1]{\algorithmicloop\ #1\ \algorithmicdo}
\newcommand{\EndLoopX}{\algrenewtext{EndWhile}{{\newalgstyle end}}\EndWhile\algrenewtext{EndWhile}{{\newalgstyle od}}}

% custom keywords
\newcommand{\key}[1]{{\ttfamily\bfseries\color{teal}#1}}
\newcommand{\Input}[1]{\Statex\key{Input:} {#1}}

% full line comment
\newcommand{\linecomment}[1]{\Statex{\color{darkgray}$\triangleright$ #1}}

% algorithmic-Anpassungen
\algrenewcommand\algorithmiccomment[1]{{\color{darkgray}\hfill$\triangleright$ #1}}
\newcommand\newalgstyle{\ttfamily\bfseries\color{teal}}
\algrenewcommand\algorithmicend{{\newalgstyle end}}
\algrenewcommand\algorithmicdo{{\newalgstyle do}}
\algrenewcommand\algorithmicwhile{{\newalgstyle while}}
\algrenewcommand\algorithmicfor{{\newalgstyle for}}
\algrenewcommand\algorithmicforall{{\newalgstyle for all}}
\algrenewcommand\algorithmicforeach{{\newalgstyle for each}}
\algrenewcommand\algorithmicloop{{\newalgstyle loop}}
\algrenewcommand\algorithmicrepeat{{\newalgstyle repeat}}
\algrenewcommand\algorithmicuntil{{\newalgstyle until}}
\algrenewcommand\algorithmicprocedure{{\newalgstyle procedure}}
\algrenewcommand\algorithmicfunction{{\newalgstyle function}}
\algrenewcommand\algorithmicif{{\newalgstyle if}}
\algrenewcommand\algorithmicthen{{\newalgstyle then}}
\algrenewcommand\algorithmicelse{{\newalgstyle else}}
\algrenewcommand\algorithmicrequire{{\newalgstyle Require:}}
\algrenewcommand\algorithmicensure{{\newalgstyle Ensure:}}
\algrenewcommand\algorithmicreturn{{\newalgstyle return}}
\algrenewtext{EndWhile}{{\newalgstyle od}}
\algrenewtext{EndFor}{{\newalgstyle od}}
\algrenewtext{EndLoop}{{\newalgstyle od}}
\algrenewtext{EndIf}{{\newalgstyle fi}}
\algrenewtext{EndFunction}{{\newalgstyle end}}

% kleine Aufzählungszeichen & Prozent
% \renewcommand{\labelitemi}{\raise .5ex\hbox{\tiny$\bullet$}}
\renewcommand\labelitemi{$\vcenter{\hbox{\tiny$\bullet$}}$}
% \renewcommand{\labelitemi}{\boldmath$\cdot$}
\newcommand{\pct}{\,\scalebox{.9}{\%} }

% \Item-Befehl, damit Align-Umgebungen in der richtigen Zeile beginnen
\newcommand\Item[1][]{%
  \ifx\relax#1\relax  \item \else \item[#1] \fi
  \abovedisplayskip=0pt\abovedisplayshortskip=0pt~\vspace*{-\baselineskip}
}

% Damit man Anführungszeichen hübscher schreiben kann als "`"'
\newcommand{\enquote}[1]{``{#1}''}

% für die Kurzschreibweisen
\usepackage{xspace}

% Kurzschreibweisen
\newcommand{\setN}{\mathbb{N}}
\newcommand{\setZ}{\mathbb{Z}}
\newcommand{\setQ}{\mathbb{Q}}
\newcommand{\setR}{\mathbb{R}}
\newcommand{\setP}{\mathbb{P}}
\newcommand{\sigStar}{\Sigma^{*}}
\newcommand{\EStar}{E^{*}}
\newcommand{\binStar}{\{0,1\}^{*}}
\newcommand{\Oh}[1]{\mathcal{O}({#1})}
\newcommand{\OhOmega}[1]{\Omega({#1})}
\newcommand{\OhTheta}[1]{\Theta({#1})}
\newcommand{\qed}{\hfill $\square$}
\newcommand{\Null}{\textsc{Null}\xspace}
\newcommand{\overbar}[1]{\mkern 1.5mu\overline{\mkern-1.5mu#1\mkern-1.5mu}\mkern 1.5mu}
\newcommand{\True}{\textsc{True}\xspace}
\newcommand{\False}{\textsc{False}\xspace}
\newcommand{\defeq}{\vcentcolon=} % := (benötigt mathtools)
\newcommand{\eqdef}{=\vcentcolon} % =: (benötigt mathtools)
\newcommand{\Hinweis}[1]{\smallskip\noindent(\emph{Hinweis:} {#1})}
\newcommand{\Bemerkung}[1]{\smallskip\noindent(\emph{Bemerkung:} {#1})}
\newcommand{\ztm}[2]{\begin{array}{c} {#1} \\ {#2} \end{array}}

% Gaußklammern
\providecommand{\floor}[1]{\left \lfloor #1 \right \rfloor }
\providecommand{\ceil}[1]{\left \lceil #1 \right \rceil }

% Mathekommentare
\newcommand{\mathcomm}[1]{\triangleright~\text{#1}}
% Farbig unterstreichen
\def\mathunderline#1#2{\color{#1}\underline{{\color{black}#2}}\color{black}}

% Silbentrennung
\hyphenation{While-Schlei-fe}
\hyphenation{While-be-rech-en-bar}

% Mayaziffern
\usepackage{fontspec}
\newfontface{\babm}{BabelStone Mayan Numerals}
\DeclareRobustCommand\mzero{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E0}}}%
}
\DeclareRobustCommand\mone{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E1}}}%
}
\DeclareRobustCommand\mtwo{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E2}}}%
}
\DeclareRobustCommand\mthree{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E3}}}%
}
\DeclareRobustCommand\mfour{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E4}}}%
}
\DeclareRobustCommand\mfive{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E5}}}%
}
\DeclareRobustCommand\msix{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E6}}}%
}
\DeclareRobustCommand\mseven{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E7}}}%
}
\DeclareRobustCommand\meight{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E8}}}%
}
\DeclareRobustCommand\mnine{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2E9}}}%
}
\DeclareRobustCommand\mten{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EA}}}%
}
\DeclareRobustCommand\meleven{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EB}}}%
}
\DeclareRobustCommand\mtwelve{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EC}}}%
}
\DeclareRobustCommand\mthirteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2ED}}}%
}
\DeclareRobustCommand\mfourteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EE}}}%
}
\DeclareRobustCommand\mfifteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2EF}}}%
}
\DeclareRobustCommand\msixteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F0}}}%
}
\DeclareRobustCommand\mseventeen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F1}}}%
}
\DeclareRobustCommand\meighteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F2}}}%
}
\DeclareRobustCommand\mnineteen{%
    \mathrel{\text{\normalfont\babm\symbol{"01D2F3}}}%
}

% Counter für Aufgaben
\newcounter{AufgabenNummer}
\setcounter{AufgabenNummer}{1}

% Counter für Lösungen
\newcounter{LoesungNummer}
\setcounter{LoesungNummer}{1}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ÄNDERN
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Variablen für Übungsnummer und Abgabedatum
\newcommand\Nummer{5}
\newcommand\Abgabe{10.\,Dezember 2021 um 12 Uhr}
\newif\ifhideloesung
\usepackage{substr}
\IfSubStringInString{\detokenize{loesung}}{\jobname}{}{\hideloesungtrue}
% \hideloesungtrue % Nicht kommentiert = Lösungen versteckt

% Environment für Aufgaben
\newenvironment{aufgabe}[1]{\noindent \textbf{Aufgabe \Nummer{}.\arabic{AufgabenNummer}} \textit{(#1 Punkte)} \nopagebreak \smallskip \par \noindent \ignorespaces}{\stepcounter{AufgabenNummer} \bigskip}

% Environment für Lösungen
\newenvironment{loesung}{\color{blue} \noindent \textbf{Lösung} \nopagebreak \smallskip \par \noindent \ignorespaces}{\bigskip}

% Environment für Lösungen 2
\newenvironment{loesung2}{\color{blue} \noindent \textbf{Lösung \Nummer{}.\arabic{LoesungNummer}} \nopagebreak \smallskip \par \noindent \ignorespaces}{\stepcounter{LoesungNummer} \bigskip}

% Environment für Ankündigungen
\newenvironment{ankuendigung}{\noindent \hrulefill \medskip \par \noindent \textbf{Ankündigung:} }{\par \noindent \hrulefill \bigskip}

% Environment für Mitteilung
\newenvironment{mitteilung}{\noindent \hrulefill \medskip \par \noindent \textbf{Mitteilung:} }{\par \noindent \hrulefill \bigskip}

% Environment für Definitionen
\newenvironment{definition2}{\noindent \textbf{Definition(en)} \smallskip \par \noindent \ignorespaces}{\bigskip}

% Environment für Dateinamensschema
% \newenvironment{dateinamensschema}{\noindent \hrulefill \medskip \par \noindent \textbf{Bitte beachten Sie die folgenden Vorgaben für die Abgabe:}}{\par \noindent \hrulefill \bigskip}
\newenvironment{dateinamensschema}{\noindent \hrulefill \medskip \par \noindent \textbf{Bitte beachten Sie die folgenden Vorgaben für die Abgabe:}}{\par \noindent \hrulefill \pagebreak}

% Kopfzeile
\newcommand{\Kopfzeile}{
\begin{center}
	\noindent
	\parbox[t][5em][c]{0.5\textwidth}{
	\begin{flushleft}
		\textmd{Datenstrukturen und Effiziente Algorithmen} \\
		\textit{Fachbereich IV - Informatik} \\
		\textit{Universität Trier}
	\end{flushleft}}
	\hfill
	\parbox[t][5em][c]{0.49\textwidth}{
	\begin{flushright}
		Moritz Gobbert \\
		\textit{gobbert@uni-trier.de} \\
		\textit{Raum H\,428}
	\end{flushright}}
\end{center}
\bigskip
}

% Titel
\newcommand{\Titel}{
\begin{center}
	{\Large Berechenbarkeit und Komplexitätstheorie} \\
	Wintersemester 2021/2022 \\
	Aufgabenblatt \Nummer \\
	\textbf{Abgabe: \Abgabe}
\end{center}
}

\ifhideloesung
	\usepackage{environ}
	\NewEnviron{hide}{}
	\let\loesung\hide
	\let\endloesung\endhide
\else
	\usepackage{environ}
	\NewEnviron{hide}{}
	\let\dateinamensschema\hide
	\let\enddateinamensschema\endhide
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%                               Textanfang                                                   %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
	\Titel
	\bigskip
	\begin{dateinamensschema}
		Geben Sie nur eine \emph{einzelne} Datei ab. Diese Datei sollte vorzugsweise im \texttt{pdf}-Format sein. Falls Ihre Abgabe aus mehr als einer Datei besteht, dann packen Sie diese bitte zusammen in ein \texttt{zip}-Archiv. Notieren Sie auf Ihrer Abgabe die Namen und Matrikelnummern aller an der Abgabe beteiligten Personen. Achten Sie darauf, dass Ihre Datei leserlich ist -- insbesondere bei Fotos einer handschriftlichen Abgabe. Bezeichnen Sie die abzugebende Datei nach dem folgenden Muster:
		
		\begin{center}\texttt{Nachname\_Vorname\_Matrikelnummer.pdf} (bzw.\ \texttt{.zip})\end{center}
		
		\noindent{}Falls Sie als Gruppe abgeben reichen als Dateiname die Daten eines Gruppenmitglieds -- die Daten der anderen Mitglieder stehen in der Lösung selbst. Zur Abgabe gibt es in \emph{Moodle} einen passenden Abschnitt namens \enquote{\texttt{Übung \Nummer}} in dem Sie Ihre Lösungen hochladen können.
		
		Abgabetermin ist Freitag, der \textbf{\Abgabe}.
	\end{dateinamensschema}
	
	\begin{definition2}
		Seien $A, B \subseteq \sigStar$ beliebige Mengen. $A$ heißt \emph{reduzierbar} auf $B$ ($A \leq B$), falls es eine totale und berechenbare Funktion $f: \sigStar \rightarrow \sigStar$ gibt mit: $w \in A \Leftrightarrow f(w) \in B$.
	\end{definition2}
	
	\begin{aufgabe}{3}
		Sei $f: \sigStar \rightarrow \setN$ eine \emph{totale} Funktion mit der Eigenschaft: Falls für ein $w \in \sigStar$ die TM $M_w$ angesetzt auf $w$ hält, dann geschieht dies in weniger als $f(w)$ Schritten. Zeigen Sie: $f$ ist nicht berechenbar.
	\end{aufgabe}
	
	\begin{loesung}
		Da $f$ total, gilt für alle $w \in \sigStar: f(w) \in \setN$. Das heißt, falls $M_w$ angesetzt auf $w$ hält, dann liefert $f(w)$ eine Obergrenze an die Anzahl der Rechenschritte. Falls $M_w$ angesetzt auf $w$ nicht hält, dann liefert die Funktion nur eine nichtssagende natürliche Zahl. Sei nun $w \in \sigStar$ beliebig. Angenommen $f$ ist berechenbar. Betrachte folgenden Algorithmus:
		\begin{enumerate}[\quad 1.]
			\item Berechne $f(w)$.
			\item Lasse $M_w$ auf $w$ angesetzt laufen und zähle die Rechenschritte mit.
			\item Falls $M_w$ nach $f(w)$ Schritten noch immer nicht hält, dann stoppe und gib \textsc{falsch} aus.
			\item Sonst gib \textsc{wahr} aus.
		\end{enumerate}
		Dieser Algorithmus entscheidet das spezielle Halteproblem. Dies ist ein Widerspruch. Also kann $f$ nicht berechenbar sein.
	\end{loesung}
	
	% \begin{aufgabe}{2 + 2}
		% Sei $K$ das in der Vorlesung definierte spezielle Halteproblem. Zeigen Sie:
		% \begin{enumerate}[\quad a)]
			% \item $K$ ist semi-entscheidbar.
			% \item Das Komplement $\bar{K} = \sigStar \setminus K$ ist nicht semi-entscheidbar.
		% \end{enumerate}
	% \end{aufgabe}
	
	% \begin{loesung}
		% \begin{enumerate}[\quad a)]
			% \item Wir berechnen $\hat{\chi}_K$ mithilfe einer universellen TM $M$. Diese bekommt als Eingabe die Beschreibung einer TM $\hat{M}$ und ein Wort $w$. Wir simulieren $\hat{M}_w$ mit Eingabe $w$ auf der UTM $M$. Wenn $\hat{M}_w$ angesetzt auf $w$ hält, dann leeren wir das Arbeitsband und schreiben eine $1$. Ansonsten hält (die Simulation von) $M_w$ nicht und die Funktion $\hat{\chi}_K$ ist an dieser Stelle undefiniert.
			% \item Angenommen $\bar{K}$ wäre semi-entscheidbar. Da $K$ semi-entscheidbar ist (Teil a)), wäre $K$ sogar entscheidbar. Dies ist ein Widerspruch dazu, dass das spezielle Halteproblem nicht entscheidbar ist.
		% \end{enumerate}
	% \end{loesung}
	
	\begin{aufgabe}{2 + 1 + 2 + 1}\label{aufg:entscheidbar}
		Seien $A,B \subseteq \sigStar$ zwei beliebige Sprachen und sei $A$ auf $B$ reduzierbar mittels Funktion $f$. Zeigen Sie:
		\begin{enumerate}[\quad (i)]
			\item\label{aufg:entscheidbar:a} $B \text{~entscheidbar} \Rightarrow A \text{~entscheidbar}$
			\item\label{aufg:entscheidbar:b} $A \text{~nicht entscheidbar} \Rightarrow B \text{~nicht entscheidbar}$
			\item\label{aufg:entscheidbar:c} $B \text{~semi-entscheidbar} \Rightarrow A \text{~semi-entscheidbar}$
			\item\label{aufg:entscheidbar:d} $A \text{~nicht semi-entscheidbar} \Rightarrow B \text{~nicht semi-entscheidbar}$
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		(Die folgenden Lösungen könnte man auch in eine Lösung zusammenfassen -- im Prinzip nutzen alle vier Teilaufgaben die selbe Äquivalenzkette.)
		\begin{enumerate}[\quad a)]
			\item Sei $B$ entscheidbar, dann ist $\chi_{B}$ berechenbar. Da $f$ nach Definition der Reduzierbarkeit ebenfalls berechenbar ist, ist auch die Komposition $\chi_{B} \circ f$ berechenbar. In dem Fall gilt für $x \in \sigStar$:
				\begin{align*}
					\chi_{A}(x) = 1 &\equiv x \in A &\mathcomm{Def.\ char.\ Funktion}\\
						&\equiv f(x) \in B &\mathcomm{$A$ ist reduzierbar auf $B$}\\
						&\equiv \chi_{B}(f(x)) = 1 &\mathcomm{Def.\ char.\ Funktion}
				\end{align*}
				\begin{align*}
					\chi_{A}(x) = 0 &\equiv x \notin A &\mathcomm{Def.\ char.\ Funktion}\\
						&\equiv f(x) \notin B &\mathcomm{$A$ ist reduzierbar auf $B$}\\
						&\equiv \chi_{B}(f(x)) = 0 &\mathcomm{Def.\ char.\ Funktion}
				\end{align*}
				Damit gilt $\chi_{B} \circ f = \chi_{A}$. Und da $B$ entscheidbar ist (also $\chi_{B}$ berechenbar ist) ist auch $\chi_{A}$ berechenbar und somit $A$ entscheidbar.
			\item Angenommen $B$ sei entscheidbar, dann wäre $\chi_{B}$ berechenbar. Da $f$ nach Definition der Reduzierbarkeit ebenfalls berechenbar ist, ist auch die Komposition $\chi_{B} \circ f$ berechenbar. In dem Fall gilt für $x \in \sigStar$ (genau wie im vorigen Aufgabenteil):
				\begin{align*}
					\chi_{A}(x) = 1 &\equiv x \in A &\mathcomm{Def.\ char.\ Funktion}\\
						&\equiv f(x) \in B &\mathcomm{$A$ ist reduzierbar auf $B$}\\
						&\equiv \chi_{B}(f(x)) = 1 &\mathcomm{Def.\ char.\ Funktion}
				\end{align*}
				Der andere Fall ($\chi_{A}(x) = 0$) folgt ebenfalls wieder analog. Damit gilt $\chi_{B} \circ f = \chi_{A}$. Das heißt $\chi_{A}$ ist berechenbar und $A$ entscheidbar, was einen Widerspruch zur Prämisse ($A$ nicht entscheidbar) darstellt.
				
				(Alternativ kann man hier auch kürzer über Kontraposition argumentieren. Nach Aufgabenteil (\ref{aufg:entscheidbar:a}) gilt $B \text{~entscheidbar} \Rightarrow A \text{~entscheidbar}$ und das ist äquivalent zu Aussage (\ref{aufg:entscheidbar:b}).)
			\item Analog zum vorigen Aufgabenteil gilt für $x \in \sigStar$:
				\begin{align*}
					\chi'_{A}(x) = 1 &\equiv x \in A &\mathcomm{Def.\ eingeschränkte char.\ Funktion}\\
						&\equiv f(x) \in B &\mathcomm{$A$ ist reduzierbar auf $B$}\\
						&\equiv \chi'_{B}(f(x)) = 1 &\mathcomm{Def.\ eingeschränkte char.\ Funktion}
				\end{align*}
				Der andere Fall ($\chi'_{A}(x) = \text{undefiniert} \equiv \chi'_{B}(f(x)) = \text{undefiniert}$) gilt analog. D.\,h.\ man kann $A$ mithilfe von $B$ \enquote{semi-entscheiden}.
			\item Hier kann man wieder wie im ersten Aufgabenteil einen Widerspruch zeigen, oder ausnutzen, dass Aussage (\ref{aufg:entscheidbar:c}) und (\ref{aufg:entscheidbar:d}) äquivalent sind (\emph{Kontraposition}).
		\end{enumerate}
	\end{loesung}
	
	\begin{aufgabe}{2 + 2 + 2}
		Seien $A,B,C \subseteq \sigStar$ beliebige, nicht-leere Mengen. Zeigen Sie:
		\begin{enumerate}[\quad a)]
			\item $A \leq B$ genau dann, wenn $\bar{A} \leq \bar{B}$.
			% \item Falls $B$ semi-entscheidbar und $A \leq B$, dann ist $A$ semi-entscheidbar.
			\item Aus $A \leq B$ und $B \leq C$ folgt $A \leq C$.
			\item $A$ ist entscheidbar genau dann, wenn $A$ semi-entscheidbar ist und $A \leq \bar{A}$.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		Im Folgenden sind $f,g: \sigStar \rightarrow \sigStar$ totale und berechenbare Funktionen, die für die jeweiligen Reduktionen passend sind.
		\begin{enumerate}[\quad a)]
			\item$\begin{aligned}[t]
					A \leq B &\equiv \exists f: w \in A \Leftrightarrow f(w) \in B \\
					&\equiv \exists f: \neg (w \in A) \Leftrightarrow \neg (f(w) \in B) \\
					&\equiv \exists f: w \in \bar{A} \Leftrightarrow f(w) \in \bar{B} \\
					&\equiv \bar{A} \leq \bar{B}
				\end{aligned}$
			% \item Um zu zeigen, dass $A$ semi-entscheidbar ist müssen wir eine Funktion $\hat{\chi}_{A}: \sigStar \rightarrow \{\text{undefiniert}, 1\}$ angeben mit $\hat{\chi}_{A}(w) = \begin{cases} 1, &w \in A \\ \text{undefiniert}, &\text{sonst}\end{cases}$ \\
			% Da $A \leq B$ $\exists f: w \in A \Leftrightarrow f(w) \in B$. Und da $B$ semi-entscheidbar gibt es die passende Funktion $\hat{\chi}_{B}$. Wir definieren $\hat{\chi}_{A}(w) = \hat{\chi}_{B}(f(w))$.
			\item Es gilt:
				\begin{align*}
					A \leq B &\equiv \exists f \colon w \in A \Leftrightarrow f(w) \in B &\mathcomm{Def. Reduzierbarkeit}\\
					B \leq C &\equiv \exists g \colon w \in B \Leftrightarrow g(w) \in C &\mathcomm{Def. Reduzierbarkeit}
				\end{align*}
				Wir definieren eine neue Funktion $h \colon \sigStar \rightarrow \sigStar$, $h(w) = g(f(w))$. $h$ ist berechenbar und total, weil $f$ und $g$ es auch sind. Weiter folgt aus den Reduzierbarkeiten zwischen $A$ und $B$ bzw. $B$ und $C$, dass $w \in A \Leftrightarrow f(w) \in B \Leftrightarrow g(f(w)) \in C$, also $A \leq C$.
			\item \enquote{$\Rightarrow$}:
			
			Seien $a \in A$ und $b \notin A$ beliebig. Wir definieren $f: \sigStar \rightarrow \sigStar$ mit
				\begin{gather*}
					f(w) = \begin{cases} a, &w \notin A \\ b, &w \in A\end{cases}
				\end{gather*}
			Damit gilt dann $w \in A \equiv f(w) \notin A \equiv f(w) \in \bar{A}$ und da $A$ entscheidbar ist $f$ berechenbar und total. \medskip\\
			\noindent \enquote{$\Leftarrow$}:
			
			\noindent\phantom{$\Rightarrow$} $A$ semi-entscheidbar und $A \leq \bar{A}$ \\
			$\Rightarrow$ $A$ semi-entscheidbar und $\bar{A} \leq A$ (folgt aus Teil a) zusammen mit $\bar{\bar{A}} = A$) \\
			$\Rightarrow$ $A$ semi-entscheidbar und $\bar{A}$ semi-entscheidbar (Aussage (\ref{aufg:entscheidbar:c}) aus der vorigen Aufgabe) \\
			$\Rightarrow$ $A$ entscheidbar. (Siehe Aufgabe 4.2)
		\end{enumerate}
	\end{loesung}
\label{lastpage}
\end{document}