\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{\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{2}
\newcommand\Abgabe{19.\,November 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}{2 + 3}
		\begin{enumerate}[\quad a)]
			\item Zeigen Sie, dass man zu jeder (Einband-)Turingmaschine eine neue Turingmaschine konstruieren kann, die zwei Bänder und nur die beiden Zustände $z_0$ (Startzustand) und $z_e$ (Endzustand) besitzt.
			\item Zeigen Sie, dass man eine beliebige Mehrband-Turingmaschine mit $k$ Bändern durch eine Einband-Turingmaschine simulieren kann.
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item Die Idee bei dieser Aufgabe ist, dass man aus einer TM eine neue konstruiert, die die Zustände der alten TM explizit auf dem zweiten Band speichert. Für jeden Berechnungsschritt der ursprünglichen TM muss die neue TM erst das zweite Band lesen und dann anhand dessen Inhalts auf dem ersten Band agieren. Danach muss sie den neuen Zustand auf das zweite Band schreiben. Etwas formaler ersetzt man jeden Übergang $\delta(z_i, w) = (z_j, v, B)$ (mit $B \in \{L,N,R\}$) durch den Übergang $\delta(z_0, w, z_i) = (z_0, v, z_j, B, N)$ für alle $z_j \notin F$. Falls $z_i$ der Startzustand ist, dann muss man noch den Übergang $\delta(z_0, w, \square) = (z_0, v, z_j, B, N)$ hinzufügen, da das zweite Band zu Beginn leer ist. Falls $z_j \in F$, so muss man den Übergang durch $\delta(z_0, w, z_i) = (z_e, v, \square, B, N)$ ersetzen.
			\item Die grobe Idee ist es, das einzelne Band der Einband-TM (ETM) in mehrere \enquote{Spuren} aufzuteilen -- wenn bei der Mehrband-TM (MTM) $a_1, \dots, a_k$ untereinander auf den verschiedenen Bändern stehen, schreibt man bei der ETM $(a_1, \dots, a_k)$ als einzelnes Symbol auf das Band. Bei dieser einfachen Überlegung ergibt sich allerdings die Problematik, dass die Positionen der einzelnen Köpfe der MTM nicht gespeichert werden. Um dieses Problem zu umgehen kann man $k$ weitere Spuren einfügen, die sich die Positionen der Köpfe merken. Am einfachsten, in dem die jeweilige Spur bis auf ein einzelnes Symbol $\ast$ sonst überall leer ist. Dieses Symbol markiert die Position des jeweiligen Kopfes. Sei also eine MTM mit $k$ Bändern und einem Arbeitsalphabet $\Sigma$ gegeben, dann konstruieren wir eine ETM wie folgt:
			\begin{itemize}
				\item Unterteile das Arbeitsband der ETM in $2 \cdot k$ Spuren -- jedes Symbol auf dem Arbeitsband ist also ein $2k$-Tupel.
				\item Spur $2 \cdot i - 1$ enthält den Inhalt von Band $i$ der MTM.
				\item Spur $2 \cdot i$ speichert die Kopfposition von Kopf $i$ -- die Spur enthält ein einzelnes Symbol $\ast$, welches die Position angibt. Sonst enthält die Spur nur Blanksymbole.
				\item Das neue Arbeitsalphabet ist damit $\Gamma' = (\Gamma \cup \{\ast\})^{2k} \cup \Gamma$. Das äußere $\Gamma$ dient dazu, dass die Ein- und Ausgabe eins-zu-eins übernommen werden kann. (Potentiell ist $\Gamma'$ eine Obermenge der gültigen Symbole, da auf den ungerade Spuren kein $\ast$ stehen kann. Genauer wäre das Alphabet also $\Gamma' = (\Gamma \times \{\ast, \square\})^k \cup \Gamma$)
			\end{itemize}
			
			Die Arbeitsweise der ETM bei Eingabe $a_1 \cdots a_n$ ist beschreibt sich wie folgt: Ersetze $a_1 \cdots a_n \vdash^{\ast} (a_1, \ast, \square, \ast, \dots \square, \ast) \cdots (a_n, \ast, \square, \ast, \dots \square, \ast)$. Die Eingabe steht jetzt also auf der ersten Spur und alle anderen (ungeraden) Spuren sind leer. Weiter sind alle Kopfpositionen auf der \enquote{ersten} Zelle. Mit dieser Ersetzung stehen sowohl links als auch rechts vom in Spuren unterteilten Abschnitt einzelne Blanksymbole. Die TM kann also den Anfang und das Ende des Bandes erkennen. Laufe (mehrmals) über das Band und behandle jede Spur (also jedes Band der MTM) einzeln, nacheinander. Hierbei bietet es sich an, in den Zuständen zu speichern, welches Band (bzw. welche Spur) gerade betrachtet wird (intuitiv kann man zu jedem Zustand der MTM $k$ Zustände in der ETM definieren). Sei bspw.\ der Übergang der MTM $\delta(z, a_1, \dots, a_k) = (z', b_1, \dots, b_k, L, \dots, L)$. Die ETM simuliert diesen Übergang wie folgt:
			\begin{itemize}
				\item[] (Beginne in Zustand $z_{Spur 1}$)
				\item Suche auf Spur $2$ das Kopfsymbol $\ast$.
				\item Ersetze Symbol $a_1$ auf Spur $1$ zu $b_1$.
				\item Verschiebe das Kopfsymbol $\ast$ auf Spur $2$ nach links.
				\item[] (Wechsle in Zustand $z_{Spur 2}$)
				\item Wiederhole die drei Schritte für alle anderen Spur-Paare $(3,4), \dots, (2k-1,2k)$.
				\item[] (Wechsle in Zustand $z'_{Spur 1}$)
			\end{itemize}
		\end{enumerate}
	\end{loesung}
	
	\begin{aufgabe}{6}
		Die Firma \textsc{Globex} verkauft die Programmiersprache \enquote{\textsc{Loop++}}. Zusätzlich zu den Anweisungen üblicher (also aus der Vorlesung bekannter) \textsc{Loop}-Programme besitzt \textsc{Loop++} noch die folgenden Makros (mit der üblichen Semantik aus bekannten Programmiersprachen):
		\begin{itemize}
			\item \key{if} $x_k = 0$ \key{then} $A$ \key{else} $B$ \key{end} ($A$ und $B$ sind beliebige \textsc{Loop++}-Programme.)
			\item $x_i \defeq x_j + x_k$
			\item $x_i \defeq x_j \cdot x_k$
		\end{itemize}
		\textsc{Loop++} kostet wesentlich mehr als \textsc{Loop}. Ist dieser höhere Preis gerechtfertigt, oder kann \textsc{Loop++} nicht mehr berechnen als \textsc{Loop}?
	\end{aufgabe}
	
	\begin{loesung}
		\begin{itemize}
			\item \enquote{if-then-else} lässt sich mit den üblichen \textsc{Loop}-Befehlen simulieren. Eine Idee ist es, wenn $x_k \neq 0$ eine Variable, die das Ausführen von $A$ steuert auf $0$ zu setzen und eine Variable, die das Ausführen von $B$ steuert auf $1$ zu setzen.
			\begin{algorithmic}[1]
				\State $x_a \defeq 1$ \Comment{Steuert, ob $A$ ausgeführt wird.}
				\State $x_b \defeq 0$ \Comment{Steuert, ob $B$ ausgeführt wird.}
				\LoopX{$x_k$} \Comment{Wenn $x_k \neq 0$, \ldots}
					\State $x_a \defeq 0$ \Comment{\ldots, setze $x_a$ auf 0 \ldots}
					\State $x_b \defeq 1$ \Comment{\ldots und setze $x_b$ auf 1.}
				\EndLoopX
				\LoopX{$x_a$} \Comment{Wenn $x_a \neq 0$, also $x_k = 0$, \ldots}
					\State $A$ \Comment{(\ldots führe $A$ aus.}
				\EndLoopX
				\LoopX{$x_b$} \Comment{Wenn $x_b \neq 0$, also $x_k \neq 0$, \ldots}
					\State $B$ \Comment{\ldots führe $B$ aus.}
				\EndLoopX
			\end{algorithmic}
			\item \enquote{$x_j + x_k$} lässt sich auch mit den üblichen \textsc{Loop}-Befehlen simulieren. Man muss im Prinzip nur $x_k$-mal $1$ auf $x_j$ addieren. Formal sind in der VL bei der Addition \enquote{$x_i \defeq x_j + 1$} $i$ und $j$ verschieden, darum das etwas \enquote{umständliche} Programm mit der Extrazuweisung.
			\begin{algorithmic}[1]
				\State $x_i \defeq x_j$
				\LoopX{$x_k$} \Comment{$x_k$-mal addieren}
					\State $x_t \defeq x_i$
					\State $x_i \defeq x_t + 1$
				\EndLoopX
			\end{algorithmic}
		\item \enquote{$x_j \cdot x_k$} lässt sich auch dann mithilfe der Addition implementieren, indem man $x_k$-mal $x_j$ aufaddiert.
			\begin{algorithmic}[1]
				\State $x_i \defeq 0$
				\LoopX{$x_k$}
					\State $x_i \defeq x_i + x_j$
				\EndLoopX
			\end{algorithmic}
		\end{itemize}
	\end{loesung}
	
	\begin{aufgabe}{4}
		Die \emph{Lucas}-Zahlen sind wie folgt definiert:
		\begin{align*}
			L_1 &= 2 \\
			L_2 &= 1 \\
			L_{n+1} &= L_n + L_{n-1} \text{ (Für } n \geq 2 \text{)}
		\end{align*}
		
		Schreiben Sie ein \textsc{Loop}-Programm, das die $n$-te Lucas-Zahl $L_n$ berechnet. Wie üblich ist der Wert $n$ zu Beginn des Programms in Variable $x_1$ gespeichert. (Sie dürfen hierzu das Additions-Makro aus der vorigen Aufgabe nutzen.)
	\end{aufgabe}
	
	\begin{loesung}
		\begin{algorithmic}[1]
			\State $x_0 \defeq 2$ \Comment{Entspricht $L_n$}
			\State $x_2 \defeq 1$ \Comment{Entspricht $L_{n+1}$}
			\State $x_3 \defeq 0$ \Comment{Temporäre Variable zum Tauschen}
			\State $x_4 \defeq x_1 - 1$ \Comment{Zählvariable}
			
			\LoopX{$x_4$}
				\State $x_3 \defeq x_0 + x_2$
				\State $x_0 \defeq x_2$
				\State $x_2 \defeq x_3$
			\EndLoopX
		\end{algorithmic}
		
		Statt mit einer Hilfsvariable zu arbeiten kann man auch die drei Zeilen in der \textsc{Loop}-Schleife ersetzen durch: $x_2 \defeq x_0 + x_2$ und $x_0 \defeq x_2 - x_0$.
	\end{loesung}
	
	% \begin{aufgabe}{3 + 2}
		% Sei $f: \mathbb{N} \rightarrow \mathbb{N}$ eine \textsc{While}-berechenbare, injektive, totale Funktion.
		% \begin{enumerate}[\quad a)]
			% \item Zeigen Sie, dass die Umkehrfunktion $f^{-1}$ von $f$ ebenfalls \textsc{While}-berechenbar ist.
			% \item Gilt das gleiche auch für \textsc{Loop}-berechenbare Funktionen? (Begründen Sie Ihre Antwort.)
		% \end{enumerate}
	% \end{aufgabe}
	
	% \begin{loesung}
		% \begin{enumerate}[\quad a)]
			% \item \textsc{While}-berechenbare Funktionen müssen nicht total sein; Also darf die gesuchte Umkehrfunktion $f^{-1}$ partiell sein. Da $f$ injektiv ist, ist die folgende Umkehrfunktion wohldefiniert:
			% \begin{gather*}
				% f^{-1}(y) = \begin{cases}x \text{, falls }f(x) = y\\\text{undefiniert, sonst}\end{cases}
			% \end{gather*}
			% Um nun $f^{-1}$ zu berechnen, kann man einen Algorithmus schreiben, der alle $x$ ausprobiert, bis er dasjenige findet, für das gilt $f(x) = y$.
			
			% Beispielsweise:
			% \begin{algorithmic}[1]
				% \State $x_0 \defeq 0$
				% \State $x_t \defeq 1$
				% \While{$x_t \neq 0$}
					% \State $x_0 \defeq x_0 + 1$
					% \If{$f(x_0) = y$}
						% \State $x_t \defeq 0$
					% \EndIf
				% \EndWhile
			% \end{algorithmic}
			% \item Nein. \textsc{Loop}-berechenbare Funktionen müssen total sein, aber eine Umkehrfunktion ist nicht zwingend total. (Bspw. ist $f \colon \setN \rightarrow \setN$, $x \mapsto 2\cdot x$ total, aber die Umkehrfunktion $f^{-1} \colon \setN \rightarrow \setN$ ist nur für gerade Zahlen definiert.) Prinzipiell kann man in den meisten Fällen den Definitionsbereich einschränken um die undefinierten Fälle auszuschließen. Also statt $f^{-1} \colon \setN \rightarrow \setN$ kann man $f^{-1} \colon f(\setN) \rightarrow \setN$ setzen. (Im obigen Beispiel wäre dann $f^{-1} \colon \{x \in \setN \colon \exists x' \in \setN~2 \cdot x' = x\} \rightarrow \setN$ eine totale Funktion.) Allerdings müsste dann die Definition der \textsc{Loop}-Programme aus der Vorlesung, die beliebige natürliche Zahlen als Eingabe erlaubt, etwas verändert werden.
		% \end{enumerate}
	% \end{loesung}
\label{lastpage}
\end{document}