\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{4}
\newcommand\Abgabe{3.\,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{aufgabe}{4}
		% Die Wahrheitswerte \textsc{wahr} und \textsc{falsch} lassen sich in einer Variablen $x_i$ mittels $x_i \neq 0$ und $x_i = 0$ darstellen. Schreiben Sie (möglichst kurze) \textsc{Loop}-Programme für die logischen Verknüpfungen $\vee$, $\neg$, \textsc{Nand} und $\Rightarrow$.
	% \end{aufgabe}
	
	% \begin{loesung}
		% (Das \enquote{möglichst kurze} soll nur dazu da sein, dass keiner seitenlange Programme abgibt. Falls jemand Lösungen abgibt, die länger sind, als die Musterlösung, aber dennoch vernünftig, so sollten die schon normal bewertet werden.)
		% \begin{enumerate}[i)]
		% \item\begin{algorithmic}[1]
			% \linecomment{$x_0 = (x_1 \vee x_2)$}
			% \State $x_0 \defeq x_1 + x_2$
		% \end{algorithmic}				
		% \item\begin{algorithmic}[1]
			% \linecomment{$x_0 = \neg x_1$}
			% \State $x_0 \defeq 1$
			% \LoopX{$x_1$}
				% \State $x_0 \defeq 0$
			% \EndLoopX
		% \end{algorithmic}
		% \item\begin{algorithmic}[1]
			% \linecomment{$x_0 = (x_1 ~\textsc{Nand}~ x_2)$}
			% \State $x_0 \defeq 1$
			% \State $x_3 \defeq x_2 \cdot x_1$
			% \LoopX{$x_3$}
				% \State $x_0 \defeq 0$
			% \EndLoopX
		% \end{algorithmic}
		% \item\begin{algorithmic}[1]
			% \linecomment{$x_0 = (x_1 \Rightarrow x_2)$}
			% \State $x_0 \defeq 1$
			% \LoopX{$x_1$}
				% \State $x_0 \defeq 0$
				% \LoopX{$x_2$}
					% \State $x_0 \defeq 1$
				% \EndLoopX
			% \EndLoopX
		% \end{algorithmic}
		% \end{enumerate}
	% \end{loesung}
	% \pagebreak
	
	% \begin{aufgabe}{6}
		% Die Ackermannfunktion $A: \setN \times \setN \rightarrow \setN$ ist induktiv wie folgt definiert:
		% \begin{align*}
			% A(0, y) &= y + 1 \\
			% A(x, 0) &= A(x - 1, 1) \\
			% A(x + 1, y + 1) &= A(x, A(x+1, y))
		% \end{align*}
		
		% \noindent Zeigen Sie die folgenden drei Aussagen:
		% \begin{enumerate}[\quad i)]
			% \item $A(1, y) = y + 2$
			% \item $A(2, y) = 2y + 3$
			% \item $A(3, y) = 2^{y + 3} - 3$
		% \end{enumerate}
	% \end{aufgabe}
	
	% \begin{loesung}
		% Alle drei Aussagen lassen sich induktiv zeigen.
		% \begin{enumerate}[\quad i)]
			% \item Induktionsanfang: \underline{$y = 0$}
			% \begin{align*}
				% A(1, 0) &= A(0, 1) &\text{ (Def. von A)} \\
				% &= 1 + 1 &\text{ (Def. von A)} \\
				% &= 2 \\
				% &= 0 + 2 \\
				% &= y + 2 &(y=0)
			% \end{align*}
			% Induktionsschritt: \underline{$y \rightarrow y + 1$}
			% \begin{align*}
				% A(1, y + 1) &= A(0, A(1, y)) &\text{ (Def. von A)}\\
				% &= A(0, y + 2) &\text{ (IA)}\\
				% &= y + 2 + 1 &\text{ (Def. von A)}\\
				% &= (y + 1) + 2
			% \end{align*}
			% \item Induktionsanfang: \underline{$y = 0$}
			% \begin{align*}
				% A(2, 0) &= A(1, 1) &\text{ (Def. von A)}\\
				% &= A(0, A(1,0)) &\text{ (Def. von A)}\\
				% &= A(1,0) + 1 &\text{ (Def. von A)}\\
				% &= A(0,1) + 1 &\text{ (Def. von A)}\\
				% &= 1 + 1 + 1  &\text{ (Def. von A)}\\
				% &= 3 \\
				% &= 2 \cdot 0 + 3 \\
				% &= 2 \cdot y + 3 &(y=0)\\
			% \end{align*}
			% Induktionsschritt: \underline{$y \rightarrow y + 1$}
			% \begin{align*}
				% A(2, y + 1) &= A(1, A(2, y)) &\text{ (Def. von A)}\\
				% &= A(2, y) + 2 &\text{ (i)}\\
				% &= 2y + 3 + 2 &\text{ (IV)}\\
				% &= 2y + 2 + 3 \\
				% &= 2 \cdot (y + 1) + 3
			% \end{align*}
			% \item Induktionsanfang: \underline{$y = 0$}
			% \begin{align*}
				% A(3, 0) &= A(2, 1) &\text{ (Def. von A)}\\
				% &= 2 \cdot 1 + 3 &\text{ (ii)}\\
				% &= 5 \\
				% &= 8 - 3 \\
				% &= 2^3 - 3 \\
				% &= 2^{2 \cdot 0 + 3} -3 \\
				% &= 2^{2 \cdot y + 3} -3 &(y=0)
			% \end{align*}
			% Induktionsschritt: \underline{$y \rightarrow y + 1$}
			% \begin{align*}
				% A(3, y + 1) &= A(2, A(3, y)) &\text{ (Def. von A)}\\
				% &= 2 \cdot A(3, y) + 3 &\text{ (ii)}\\
				% &= 2 \cdot (2^{y+3} - 3) + 3 &\text{ (IV)}\\
				% &= 2^{y + 4} - 3 \\
				% &= 2^{(y + 1) + 3} - 3
			% \end{align*}
		% \end{enumerate}
	% \end{loesung}
	
	% \begin{aufgabe}{5}
		% Sei $h$ eine totale und surjektive Funktion, die als Bildbereich die \emph{komplette} Menge aller einstelligen berechenbaren Zahlenfunktionen hat, also:
		% \begin{gather*}
			% h \colon \setN \rightarrow \{f \colon \setN \rightarrow \setN \colon f~\text{ist eine totale berechenbare Funktion}\}
		% \end{gather*}
		% Das heißt, für jedes $n \in \setN$ ist $h(n)$ eine Funktion von $\setN$ nach $\setN$ und $h(n)(x)$ ist der Wert der Funktion $h(n)$ an Stelle $x$.
		
		% Zeigen Sie, dass die folgende Funktion nicht berechenbar ist:
		% \begin{gather*}
			% g \colon \setN^2 \rightarrow \setN,~g(n,x) = h(n)(x)
		% \end{gather*}

		% \Hinweis{Konstruieren Sie aus $g$ eine einstellige totale Funktion, welche im Bildbereich von $h$ liegen würde und zeigen Sie mithilfe von Diagonalisierung (ähnlich zu Kapitel 5 in den Folien) einen Widerspruch auf.}
	% \end{aufgabe}
	
	% \begin{loesung}
		% Angenommen $g$ sei berechenbar. Dann wäre $g' \colon \setN \rightarrow \setN$ mit $g'(x) = g(x,x) + 1 (= h(x)(x)+1)$ auch berechenbar. Weiter gilt: $g'$ ist total (da sowohl $h$ als auch $h(x)$ total sind). Daraus folgt, dass $g'$ im Bildbereich von $h$ liegt -- es gibt also ein $z \in \setN$ mit $h(z) = g'$. Insbesondere gilt dann $g'(z) = h(z)(z) = g(z,z)$. Nach Definition von $g'$ gilt allerdings $g'(z) = g(z,z) + 1 \lightning$.
	% \end{loesung}
	\begin{definition2}
		Seien $L_1, L_2 \subseteq \Sigma^{*}$ zwei Sprachen. Wir definieren die \emph{Konkatenation von Sprachen} als $L_1 \circ L_2 \defeq \{w_1 \cdot w_2 \colon w_1 \in L_1 \wedge w_2 \in L_2\}$.
	\end{definition2}
	
	\begin{aufgabe}{3}
		Seien $L_1, L_2 \subseteq \Sigma^{*}$ entscheidbare Sprachen. Zeigen Sie, dass $L_1 \circ L_2$ ebenfalls entscheidbar ist.
	\end{aufgabe}
	
	\begin{loesung}		
		$L_1 \circ L_2$ entscheidbar, gdw. $\chi_{L_1 \circ L_2}$ berechenbar. Sei $w = \alpha_1 \cdots \alpha_n$ mit $\alpha_1, \dots, \alpha_n \in \Sigma$. Es gilt:
		\begin{align*}
			w \in L_1 \circ L_2 &\equiv \varepsilon \in L_1 \wedge \alpha_1 \cdots \alpha_n \in L_2\\
			&\vee \alpha_1 \in L_1 \wedge \alpha_2 \cdots \alpha_n \in L_2\\
			&\vee \dots\\
			&\vee \alpha_1 \cdots \alpha_{n-1} \in L_1 \wedge \alpha_n \in L_2\\
			&\vee \alpha_1 \cdots \alpha_n \in L_1 \wedge \varepsilon \in L_2\\
			&\equiv \chi_{L_1}(\varepsilon) = 1 \wedge \chi_{L_2}(\alpha_1 \cdots \alpha_n) = 1\\
			&\vee \dots\\
			&\vee \chi_{L_1}(\alpha_1 \cdots \alpha_n) = 1 \wedge \chi_{L_2}(\varepsilon) = 1\\
			&\equiv \chi_{L_1}(\varepsilon) \cdot \chi_{L_2}(\alpha_1 \cdots \alpha_n) + \dots + \chi_{L_1}(\alpha_1 \cdots \alpha_n) \cdot \chi_{L_2}(\varepsilon) \geq 1
		\end{align*}
		Daraus folgt: $\chi_{L_1 \circ L_2}$  ist berechenbar, da es eine Verknüpfung berechenbarer Funktionen ist.
		
		Alternativ kann man auch einen Algorithmus angeben der die Sprache entscheidet. Am einfachsten läuft man mit einer Schleife über die Eingabe $w$ und teilt das Wort in zwei Teilwörter auf. Dann kann man in jedem Schleifendurchlauf testen, ob das linke Teilwort in $L_1$ und das rechte Teilwort in $L_2$ liegt.
	\end{loesung}
	
	\begin{aufgabe}{4}
		Seien $A, \bar{A} \subseteq \sigStar$ semi-entscheidbare Sprachen (wobei $\bar{A} = \sigStar \setminus A$ das Komplement von $A$ bezeichnet).
		
		Zeigen Sie: $A$ ist entscheidbar.
		
		\Hinweis{Für ein beliebiges $w \in \sigStar$ hält mindestens eine der beiden Turingmaschinen, die die jeweilige charakteristische Funktion berechnen. Überlegen Sie sich, wie Sie diese beiden Turingmaschinen \enquote{parallel} laufen lassen können.}
	\end{aufgabe}
	
	\begin{loesung}
		Die Idee ist, wie im Hinweis steht, beide Maschinen gleichzeitig laufen zu lassen. D.\,h.\ man führt jeweils einen Rechenschritt der einen Maschine und dann einen Rechenschritt der anderen Maschine durch. Da mindestens eine der beiden Maschinen hält (für ein $w \in \sigStar$ gilt entweder $w \in A$ oder $w \notin A \equiv w \in \bar{A}$), erkennt man, ob das Wort in der Menge oder im Komplement ist. Etwas genauer: Sei $M_1$ die TM, die $\chi'_{A}$ berechnet und $M_2$ die TM, die $\chi'_{\bar{A}}$ berechnet. Wie konstruieren eine neue TM $M$ wie folgt:
		\begin{itemize}
			\item[] (Eingabe: $w \in \sigStar$ beliebig)
			\item Simuliere \emph{einen} Rechenschritt (bzw.\ Zustandsübergang) von $M_1$.
			\item Simuliere \emph{einen} Rechenschritt (bzw.\ Zustandsübergang) von $M_2$.
			% \item[] (Intuitiv kann man sich hier eine TM mit zwei Bändern vorstellen, die auf dem oberen Band $M_1$ und auf dem unteren Band $M_2$ simuliert.)
			\item Wiederhole die (abwechselnd ausgeführten) Rechenschritte der beiden TMs bis eine der beiden Maschinen in den Endzustand übergeht.
			\item Falls $M_1$ hält, so wechsle in den Endzustand und gibt das Ergebnis der Simulation von $M_1$ aus.
			\item Falls $M_2$ hält, so wechsle in den Endzustand und gibt das Ergebnis der Simulation von $M_2$ aus.
		\end{itemize}
		Für die (paralelle) Simulation beider Maschinen kann man sich bspw.\ eine Mehrband-TM mit zwei Bändern vorstellen. Das erste Band simuliert $M_1$ und das zweite Band $M_2$. Falls $A$ semi-entscheidbar aber \emph{nicht} entscheidbar ist, hält \emph{genau} eine der beiden TMs $M_1$ und $M_2$. Dann gilt $w \in A$, falls $M_1$ hält und $w \in \bar{A}$, falls $M_2$ hält.
	\end{loesung}
	
	\begin{aufgabe}{4}
		Seien $A,B \subseteq \setN^k$ semi-entscheidbare Mengen. Welche der Mengen $A \cup B$, $A \cap B$, $\bar{A}$ und $A \setminus B$ sind ebenfalls semi-entscheidbar? Und welche nicht? Begründen Sie Ihre Antworten.
	\end{aufgabe}
	
	\begin{loesung}
		$A \cup B$ und $A \cap B$ sind semi-entscheidbar: $A$ ist semi-entscheidbar $\Rightarrow$ $A$ ist rekursiv aufzählbar $\Rightarrow$ $\exists f_A : \setN \rightarrow A$, $A = \{f(1), f(2), f(3), ...\}$. (Analog existiert $f_B$ für $B$.) Folgendes Programm ist ein Semi-Entscheidungsverfahren für $A \cup B$:
		\begin{algorithmic}[1]
			\Function{$\chi_{A \cup B}$}{$x$}
				\State $i \leftarrow 1$
				\State $inA, inB \gets \False$
				\While{$\neg (inA \vee inB)$}\label{line:bedingung}
					\If{$f_A(i) = x$}
						\State $inA \gets \True$
					\EndIf
					\If{$f_B(i) = x$}
						\State $inB \gets \True$
					\EndIf
					\State $i \gets i+1$
				\EndWhile
				\State \Return{$1$}
			\EndFunction
		\end{algorithmic}
		Wenn man die Bedingung in Zeile \ref{line:bedingung} zu \enquote{$\neg (inA \wedge inB)$} ändert, ist der Algorithmus ein Semi-Entscheidungsverfahren für $A \cap B$. Wichtig bei der Vereinigung ist, dass man die beiden Mengen $A$ und $B$ \enquote{parallel} testet. Wenn man sie nacheinander testet, dann hat man ein Problem, falls $x \notin A$ aber $x \in B$; Da $A$ semi-entscheidbar, läuft der Algorithmus eventuell in eine Endlosschleife und erkennt nicht, dass $x$ in $B$ und somit auch in der Vereinigung ist. 
		
		$\overbar{A}$ ist im Allgemeinen nicht semi-entscheidbar: Sei $A$ semi-entscheidbar aber \emph{nicht entscheidbar}. Angenommen $\overbar{A}$ wäre semi-entscheidbar. Da $A$ nach Voraussetzung semi-entscheidbar ist, wäre $A$ entscheidbar (Vorige Aufgabe bzw. Satz 8.2). Dies ist ein Widerspruch.
		
		$A \setminus B$ ist ebenfalls nicht semi-entscheidbar (da das Komplement nicht semi-entscheidbar ist). Wäre $A \setminus B$ semi-entscheidbar, dann wäre insbesondere auch $\setN^k \setminus A = \overbar{A}$ semi-entscheidbar, was ein Widerspruch zum vorigen Punkt darstellt.
	\end{loesung}
	
	% \begin{aufgabe}{4}
		% Zeigen Sie, dass die folgenden beiden Aussagen äquivalent sind:
		% \begin{enumerate}[\quad (i)]
			% \item $A \subseteq \setN$ ist eine unendliche, entscheidbare Menge.
			% \item Es gibt eine \emph{streng monotone}, totale, berechenbare Funktion $g: \setN \rightarrow \setN$ mit $g(\setN) = A$
		% \end{enumerate}
	% \end{aufgabe}
	
	% \begin{loesung}
		% \underline{$\Rightarrow$}
		
		% Da $A$ entscheidbar ist $A$ rekursiv aufzählbar. Daraus folgt, dass ein $f \colon \setN \rightarrow A$ existiert mit $f(\setN) = A$. \textbf{Problem:} Dieses $f$ muss nicht streng monoton sein. Man kann nun entweder $f(\setN)$ \enquote{sortieren}, damit Monotonie entsteht, oder man definiert direkt eine eigene Funktion die den Anforderungen genügt. Wir definieren also $g \colon \setN \rightarrow A$ induktiv:
		% \begin{align*}
			% g(1) &= min(A)\\
			% g(n+1) &= min(A \setminus \{g(1), \ldots g(n)\})
		% \end{align*}
		
		% \begin{itemize}
			% \item $g$ ist streng monoton wegen $min()$:
				% \begin{align*}
					% g(i) &= min(A \setminus \{g(1), \ldots g(i-1)\})\\
					% &\Rightarrow \forall x \in A \setminus \{g(1), \ldots, g(i)\} \colon x > g(i)
				% \end{align*}
				% Und da $g(i+1) \in A \setminus \{g(1), \ldots, g(i)\}$ gilt $g(i+1) > g(i)$.
			% \item $g$ ist total da $A$ (abzählbar) unendlich
			% \item $g$ ist berechenbar, da $A$ entscheidbar und eine Art Sortierung vorliegt ($A \subseteq \setN$). Außerdem ist für jedes endliche $B$ dann auch $A \setminus B$ entscheidbar. Der folgende Algorithmus hält (da $(A \setminus B) \cap \setN \neq \emptyset$) und liefert das kleinste Element in $A \setminus B$ zurück:
				% \begin{algorithmic}[1]
					% \State $i \leftarrow 1$
					% \While{$i \notin A \setminus B$} \Comment{$A \setminus B = A \cap \overbar{B}$ ist entscheidbar}
						% \State $i \gets i + 1$
					% \EndWhile
					% \State \Return{$i$} \Comment{Da für alle $i' < i$ gilt $i' \notin A$ ist $i$ Minimum in $A$}
				% \end{algorithmic}
			% \item Grob argumentiert gilt $g(\setN) = A$ da unsere Funktion $A$ \enquote{sortiert} und somit jedem $x \in A$ eine natürliche Zahl zuweist. Etwas genauer: $g(\setN) \subseteq A$ nach Definition von $g$. Bleibt also noch $g(\setN) \supseteq A$ zu zeigen. Sei $a \in A$. Definieren $A_{k}, A_{g} \subseteq A$ wie folgt: $A_{k} = \{x \in A \colon x < a\}$ und $A_{g} = \{x \in A \colon x > a\}$. Dann ist $A = A_{k} \cup \{a\} \cup A_{g}$. Daraus folgt, dass $a = g(|A_{k}|+1)$ und somit $a \in g(\setN)$.
		% \end{itemize}
		% \noindent\underline{$\Leftarrow$}
		
		% O.\,b.\,d.\,A. sei $g$ monoton steigend.
		% \begin{itemize}
			% \item $A$ ist entscheidbar. Folgender Algorithmus berechnet \enquote{$x \stackrel{?}{\in} A$}:
				% \begin{algorithmic}[1]
					% \State $i \leftarrow 1$
					% \While{$g(i) < x$} \Comment{Da $g$ streng monoton steigend hält die Schleife}
						% \State $i \leftarrow i+1$
					% \EndWhile
					% \If{$g(i) = x$}
						% \State \Return{\True}
					% \Else
						% \State \Return{\False}
					% \EndIf
				% \end{algorithmic}
				
			% \item $A$ ist unendlich. $g$ ist streng monoton und somit injektiv. Außerdem ist $g$ total. Also wird jedem Element in $\setN$ ein eindeutiger Wert aus $A$ zugewiesen.
		% \end{itemize}
	% \end{loesung}
	
	\begin{aufgabe}{2 + 2}
		Zeigen Sie die folgenden Aussagen:
		\begin{enumerate}[\quad a)]
			\item $\setP \defeq \{p \in \setN \colon p ~\text{ist eine Primzahl.}\}$ ist entscheidbar.
			% \item $\{(x,y,z) \in \setN^3 \colon (\exists n \in \setN) ~ x^n + y^n = z^n\}$ ist semi-entscheidbar.
			\item $\{n \in \setN \colon \text{Es gibt eine Primzahl}~p\text{, sodass}~p+1,\dots,p+n~\text{keine Primzahlen sind.}\}$ ist semi-entscheidbar.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item $\{p \in \setN \colon p ~\text{ist eine Primzahl.}\}$ kann man mit folgendem Algorithmus entscheiden:
				\begin{algorithmic}[1]
					\linecomment{Eingabe: $p \in \setN$}
					\If{$p \leq 1$}
						\State \Return{\False}
					\EndIf
					\State $i \leftarrow 2$
					\While{$i < p$} \Comment{Als Bedingung reicht auch $i \cdot i \leq p$}
						\If{$p \equiv 0~(mod~i)$} \Comment{$i$ teilt $p$}
							\State \Return{\False}
						\EndIf
						\State $i \gets i+1$
					\EndWhile
					\State \Return{\True}
				\end{algorithmic}
				Der Algorithmus testet alle potentiellen Teiler und gibt \False zurück, wenn ein Teiler gefunden wird. Wenn kein Teiler (in $\{2, \dots, p-1\}$) gefunden wird, dann ist die Zahl prim und der Algorithmus liefert \True zurück.
			% \item $\{(x,y,z) \in \setN^3 \colon \exists n \in \setN ~ x^n + y^n = z^n\}$ lässt sich mit folgendem Algorithmus \enquote{semi-entscheiden}:
				% \begin{algorithmic}[1]
					% \State $i \leftarrow 1$
					% \While{$x^i + y^i \neq z^i$}
						% \State $i \gets i+1$
					% \EndWhile
					% \State \Return{\True}
				% \end{algorithmic}
				% Der Algorithmus testet für alle natürlichen Zahlen, ob die Gleichung erfüllt ist. Wenn er eine Zahl findet, für die die Gleichung gilt, liefert er \True zurück, sonst rechnet er weiter. Da Addition und Potenzierung \textsc{While}-berechenbar sind, ist auch die Schleifenbedingung \textsc{While}-berechenbar und damit ist der Algorithmus ein Semi-Entscheidungsverfahren. Prinzipiell ist die Menge sogar entscheidbar, da man nur $n=1$ und $n=2$ testen muss. Für alle $n>2$ ist die Gleichung immer falsch (Großer Fermat'scher Satz).
			\item Ein einfaches Semi-Entscheidungsverfahren ist das folgende:
			\begin{algorithmic}[1]
				\ForEach{$p \in \setP$}\Comment{$\setP$ ist die Menge aller Primzahlen}
					\If{$\{p+1, \dots, p+n\} \cap \setP = \emptyset$}
						\State \Return{\True}
					\EndIf
				\EndFor
			\end{algorithmic}
			Der Algorithmus testet zu jeder Primzahl $p$ ob $p+1$ bis $p+n$ auch Primzahlen sind. Vielleicht ist die Menge sogar entscheidbar, da es zu jeder Zahl $n \in \setN$ mit $\{n!+2, \dots, n!+n\}$ eine Menge von $n-1$ aufeinanderfolgenden Zahlen gibt, die nicht prim sind. Der Algorithmus könnte in dem Fall also immer \True zurückgeben, da man beliebig große Lücken zwischen Primzahlen generieren kann. (Hier müsste man zahlentheoretisch etwas genauer argumentieren, oder die ursprüngliche Menge anders formulieren, denn $n! + 1$ ist nicht immer eine Primzahl. Allerdings wird vermutet, dass es unendlich viele Primzahlen dieser Form gibt.)
		\end{enumerate}
	\end{loesung}
\label{lastpage}
\end{document}