\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}
\usepackage{linearA}
\usepackage{emoji}
\setemojifont{Segoe UI Emoji}

% 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[dvipsnames]{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}}
\newcommand{\classL}{\textsf{L}\xspace}
\newcommand{\classNL}{\textsf{NL}\xspace}
\newcommand{\classP}{\textsf{P}\xspace}
\newcommand{\classNP}{\textsf{NP}\xspace}
\newcommand{\classPSPACE}{\textsf{PSPACE}\xspace}
\newcommand{\classNPSPACE}{\textsf{NPSPACE}\xspace}
\newcommand{\classEXP}{\textsf{EXP}\xspace}

% Regeln für TM -> MPCP
\newcommand{\ruleSa}{\textcolor{Aquamarine}{S1}}
\newcommand{\ruleKa}{\textcolor{Fuchsia}{K1}}
\newcommand{\ruleKb}{\textcolor{Apricot}{K2}}
\newcommand{\ruleKc}{\textcolor{ForestGreen}{K3}}
\newcommand{\ruleKd}{\textcolor{Magenta}{K4}}
\newcommand{\ruleUa}{\textcolor{SeaGreen}{U1}}
\newcommand{\ruleUb}{\textcolor{Sepia}{U2}}
\newcommand{\ruleUc}{\textcolor{red}{U3}}
\newcommand{\ruleUd}{\textcolor{NavyBlue}{U4}}
\newcommand{\ruleLa}{\textcolor{Black}{L1}}
\newcommand{\ruleLb}{\textcolor{BlueViolet}{L2}}
\newcommand{\ruleLc}{\textcolor{Lavender}{L3}}
\newcommand{\ruleLd}{\textcolor{LimeGreen}{L4}}
\newcommand{\ruleLe}{\textcolor{RawSienna}{L5}}
\newcommand{\ruleLf}{\textcolor{CadetBlue}{L6}}
\newcommand{\ruleAa}{\textcolor{BrickRed}{A1}}

\newcommand{\ruleSaTop}{\textcolor{Aquamarine}{\#}}
\newcommand{\ruleKaTop}{\textcolor{Fuchsia}{0}}
\newcommand{\ruleKbTop}{\textcolor{Apricot}{1}}
\newcommand{\ruleKcTop}{\textcolor{ForestGreen}{\square}}
\newcommand{\ruleKdTop}{\textcolor{Magenta}{\#}}
\newcommand{\ruleUaTop}{\textcolor{SeaGreen}{z_0 0}}
\newcommand{\ruleUbTop}{\textcolor{Sepia}{z_0 1}}
\newcommand{\ruleUcTop}{\textcolor{red}{z_0 \square}}
\newcommand{\ruleUdTop}{\textcolor{NavyBlue}{z_0 \#}}
\newcommand{\ruleLaTop}{\textcolor{Black}{0 z_f}}
\newcommand{\ruleLbTop}{\textcolor{BlueViolet}{1 z_f}}
\newcommand{\ruleLcTop}{\textcolor{Lavender}{\square z_f}}
\newcommand{\ruleLdTop}{\textcolor{LimeGreen}{z_f 0}}
\newcommand{\ruleLeTop}{\textcolor{RawSienna}{z_f 1}}
\newcommand{\ruleLfTop}{\textcolor{CadetBlue}{z_f \square}}
\newcommand{\ruleAaTop}{\textcolor{BrickRed}{z_f \# \#}}

\newcommand{\ruleSaBottom}{\textcolor{Aquamarine}{\# \square z_0 1 0 1 \square \#}}
\newcommand{\ruleKaBottom}{\textcolor{Fuchsia}{0}}
\newcommand{\ruleKbBottom}{\textcolor{Apricot}{1}}
\newcommand{\ruleKcBottom}{\textcolor{ForestGreen}{\square}}
\newcommand{\ruleKdBottom}{\textcolor{Magenta}{\#}}
\newcommand{\ruleUaBottom}{\textcolor{SeaGreen}{0 z_0}}
\newcommand{\ruleUbBottom}{\textcolor{Sepia}{1 z_0}}
\newcommand{\ruleUcBottom}{\textcolor{red}{z_f 0}}
\newcommand{\ruleUdBottom}{\textcolor{NavyBlue}{z_f 0 \#}}
\newcommand{\ruleLaBottom}{\textcolor{Black}{z_f}}
\newcommand{\ruleLbBottom}{\textcolor{BlueViolet}{z_f}}
\newcommand{\ruleLcBottom}{\textcolor{Lavender}{z_f}}
\newcommand{\ruleLdBottom}{\textcolor{LimeGreen}{z_f}}
\newcommand{\ruleLeBottom}{\textcolor{RawSienna}{z_f}}
\newcommand{\ruleLfBottom}{\textcolor{CadetBlue}{z_f}}
\newcommand{\ruleAaBottom}{\textcolor{BrickRed}{\#}}

% 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{7}
\newcommand\Abgabe{14.\,Januar 2022 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}{5}
		% Finden Sie Beispiele für Mengen $A,B,C,D,E \subseteq \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast}$ mit $A \subset B \subset C \subset D \subset E$, so dass $A$, $C$ und $E$ entscheidbar sind, $B$ und $D$ jedoch nicht. (Begründen Sie Ihre Antwort.)
	% \end{aufgabe}
	
	% \begin{loesung}
		% Hier gibt es viele Lösungen. Zwei ähnliche Beispiele:
		% \begin{itemize}
			% \item Setze $A = \emptyset$. Eine TM, die immer \textsc{Falsch} ausgibt entscheidet die leere Menge. Die leere Menge ist außerdem Teilmenge jeder Menge.
			% \item Setze $B = H$ (also das Halteproblem). Ist nach VL nicht entscheidbar.
			% \item Setze $C = \{\text{\enquote{Menge aller Turingmaschinen}}\}$. Ist entscheidbar, da man nur die \enquote{Syntax} überprüfen muss. Da jedes Element \enquote{im Halteproblem} eine TM ist, ist die Menge aller Turingmaschinen eine Obermenge zu $B$.
			% \item Setze $D = C \cup PCP$. Das Post'sche Korrespondenzproblem ist nicht entscheidbar, also auch nicht die Menge $D$. Außerdem ist nach Konstruktion $D$ eine Obermenge zu $C$.
			% \item Setze $E = \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast}$. Analog zu $\emptyset$ entscheidet eine TM, die immer \textsc{Wahr} ausgibt, das gesamte Universum. Nach Definition ist $\left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast}$ auch eine Obermenge zu $D$.
		% \end{itemize}
		% Beim folgenden Beispiel bestehen Mengen $B$ und $C$ aus Tupeln um die Teilmengenbeziehung zu ermöglichen. Die zweite Komponente wird allerdings \enquote{ignoriert}.
		% \begin{itemize}
			% \item Setze $A = \emptyset$. (siehe oben)
			% \item Setze $B = \{(u,u) \in \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast} \times \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast} \colon M_u(u) \text{ hält}\}$. Halteproblem ist nicht entscheidbar.
			% \item Setze $C = \{(u,u) \in \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast} \times \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast} \colon M_u \text{ ist eine TM}\}$. Wie oben. \enquote{Syntax} überprüfen ist entscheidbar und jede haltende TM ist eine TM, also gilt $B \subset C$.
			% \item Setze $D = \{(u,v) \in \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast} \times \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast} \colon M_u = M_v\}$. Das Äquivalenzproblem für Turingmaschinen ist nicht entscheidbar. Da allerdings für jede TM $M_u$ gilt: $M_u = M_u$, gilt $C \subset D$.
			% \item Setze $E = \left\{\text{\emoji{santa-claus}},\text{\emoji{snowflake}}\right\}^{\ast}$. (siehe oben)
		% \end{itemize}
	% \end{loesung}
	
	% \begin{aufgabe}{5}
		% Sei $A \defeq \left\{\text{\emoji{christmas-tree}}^p\text{\emoji{wrapped-gift}}^q \colon p,q \in \setN ~\text{mit}~ p \neq q\right\}$. Zeigen Sie: Es gibt ein $c \in \setN$, sodass $A \in TIME(n+c)$
	% \end{aufgabe}
	
	% \begin{loesung}
		% Für $c \in \setN$ gilt $TIME(n+c) = \{A \subseteq \Sigma^{*} \colon \text{Es gibt eine Turingmaschine}~ M ~\text{mit}~ L(M) = A ~\text{und}~ time_M(w) \leq |w| + c\}$. Das heißt, wir müssen eine Mehrband-TM finden, die zu einem beliebigen Wort (der Länge $n$) in $n+c$ Schritten entscheiden kann, ob es von der Form $\text{\emoji{christmas-tree}}^p\text{\emoji{wrapped-gift}}^q$ (mit $p \neq q$) ist. Eine solche TM (mit zwei Bändern) arbeitet beispielsweise folgendermaßen:
		% \begin{enumerate}[\quad 1.]
			% \item Laufe über die Eingabe auf dem ersten Arbeitsband und schreibe für jedes \emoji{christmas-tree} eine Markierung auf das zweite Arbeitsband.
			% \item Falls ein \emoji{wrapped-gift} gefunden wird, dann lösche eine Markierung auf dem zweiten Arbeitsband. Laufe nun weiter auf dem ersten Band und lösche für jedes gefundene \emoji{wrapped-gift} eine Markierung auf dem zweiten Arbeitsband. Lehne ab, falls auf dem ersten Band erneut ein \emoji{wrapped-gift} gefunden wird, sonst akzeptiere. (In dem Fall gilt $p < q$.)
			% \item Falls auf dem ersten Band das Ende erreicht wird, prüfe, ob das zweite Arbeitsband leer ist. Wenn ja, lehne ab (in dem Fall gilt $p = q$), sonst akzeptiere (in dem Fall gilt $p > q$).
		% \end{enumerate}
		% Diese TM braucht ${|\text{\emoji{christmas-tree}}^p\text{\emoji{wrapped-gift}}^q|} \eqdef n$ viele Schritte um ans Ende auf dem ersten Band zu gelangen und einen weiteren Schritt um zu prüfen, ob die Eingabe zu Ende ist und das zweite Arbeitsband leer ist. Das heißt, $A$ lässt sich in $n+1 \defeq n+c$ Schritten entscheiden und die Aussage gilt.
	% \end{loesung}
	
	% \begin{aufgabe}{5}
		% Zeigen Sie: $\left\{w \cdot \text{\emoji{snowman}} \cdot w \colon w \in \left\{\text{\emoji{christmas-tree}},\text{\emoji{wrapped-gift}}\right\}^{\ast}\right\}$ ist in \classP.
	% \end{aufgabe}
	
	% \begin{loesung}
		% Hierbei müssen wir eine TM konstruieren, die (deterministisch) in Polynomzeit entscheidet, ob ein Wort von der Form $w \cdot \text{\emoji{snowman}} \cdot w$ ist, also ob das Wort aus zwei gleichen Wortteilen besteht, die durch das Trennsymbol \emoji{snowman} getrennt sind. Folgende (grobe) Arbeitsweise beschreibt eine solche TM:
		% \begin{itemize}
			% \item Markiere den linken und den rechten Rand mit einem eigenen Symbol, bspw.\ \emoji{santa-claus}.
			% \item Lies das linkeste (nicht-Rand-)Symbol ein und speichere dieses (Zustand oder zweites Arbeitsband).
			% \item Überschreibe das Feld mit einem $\square$ und gehe danach zum ersten Symbol (ungleich $\square$) nach dem Trennsymbol.
			% \item Überprüfe, ob dieses Symbol gleich dem gespeicherten ist. Wenn nein: Lehne ab. Wenn ja: Überschreibe das Feld mit einem $\square$ und gehe wieder zum linkesten Symbol (ungleich $\square$ bzw.\ \emoji{santa-claus}).
			% \item Wiederhole den Vorgang, bis das linkteste Symbol das Trennzeichen \emoji{snowman} ist. Akzeptiere, falls das Band rechts des Trennsymbols auch leer ist, sonst lehne ab.
		% \end{itemize}
		
		% Der erste Schritt (markieren der Ränder) hilft dabei, zu testen ob das Band rechts des Trennsymbols \emoji{snowman} leer ist (d.\,h.\ bei der beschriebenen Arbeitsweise würde auch nur der rechte Rand reichen). Ohne diese Markierung würde die TM sonst nicht wissen, wie weit sie nach rechts laufen muss, um ein potentielles Zeichen aus $\left\{\text{\emoji{christmas-tree}},\text{\emoji{wrapped-gift}}\right\}$ zu finden. Statt den Randsymbolen kann man sich auch andere Möglichkeiten überlegen, wie man erkennt, wo das Wort ursprünglich zu Ende war (spezielle Blanksymbole, mitzählen der Wortlänge, beim Überprüfen des rechten Symbols testen, ob es das letzte Zeichen des Wortes ist, \dots).
		
		% Um die Ränder des Wortes zu markieren müssen wir zweimal über die gesamte Eingabe laufen (einmal für den rechten Rand und einmal, um den Kopf wieder auf das erste Symbol in $w$ zu bewegen). Bei den restlichen Schritten (der \enquote{Hauptschleife}) laufen wir immer über die \enquote{halbe} Eingabe (Länge $|w|$) um zwei Zeichen zu vergleichen. Es werden insgesamt $|w|$ viele Vergleiche durchgeführt. Um zu testen, ob der rechte Teil der Eingabe leer ist, muss die TM potentiell nochmal über die halbe Eingabe laufen. Für ein Wort der Länge $n$ ergibt sich dann eine Laufzeit von $2 \cdot n + {|w|}^2 + |w| = {\left(\frac{1}{2} \cdot n\right)}^{2} + \frac{5}{2} \cdot n \in \mathcal{O}(n^2)$ gilt, haben wir eine in Polynomzeit arbeitende TM konstruiert.
	% \end{loesung}
	
	\begin{aufgabe}{6 + 5}
		Gegeben sei eine Turingmaschine $M = (\{z_0, z_f\}, \{0,1\}, \{0,1,\square\}, \delta, z_0, \square, \{z_f\})$ wobei $\delta$ wie folgt definiert ist:
		\begin{center}
		\begin{tabular}[c]{r | c c c}
			$\delta(z,w)$ & 0 & 1 & $\square$ \\ \hline
			$z_0$ & $(z_0, 0, R)$ & $(z_0, 1, R)$ & $(z_f, 0, N)$
		\end{tabular}
		\end{center}
		Mit anderen Worten: $M$ hängt ans Ende der Eingabe eine einzelne $0$. Sei weiter $w \in \binStar$ das Wort, das diese Turingmaschine kodiert (also $M = M_w$).
		\begin{itemize}
			\item Geben Sie die Instanz des modifizierten Post'schen Korrespondenzproblems (\emph{MPCP}) an, die sich gemäß der Reduktion $K \leq MPCP$ (Lemma 8.4, Seite 43 im Skript) aus dieser Turingmaschine ergibt.
			\item Angenommen $w = 101$. Geben Sie die Folge der Tupel Ihrer MPCP-Instanz an, die der Arbeitsweise der obigen Turingmaschine angewendet auf $w$ entspricht.
		\end{itemize}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{itemize}
			\item Das Alphabet $\Sigma$ für die MPCP-Instanz ergibt sich aus dem Arbeitsalphabet $\Gamma$ und der Zustandsmenge $Z$ der gegebenen TM und einem Trennsymbol. Es gilt also $\Sigma = \Gamma \cup Z \cup \{\#\} = \{0, 1, \square, z_0, z_f, \#\}$. Sei für die folgenden Tupel $w \in \{0, 1\}^{\ast}$ ein beliebiger Binärstring. Die Konstruktion der Reduktion teilt die Tupel in fünf Gruppen auf:
				\begin{itemize}
					\item Startwortpaar: \textcolor{Aquamarine}{$(\#, \# \square z_0 w \square \#)$}
					\item Kopierregeln: \textcolor{Fuchsia}{$(0,0)$}, \textcolor{Apricot}{$(1,1)$}, \textcolor{ForestGreen}{$(\square,\square)$}, \textcolor{Magenta}{$(\#,\#)$}
					\item Überführungsregeln: \textcolor{SeaGreen}{$(z_0 0, 0 z_0)$}, \textcolor{Sepia}{$(z_0 1, 1 z_0)$}, \textcolor{red}{$(z_0 \square, z_f 0)$}, \textcolor{NavyBlue}{$(z_0 \#, z_f 0 \#)$}
					\item Löschregeln: \textcolor{Black}{$(0 z_f, z_f)$}, \textcolor{BlueViolet}{$(1 z_f, z_f)$}, \textcolor{Lavender}{$(\square z_f, z_f)$}, \textcolor{LimeGreen}{$(z_f 0, z_f)$}, \textcolor{RawSienna}{$(z_f 1, z_f)$}, \textcolor{CadetBlue}{$(z_f \square, z_f)$}
					\item Abschlussregeln: \textcolor{BrickRed}{$(z_f \# \#, \#)$}
				\end{itemize}
				Da wir MPCP betrachten, muss das Startwortpaar auch das mit dem kleinsten Index sein, damit wir erzwingen, dass eine gültige Lösung mit dem Paar $(\#, \# \square z_0 w \square \#)$ beginnt. Sonst wären bspw.\ die Kopierregeln gültige Lösungen. Die Reihenfolge der anderen Tupel ist allerdings egal.
			\item Seien die Tupel wie vorhin definiert und wie folgt nummeriert: Startwortpaar $\ruleSa$, Kopierregeln $\ruleKa$, $\ruleKb$, $\ruleKc$ und $\ruleKd$, Überführungsregeln, $\ruleUa$, $\ruleUb$, $\ruleUc$ und $\ruleUd$ Löschregeln $\ruleLa$, $\ruleLb$, $\ruleLc$, $\ruleLd$, $\ruleLe$ und $\ruleLf$ und Abschlussregel $\ruleAa$. Sei $w = 101$. Dann ergibt sich als Lösung die Indexfolge:
				\begin{gather*}
					\ruleSa, \ruleKc, \ruleUb, \ruleKa, \ruleKb, \ruleKc, \ruleKd, \ruleKc, \ruleKb, \ruleUa, \ruleKb, \ruleKc, \ruleKd, \ruleKc, \ruleKb, \\
					\ruleKa, \ruleUb, \ruleKc, \ruleKd, \ruleKc, \ruleKb, \ruleKa, \ruleKb, \ruleUc, \ruleKd, \ruleKc, \ruleKb, \ruleKa, \ruleLb, \ruleKa, \\
					\ruleKd, \ruleKc, \ruleKb, \ruleLa, \ruleKa, \ruleKd, \ruleKc, \ruleLb, \ruleKa, \ruleKd, \ruleKc, \ruleLd, \ruleKd, \ruleLc, \ruleKd, \ruleAa
				\end{gather*}
				
				Es wird mit $\ruleSa$ gestartet. Da es jeweils eine Löschregel für \enquote{Symbol-Zustand} und eine für \enquote{Zustand-Symbol} gibt, kann deren Reihenfolge (und damit auch die Reihenfolge der folgenden Tupel) variieren. Ansonsten gibt es keine Möglichkeiten, die Tupel anders zu wählen. Als Wörter aus dieser Tupelfolge ergeben sich dann:
		\end{itemize}
		{\small
		\begin{align*}
			&\ruleSaTop
			\ruleKcTop
			\ruleUbTop
			\ruleKaTop
			\ruleKbTop
			\ruleKcTop
			\ruleKdTop
			\ruleKcTop
			\ruleKbTop
			\ruleUaTop
			\ruleKbTop
			\ruleKcTop
			\ruleKdTop
			\ruleKcTop
			\ruleKbTop
			\ruleKaTop
			\ruleUbTop
			\ruleKcTop
			\ruleKdTop
			\ruleKcTop
			\ruleKbTop
			\ruleKaTop
			\ruleKbTop
			\ruleUcTop
			\ruleKdTop
			\ruleKcTop
			\ruleKbTop
			\ruleKaTop
			\ruleLbTop
			\ruleKaTop
			\ruleKdTop
			\ruleKcTop
			\ruleKbTop
			\ruleLaTop
			\ruleKaTop
			\ruleKdTop
			\ruleKcTop
			\ruleLbTop
			\ruleKaTop
			\ruleKdTop
			\ruleKcTop
			\ruleLdTop
			\ruleKdTop
			\ruleLcTop
			\ruleKdTop
			\ruleAaTop
			\\
			&\ruleSaBottom
			\ruleKcBottom
			\ruleUbBottom
			\ruleKaBottom
			\ruleKbBottom
			\ruleKcBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleKbBottom
			\ruleUaBottom
			\ruleKbBottom
			\ruleKcBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleKbBottom
			\ruleKaBottom
			\ruleUbBottom
			\ruleKcBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleKbBottom
			\ruleKaBottom
			\ruleKbBottom
			\ruleUcBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleKbBottom
			\ruleKaBottom
			\ruleLbBottom
			\ruleKaBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleKbBottom
			\ruleLaBottom
			\ruleKaBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleLbBottom
			\ruleKaBottom
			\ruleKdBottom
			\ruleKcBottom
			\ruleLdBottom
			\ruleKdBottom
			\ruleLcBottom
			\ruleKdBottom
			\ruleAaBottom
		\end{align*}}
	\end{loesung}
	
	\begin{aufgabe}{4}
		Finden Sie Beispiele für Mengen $A,B,C,D \subseteq \sigStar$ mit $A \subset B \subset C \subset D$, so dass $A$ und $C$ entscheidbar sind, $B$ und $D$ jedoch nicht. (Begründen Sie Ihre Antwort.)
	\end{aufgabe}
	
	\begin{loesung}
		Hier gibt es viele Lösungen. Zwei ähnliche Beispiele:
		\begin{itemize}
			\item Setze $A = \emptyset$. Eine TM, die immer \textsc{Falsch} ausgibt entscheidet die leere Menge. Die leere Menge ist außerdem Teilmenge jeder Menge.
			\item Setze $B = H$ (also das Halteproblem). Ist nach VL nicht entscheidbar.
			\item Setze $C = \{\text{\enquote{Menge aller Turingmaschinen}}\}$. Ist entscheidbar, da man nur die \enquote{Syntax} überprüfen muss. Da jedes Element \enquote{im Halteproblem} eine TM ist, ist die Menge aller Turingmaschinen eine Obermenge zu $B$.
			\item Setze $D = C \cup PCP$. Das Post'sche Korrespondenzproblem ist nicht entscheidbar, also auch nicht die Menge $D$. Außerdem ist nach Konstruktion $D$ eine Obermenge zu $C$.
		\end{itemize}
		Beim folgenden Beispiel bestehen Mengen $B$ und $C$ aus Tupeln um die Teilmengenbeziehung zu ermöglichen. Die zweite Komponente wird allerdings \enquote{ignoriert}.
		\begin{itemize}
			\item Setze $A = \emptyset$. (siehe oben)
			\item Setze $B = \{(u,u) \in \sigStar \times \sigStar \colon M_u(u) \text{ hält}\}$. Halteproblem ist nicht entscheidbar.
			\item Setze $C = \{(u,u) \in \sigStar \times \sigStar \colon M_u \text{ ist eine TM}\}$. Wie oben. \enquote{Syntax} überprüfen ist entscheidbar und jede haltende TM ist eine TM, also gilt $B \subset C$.
			\item Setze $D = \{(u,v) \in \sigStar \times \sigStar \colon M_u = M_v\}$. Das Äquivalenzproblem für Turingmaschinen ist nicht entscheidbar. Da allerdings für jede TM $M_u$ gilt: $M_u = M_u$, gilt $C \subset D$.
		\end{itemize}
	\end{loesung}
\label{lastpage}
\end{document}