\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
\algnewcommand\algorithmicloopx{\textbf{loop}}
\algdef{S}[WHILE]{LoopX}[1]{\algorithmicloopx\ #1\ \algorithmicdo}

% 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{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{1}
\newcommand\Abgabe{12.\,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}
		Gegeben ist eine Turingmaschine $M = (S, \Sigma, \Gamma, \delta, z_0, \square, F)$ mit Zustandsmenge $S = \{z_0, z_1, z_2, z_e\}$, Eingabealphabet $\Sigma = \{0,1\}$, Bandalphabet $\Gamma = \{0, 1, \square\}$, Blanksymbol $\square$, Startzustand $z_0$, Endzustandsmenge $F = \{z_e\}$ und Zustandsüberführungsfunktion $\delta$ mit:
		\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_1, 0, R)$ \\
			$z_1$ & $(z_1, 0, L)$ & $(z_1, 0, L)$ & $(z_2, 1, L)$ \\
			$z_2$ & $(z_2, 0, L)$ & $(z_2, 1, L)$ & $(z_e, \square, R)$
		\end{tabular}
		\end{center}
		\begin{enumerate}[\quad a)]
			\item Geben Sie die Folge der Konfigurationen an, die $M$ bei Eingabe $101$ durchläuft.
			\item Welche Funktion $s: \{0,1\}^{*} \rightarrow \{0,1\}^{*}$ und welche Funktion $f: \setN \rightarrow \setN$ berechnet $M$?
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		(Die TM sucht den rechten Rand der Eingabe und hängt $01$ hinter das Wort. Dann geht sie zurück an den linken Rand des Worts.)
		
		\begin{enumerate}[\quad a)]
			\item $z_{0}101 \vdash 1z_{0}01 \vdash 10z_{0}1 \vdash 101z_{0}\square \vdash 1010z_{1}\square \vdash 101z_{2}01 \vdash 10z_{2}101 \vdash 1z_{2}0101 \vdash z_{2}10101 \vdash z_{2}\square{}10101 \vdash z_{e}10101$
			\item Die Wortfunktion ist $s \colon \binStar \rightarrow \binStar$, $w \mapsto w \cdot 01$. Die Funktion auf den natürlichen Zahlen ist $f \colon \setN \rightarrow \setN$, $n \mapsto 2 \cdot (2 \cdot n) + 1$, was man zusammenfassen kann zu $n \mapsto 4n + 1$. (Falls man die Eingabe als Zahl zu einer anderen Basis $b$ interpretiert, dann ergibt sich als Funktion $n \mapsto b^2 \cdot n + 1$.)
		\end{enumerate}
	\end{loesung}
	
	% \begin{aufgabe}{4 + 1}
		% \begin{enumerate}[\quad a)]
			% \item Geben Sie eine Turingmaschine an, die testet ob eine gegebene natürliche Zahl durch 20 teilbar ist. Falls ja, so soll die Eingabe gelöscht werden und \textsc{Wahr} aufs Band geschrieben werden. Im anderen Fall soll \textsc{Falsch} aufs Band geschrieben werden. Nehmen Sie ruhig an, dass \textsc{Wahr} und \textsc{Falsch} einzelne Zeichen sind, die in eine einzelne Zelle auf dem Band passen.
			% \item Beschreiben Sie kurz, wie Sie Ihre Maschine so ändern können, dass diese den Rest bei einer Division durch 20 berechnet.
		% \end{enumerate}
		
		% \noindent(\emph{Hinweis:} Nutzen Sie ein geeigneteres Zahlensytem als das Binärsystem.)
	% \end{aufgabe}
	
	% \begin{loesung}		
		% \begin{enumerate}[\quad a)]
			% \item Die einfache Variante ist es Eingaben im Zwanzigersystem (\enquote{Vigesimalsystem}) zu lesen. Dann muss man nur die letzte Stelle der Eingabe betrachten. Ist diese $0$, dann ist die Zahl teilbar durch 20, sonst nicht. Falls man die Zahl im Dezimalsystem liest, dann muss man sich die letzten beiden Stellen der Eingabe anschauen. Wenn die Zahl auf $00$, $20$, \dots, oder $80$ endet, dann ist sie durch 20 teilbar. Im Binärsystem reicht es nicht aus, sich das Wort anzusehen. Man muss auf der Eingabe rechnen. Prinzipiell kann man (unabhängig vom Zahlensytem) immer wieder 20 von der auf dem Band stehenden Zahl subtrahieren bis die Zahl auf dem Band kleiner als 20 ist. (Also im Prinzip einfach nur den Rest \enquote{von Hand} ausrechnen.) Wenn die Zahl 0 ist, dann war sie durch 20 teilbar, wenn sie 1, \dots, 18 oder 19 ist, dann war sie nicht teilbar. Das könnte man relativ \enquote{simpel} im Unärsystem durchführen: Man gibt der Maschine 21 Zustände $\{z_0, \text{\dots}, z_{19}, z_e\}$ wobei $z_0$ Start- und $z_e$ Endzustand ist. Die TM läuft über die Eingabe, löscht jedes gefundene Unärsymbol und geht von Zustand $z_i$ in Zustand $z_{i+1}$ (bzw.\,von $z_{19}$ in $z_0$). Wenn das Band leer ist und die TM in Zustand $z_0$ ist, dann war die Zahl durch 20 teilbar. Falls sie in einem anderen Zustand ans Ende der Eingabe kommt, war die Zahl nicht teilbar. Die TM kann dann entsprechend der Teilbarkeit \textsc{Wahr} oder \textsc{Falsch} aufs Band schreiben und in den Endzustand gehen.
			
			% Ich gebe eine TM für das Zwanzigersystem an: $M = (S, \Sigma, \Gamma, \delta, z_0, \square, F)$ mit:
			% \begin{itemize}
				% \item Zustandsmenge $S = \{z_s, z_w, z_f, z_e\}$
				% \item Eingabealphabet $\Sigma = \{\mzero, \mone, \mtwo, \mthree, \mfour, \mfive, \msix, \mseven, \meight, \mnine, \mten, \meleven, \mtwelve, \mthirteen, \mfourteen, \mfifteen, \msixteen, \mseventeen, \meighteen, \mnineteen\}$\footnote{Die Zeichen für die Ziffern entstammen der Zahlschrift der Maya.}
				% \item Bandalphabet $\Gamma = \Sigma \cup \{\textsc{Wahr}, \textsc{Falsch}, \square\}$
				% \item Blanksymbol $\square$
				% \item Startzustand $z_s$
				% \item Endzustandsmenge $F = \{z_e\}$
				% \item Zustandsüberführungsfunktion $\delta$ wie folgt (die Spalten für \enquote{Ziffern} $\mone$ bis $\mnineteen$ fasse ich in einer Spalte zusammen):
				% \begin{center}
				% \begin{tabular}[c]{r | c c c}
					% $\delta(z,w)$ & $0$			& $\{\mone, \text{\dots}, \mnineteen\}$   & $\square$ \\ \hline
					% $z_0$ & $(z_w, \square, R)$	& $(z_f, \square, R)$ & $(z_e, \textsc{Wahr}, N)$ \\
					% $z_w$ & $(z_w, \square, R)$ & $(z_f, \square, R)$ & $(z_e, \textsc{Wahr}, N)$ \\
					% $z_f$ & $(z_w, \square, R)$ & $(z_f, \square, R)$ & $(z_e, \textsc{Falsch}, N)$
				% \end{tabular}
				% \end{center}
			% \end{itemize}
			
			% Die TM liest die Eingabe und überschreibt jedes gelesene Zeichen mit einem $\square$. Das zuletzt gelesene Zeichen (bzw. ob es $0$ war oder nicht) merkt sie sich im Zustand. Wenn sie eine $0$ liest, dann geht sie in den Zustand $z_w$, da die Zahl potentiell durch 20 teilbar ist. Wenn sie ein anderes Symbol liest, dann geht sie in Zustand $z_f$. Wenn sie am Ende der Eingabe angekommen ist, schreibt sie \textsc{Wahr} bzw. \textsc{Falsch} auf das Band, je nach dem ob das zuletzt gelesene Zeichen (also auch das letzte Zeichen der Eingabe) $\mzero$ (teilbar) oder eines aus $\{\mone, \text{\dots}, \mnineteen\}$ (nicht teilbar) war. Eine leere Eingabe habe ich als 0 und somit durch 20 teilbar interpretiert.
			% \item Den Rest der Division haben die oben beschriebenen TMs (implizit) schon ausgerechnet. Im Zwanzigersystem muss die TM nur das \enquote{rechteste} Zeichen stehen lassen, statt es mit \textsc{Wahr} oder \textsc{Falsch} zu überschreiben. Im Dezimalsystem lässt die TM die letzten beiden Zeichen stehen. Das linke der beiden Zeichen wird allerdings weiter verarbeitet. Falls dort eine gerade Zahl steht, dann wird diese gelöscht, falls dort eine ungerade Zahl steht, dann wird diese mit $1$ überschreiben. Im Unärsystem gibt der Zustand am Ende der Eingabe den Rest an ($z_i$ bedeutet einen Rest von $i$). Hier muss die TM dann nur noch entsprechend dem Zustand wieder Unärsymbole auf das Band schreiben.
		% \end{enumerate}
	% \end{loesung}
	
	\begin{aufgabe}{2 + 3}
		\begin{enumerate}[\quad a)]
			\item Zeigen Sie, dass man zu jeder Turingmaschine eine neue Turingmaschine konstruieren kann, die in jedem Schritt den Schreib-Lese-Kopf entweder eine Position nach links oder eine Position nach rechts bewegt. (D.\,h.\ der Kopf darf in keinem Schritt stehen bleiben -- die Kopfbewegungen sind aus $\{L, R\}$.)
			\item Zeigen Sie, dass man zu jeder Turingmaschine eine neue Turingmaschine konstruieren kann, die keine Felder links der \emph{initialen Eingabe} benutzt. D.\,h.\ das Arbeitsband ist nur rechtsseitig unendlich; die linke Seite besitzt einen Rand.
			% \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.
		\end{enumerate}
		% Zeigen Sie, dass man eine beliebige Mehrband-Turingmaschine mit $k$ Bändern durch eine Einband-Turingmaschine simulieren kann.
		
		(\emph{Hinweis}: Bei beiden Teilaufgaben reicht jeweils eine Beweisskizze -- es sind keine formalen Beweise gefordert. Überlegen Sie sich bei der ersten Teilaufgabe, wie Sie das \enquote{Stehenbleiben} mithilfe von zusätzlichen Zuständen umgehen können. Überlegen Sie sich bei der zweiten Teilaufgabe, wie Sie sicherstellen können, dass die TM links vom aktuellen Wort immer ein freies Feld für weitere Symbole hat.)
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item Hier muss aus einer beliebigen TM eine neue TM konstruiert werden, die das \enquote{Stehenbleiben} der alten TM ersetzt. Die einfachste Variante ist es, dass die neue TM statt stehen zu bleiben einen Schritt nach links und danach wieder nach rechts geht. Sie muss sich dann nur merken, in welchem Zustand sie nach der Rechtsbewegung sein müsste. Etwas formaler: Man ersetzt jeden Übergang $\delta(z_i, w) = (z_j, v, N)$ bei dem sich der Kopf nicht bewegt durch die beiden Übergänge $\delta(z_i, w) = (\hat{z}_j, v, L)$ und $\delta(\hat{z}_j, w) = (z_j, w, R)$.
			\item Die einfache (wenn auch zeitintensive) Methode ist es, jedes Mal, wenn der Kopf den linken Rand erreicht, das Wort auf dem Arbeitsband nach rechts zu schieben. Damit stellt man sicher, dass der Bandinhalt nur nach rechts wächst. Eine andere Idee, welche die Laufzeit nicht verändert, ist das Band der einseitig beschränkten TM in zwei Spuren aufzuteilen. Hierzu erweitert man das Arbeitsalphabet $\Gamma$ zu $\Gamma^2$; jedes Symbol im neuen Arbeitsalphabet ist ein Tupel $(w,v)$ (bzw. $\begin{pmatrix}w\\v\end{pmatrix}$) mit $w,v \in \Gamma$. Die ersten Komponenten entsprechen der oberen und die zweiten Komponenten der unteren Spur. Dann interpretiert man die obere Spur als die rechte und die untere Spur als die linke Hälfte des beidseitig unbeschränkten Bandes der ursprünglichen TM. Wenn die ursprüngliche TM von der linken in die rechte Hälfte wechselt (oder umgekehrt), dann muss die neue TM die entsprechende Spur betrachten. Das kann man mithilfe der Zustände steuern. Zu jedem Zustand $z_i$ führt man einen weiteren Zustand $z'_i$ ein. Die nicht-markierten Zustände werden dazu genutzt, dass die TM die obere Spur betrachtet und die markierten Zustände dazu, dass die TM die untere Spur betrachtet. Je nach Definition der einseitig beschränkten TM muss man eventuell das linkeste Feld explizit als Rand markieren.
			% \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.
		\end{enumerate}
		
		% 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 berschreibt 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 behandele 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{loesung}
	
	\begin{aufgabe}{4 + 1}
		Als Erweiterung der in der Vorlesung eingeführten Turingmaschine kann man \emph{Zweiband-Turingmaschinen} (ZTM) definieren. Eine ZTM besitzt zwei Arbeitsbänder mit jeweils eigenen Schreib-Lese-Köpfen. Formal ist eine ZTM auch ein $7$-Tupel $(S, \Sigma, \Gamma, \delta, s_0, \square, F)$. Der Unterschied ist, dass die Übergangsfunktion alle Arbeitsbänder betrachtet, also als $\delta \colon S \times \Gamma \times \Gamma \rightarrow S \times \Gamma \times \Gamma \times \{L,N,R\} \times \{L,N,R\}$ definiert ist.\footnote{Man kann die Definition allgemein auf $k$ Bänder erweitern.}
		\begin{enumerate}[\quad a)]
			\item Konstruieren Sie eine Zweiband-Turingmaschine, welche als Eingabe zwei Zahlen $x,y \in \setN$ bekommt und ausgibt, ob beide Zahlen gleich sind, ob die erste Zahl kleiner als die zweite Zahl ist, oder ob sie größer als die zweite Zahl ist. Formal soll die ZTM also die folgende Funktion berechnen:
			\begin{gather*}
				f \colon \setN^2 \rightarrow \{-1, 0, 1\}, (x,y) \mapsto \begin{cases}-1,~x<y\\0,~x=y\\1,~x>y\\\end{cases}
			\end{gather*}
			Nehmen Sie ruhig an, dass die beiden Zahlen binär kodiert sind und durch ein Trennzeichen getrennt auf dem ersten Arbeitsband als Eingabe stehen.
			\item Welchen Vorteil bietet eine ZTM gegenüber einer TM?
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item Grob kann man die Arbeitsweise der TM wie folgt beschreiben: Die TM sucht auf dem ersten Band das Trennzeichen bzw.\ die zweite Zahl. Diese Zahl überträgt sie dann Ziffer für Ziffer auf das zweite Band. Dann geht sie auf dem ersten Band wieder nach links, bis zur letzten Ziffer der ersten Zahl (und löscht dabei die Ziffern der zweiten Zahl und das Trennzeichen auf dem ersten Band.) Jetzt stehen beide Köpfe über den letzten Ziffern beider Zahlen. Nun kann die TM auf beiden Bändern die Köpfe Schritt für Schritt nach links bewegen, bis unter einem der Köpfe ein Blank-Symbol gelesen wird. Wird unter dem anderen Kopf \emph{kein} Blank gelesen, dann ist die zugehörige Zahl länger und somit größer. Falls unter dem anderen Kopf jedoch auch ein Blank gelesen wird, sind beide Zahlen gleich lang und müssen genauer betrachtet werden. Hierzu wandert die Maschine von links nach rechts, Ziffer für Ziffer, über die beiden Zahlen, bis sie eine Stelle findet, in der sich die Ziffern unterscheiden. Die Zahl, bei der die größere Ziffer gelesen wird (bei binärer Kodierung also die $1$), ist dann die größere Zahl. Falls die TM am Ende beider Zahlen ankommt und keine unterschiedlichen Ziffern findet, waren beide Zahlen gleichgroß. Die TM muss dann entsprechend die Bänder bereinigen und $-1$, $0$ oder $1$ auf das erste Band schreiben.
			
			Die Übergangsfunktion $\delta$ ist (etwas) genauer in der Tabelle auf der nachfolgenden Seite angegeben. Startzustand ist $z_s$, Finalzustände sind $\{z_{-1}, z_0, z_1\}$. Die anderen Parameter (Blanksymbol, Zustandsmenge, Alphabete) ergeben sich aus der Tabelle. Der Inhalt beider Bänder ist als Tupel angegeben; die Tupel, die das Trennsymbol ($\#$) als zweite Komponente beinhalten, stehen nicht in der Tabelle. Da die Eingabe auf dem ersten Band steht und die TM selbst das Trennsymbol nicht auf das zweite Band schreibt, muss keine dieser Kombinationen betrachtet werden. Weiter sind in der Tabelle einige Übergänge mit \enquote{--} markiert, da diese ebenfalls nicht vorkommen können. An dieser Stelle könnte man auch Übergänge einführen, die die TM in einen Zustand überführen, der anzeigt, dass die Eingabe nicht gültig war. An einigen Stellen steht als Funktionswert nur \enquote{$z'_{-1}$} (bzw.\ \enquote{$z'_{1}$}) -- hier wollte ich mir die Arbeit sparen, zu überlegen, in welche Richtung die Köpfe sinnvollerweise gehen und wie sie die Symbole löschen. (Die Arbeitsweise der TM in diesen beiden Zustände ist in der Tabelle selbst auch nur grob beschrieben.)
			
			Die von mit angegebene TM ist nur eine von vielen. Es gibt mit Sicherheit noch effizientere Möglichkeiten, die Zahlen auf Gleichheit zu überprüfen.
			\item Der Vorteil einer Mehrband-TM ist, dass man auf den verschiedenen Bändern Arbeitsschritte gleichzeitig machen kann. In der vorigen Aufgabe bspw.\ konnte man so in einem Schritt zwei Symbole vergleichen. Auf einer üblichen TM müsste man dazu das Zeichen lesen, sich das Zeichen merken und dann dass andere Zeichen suchen. Damit hat man einen (linearen) Mehraufwand. (Allerdings kann eine Mehrband-TM \emph{nicht} mehr berechnen als eine Einband-TM; man kann jede Mehrband-TM durch eine Einband-TM simulieren.)
		\end{enumerate}
		\pagebreak
		
		\begin{adjustbox}{max width=\textheight,angle=90}
			\begin{tabular}{r | c c c c c c c c c c c c}
				& $\square, \square$ & $\square, 0$ & $\square, 1$ & $\#, \square$ & $\#, 0$ & $\#, 1$ & $0, \square$ & $0, 0$ & $0, 1$ & $1, \square$ & $1, 0$ & $1, 1$ \\ \hline
				$z_s$ & -- & -- & -- & $(z_c, \#, \square, R, N)$ & -- & -- & $(z_s, 0, \square, R, N)$ & -- & -- & $(z_s, 1, \square, R, N)$ & -- & -- \\
				$z_c$ & $(z_b, \square, \square, L, L)$ & -- & -- & -- & -- & -- & $(z_c, 0, 0, R, R)$ & -- & -- & $(z_c, 1, 1, R, R)$ & -- & -- \\
				$z_b$ & -- & -- & -- & $(z_l, \square, \square, L, N)$ & $(z_l, \square, 0, L, N)$ & $(z_l, \square, 1, L, N)$ & $(z_b, \square, \square, L, N)$ & $(z_b, \square, 0, L, N)$ & $(z_b, \square, 1, L, N)$ & $(z_b, \square, \square, L, N)$ & $(z_b, \square, 0, L, N)$ & $(z_b, \square, 1, L, N)$ \\
				$z_l$ & $(z_g, \square, \square, R, R)$ & -- & \enquote{$z'_{-1}$} & -- & -- & -- & -- & $(z_l, 0, 0, L, L)$& $(z_l, 0, 1, L, L)$ & \enquote{$z'_{1}$} & $(z_l, 1, 0, L, L)$& $(z_l, 1, 1, L, L)$ \\
				$z_g$ & $(z_0, 0, \square, N, N)$ & -- & -- & -- & -- & -- & -- & $(z_g, \square, \square, R, R)$ & \enquote{$z'_{-1}$} & -- & \enquote{$z'_{1}$} & $(z_g, \square, \square, R, R)$ \\
				$z'_{-1}$ & \multicolumn{12}{c}{lösche alle Symbole auf beiden Bändern, schreibe $-1$ auf das erste Band und gehe in Zustand $z_{-1}$} \\
				$z'_{1}$ & \multicolumn{12}{c}{lösche alle Symbole auf beiden Bändern, schreibe $1$ auf das erste Band und gehe in Zustand $z_{1}$}
			\end{tabular}
		\end{adjustbox}
	\end{loesung}
\label{lastpage}
\end{document}