\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}

% 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{6}
\newcommand\Abgabe{17.\,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}{3 + 4}
		Es seien die beiden Folgen von Tupeln gegeben:
		\begin{itemize}
			\item $K_1 = $ (\LinearAXI\LinearACCCIX\LinearACCCIX, \LinearACCCIX\LinearAXXIX\LinearACCCIX), (\LinearACCCIX\LinearACCCIX\LinearAXI, \LinearACCCIX), (\LinearAXI\LinearACCCIX\LinearAXXIX\LinearAXI, \LinearAXXIX), (\LinearACCCIX\LinearAXXIX, \LinearAXI\LinearACCCIX\LinearAXXIX), (\LinearAXI, \LinearAXI\LinearAXI\LinearACCCIX)
			\item $K_2 = $ $(101, 10)$, $(1, 01)$, $(010, 10)$, $(10, 0)$
		\end{itemize}
		
		Zeigen oder widerlegen Sie die folgende Aussagen:
		\begin{enumerate}[\quad (i)]
			\item $K_1 \in PCP$
			\item $K_2 \in PCP$
		\end{enumerate}
	\end{aufgabe}
	
	\begin{loesung}
		\begin{enumerate}[\quad a)]
			\item $K_1 \in PCP$ mit $i_1 = 5$, $i_2 = 1$, $i_3 = 3$, $i_4 = 5$, $i_5 = 2$ und $i_6 = 4$. Es ergibt sich damit: \begin{center}
				\textcolor{blue}{\LinearAXI}\textcolor{green}{\LinearAXI\LinearACCCIX\LinearACCCIX}\textcolor{red}{\LinearAXI\LinearACCCIX\LinearAXXIX\LinearAXI}\textcolor{black}{\LinearAXI}\textcolor{blue}{\LinearACCCIX\LinearACCCIX\LinearAXI}\textcolor{orange}{\LinearACCCIX\LinearAXXIX}\\
				\textcolor{blue}{\LinearAXI\LinearAXI\LinearACCCIX}\textcolor{green}{\LinearACCCIX\LinearAXI\LinearACCCIX}\textcolor{red}{\LinearAXXIX}\textcolor{black}{\LinearAXI\LinearAXI\LinearACCCIX}\textcolor{blue}{\LinearACCCIX}\textcolor{orange}{\LinearAXI\LinearACCCIX\LinearAXXIX}
			\end{center}
			\item $K_2 \notin PCP$. Der einzig mögliche Anfang der Folge kann nur das erste Tupel $(101, 10)$ sein, da sich bei allen anderen Tupeln die beiden Komponenten im ersten Symbol unterscheiden. Darauf muss ein Tupel folgen, dessen zweite Komponente mit $1$ beginnt. Mit dem Tupel $(101, 10)$ ergibt sich allerdings $101\underline{1}01 \cdot w \neq 101\underline{0} \cdot v$, d.h. die beiden Wörter stimmen an der vierten Position nicht überein. Also muss das zweite gewählte Tupel $(010, 10)$ sein. Somit ergibt sich die folgende Situation, die wir $(\ast)$ nennen: \begin{align*} &\textcolor{blue}{101}\textcolor{green}{010} \cdot w\\ &\textcolor{blue}{10}\textcolor{green}{10} \cdot v
			\end{align*}
			\emph{Beobachtung:} Es muss auf jeden Fall das Tupel $(1, 01)$ verwendet werden, da bei allen anderen Tupeln die erste Komponente länger als die zweite ist und die beiden Wörter somit nie gleichlang werden können. Weiter kann das genannte Tupel höchstens zweimal hintereinander verwendet werden, da es keine Möglichkeit gibt \enquote{$111$} mit den zweiten Komponenten zu erzeugen. (Aus dem gleichen Grund kann Tupel $(101, 10)$ auch nicht auf die genannte Tupelkombination folgen.)
			
			Wenn wir die Tupel $(101,10)$, $(010,10)$, $(101,10)$ verwenden, dann können wir nicht als nächstes Tupel $(101,10)$ nutzen, da dann das nächste Tupel in der zweiten Komponente mit \enquote{$11$} beginnen müsste. Dies ist nicht möglich. Ebenfalls können wir die Tupel $(1, 01)$ und $(10, 0)$ nicht nutzen, da die zweiten Komponenten nicht mit $1$ beginnen. Wenn wir als viertes Tupel $(010,10)$ verwenden, dann müssen wir danach wieder das Tupel $(101,10)$ verwenden. Dies wiederholt sich immer wieder und das erste Wort wächst schneller als das zweite Wort. Es ist also nicht möglich, $(101,10)$ als drittes Tupel zu verwenden. Das heißt, das dritte gewählte Tupel muss $(010,10)$ sein. Wenn wir nun auf dieses Tupel zweimal $(1,01)$ folgen lassen \emph{(Einzig sinnvolle Wahl.)}, dann befinden wir uns wieder ein Situation $(\ast)$.
			
			Zusammengefasst bedeutet das, dass $K_2 \notin PCP$.
		\end{enumerate}
	\end{loesung}
	
	\begin{aufgabe}{4}
		Sei \textsc{01-PCP} die Variante des Postschen Korrespondenzproblems, bei der die Eingabetupel auf das Alphabet $\{0,1\}$ beschränkt sind (d.\,h.\ die Wörter der Wortpaarfolge sind nicht-leere Binärstrings). Zeigen Sie, dass diese Variante \emph{unentscheidbar} ist.
	\end{aufgabe}
	
	\begin{loesung}
		Die Idee bei dieser Aufgabe ist es, das allgemeine \textsc{PCP} auf \textsc{01-PCP} zu reduzieren; dann gilt, dass \textsc{01-PCP} nicht entscheidbar sein kann, da \textsc{PCP} nicht entscheidbar ist. Gegeben sei also eine \textsc{PCP}-Instanz über einem beliebigen Alphabet $\Sigma$. Wir müssen nun jedes Symbol $\alpha \in \Sigma$ als Binärstring kodieren. Allerdings muss man bei der Kodierung aufpassen, dass keine \enquote{falschen} Lösungen entstehen. Würde bspw. ein Symbol $\alpha$ mit $0$ kodiert werden und ein zweites Symbol $\beta$ mit $00$, dann wäre $0 \cdot 0 = 00$, allerdings $\alpha \cdot alpha \neq \beta$. Um diese Problematik zu umgehen, kann man die Kodierung so wählen, dass alle Kodierungen die gleiche Länge haben oder, dass bei allen Kodierungen der \enquote{Rand} eines Symbols explizit erkennbar ist. Prinzipiell funktioniert hier jede präfixfreie (oder suffixfreie) Kodierung.
		
		Eine (für die Reduktion passende) Kodierung könnte bspw. wie folgt konstruiert werden: Sei $\Sigma = \{\alpha_1, \dots, \alpha_m\}$. Wir ersetzen jedes Symbol $\alpha_i$ durch den Binärstring $01^i$ (also eine Null gefolgt von $i$ Einsen). Außerdem ersetzen wir in jedem Wort der Wortpaarfolge der gegebenen Probleminstanz die Symbole passend zur Kodierung. Diese Funktion (wenn auch nicht formal als Funktion aufgeschrieben) ist total und berechenbar und erfüllt somit die Eigenschaften einer Reduktionsfunktion. Da die Funktion bijektiv ist, gilt auch offensichtlich, dass die gegebene Probleminstanz genau dann eine Lösung hat, wenn auch die kodierte Instanz eine Lösung besitzt und somit gilt $\textsc{PCP} \leq \textsc{01-PCP}$.
	\end{loesung}
	
	\begin{aufgabe}{4}
		Sei \textsc{$1$-PCP} die Variante des Postschen Korrespondenzproblems, bei dem man die Eingabetupel auf das Alphabet $\{1\}$ beschränkt. Zeigen Sie, dass \textsc{1-PCP} \emph{entscheidbar} ist.
	\end{aufgabe}
	
	\begin{loesung}
		Wenn das Alphabet nur aus einem Zeichen besteht, dann kommt es nur auf die Längen der einzelnen Teilworte an. Darum kann man das ganze \enquote{rechnerisch} entscheiden. Folgender Algorithmus entscheidet das unäre PCP:
		\begin{enumerate}[\quad 1.]
			\item Wenn für alle Paare $(x_i, y_i)$ gilt: ${|x_i|} > {|y_i|}$, dann lehne ab.
			\item Wenn für alle Paare $(x_i, y_i)$ gilt: ${|x_i|} < {|y_i|}$, dann lehne ab.
			\item Sonst akzeptiere.
		\end{enumerate}
		Im letzten Schritt kann der Algorithmus problemlos akzeptieren, denn: Entweder es gibt ein Paar $(x_i, y_i)$ mit ${|x_i|} = {|y_i|}$. Dann ist dieses Paar eine gültige Lösung. Oder es existieren zwei Paare $(x_i, y_i)$ und $(x_j, y_j)$, so dass gilt: ${|x_i|} > {|y_i|}$ und ${|x_j|} < {|y_j|}$. Um nun mit den beiden Paaren zwei gleiche Wörter zu bilden müssen wir $n \cdot {|x_i|} + m \cdot {|x_j|} = n \cdot {|y_i|} + m \cdot {|y_j|}$ lösen. Diese Gleichung ist äquivalent zu $n \cdot ({|x_i|} - {|y_i|}) = m \cdot ({|y_j|} - {|x_j|})$. Diese hat eine Lösung mit $n = ({|y_j|} - {|x_j|})$ und $m = ({|x_i|} - {|y_i|})$. Wenn man nun $n$-mal Paar $(x_i, y_i)$ und $m$-mal Paar $(x_j, y_j)$ nimmt, ergeben sich gleiche Wörter:
		% \begin{align*}
			% &~(|y_j| - |x_j|) \cdot x_i + (|x_i| - |y_i|) \cdot x_j &=&~ (|y_j| - |x_j|) \cdot y_i + (x_i - y_i) \cdot y_j &~\\
			% \equiv &~ x_iy_j - x_ix_j + x_ix_j - x_jy_i &=&~ y_iy_j - x_jy_i + x_iy_j - y_iy_j &~\mathcomm{ausmultipliziert} \\
			% \equiv &~ x_iy_j - x_jy_i &=&~ - x_jy_i + x_iy_j &~\mathcomm{Zusammengefasst} \\
			% \equiv &~ x_iy_j - x_jy_i &=&~ x_iy_j - x_jy_i &~\mathcomm{Umsortiert}
		% \end{align*}
		\begin{align*}
			&~ x_i^{n} \cdot x_j^{m} &=&~ y_i^{n} \cdot y_j^{m} &~\\
			\equiv &~ x_i^{|y_j| - |x_j|} \cdot x_j^{|x_i| - |y_i|} &=&~ y_i^{|y_j| - |x_j|} \cdot y_j^{|x_i| - |y_i|} &~\\
			\equiv &~ (|y_j| - |x_j|) \cdot |x_i| + (|x_i| - |y_i|) \cdot |x_j| &=&~ (|y_j| - |x_j|) \cdot |y_i| + (|x_i| - |y_i|) \cdot |y_j| &~\mathcomm{Kodierung ausgewertet} \\
			\equiv &~ |x_i||y_j| - |x_i||x_j| + |x_i||x_j| - |x_j||y_i| &=&~ |y_i||y_j| - |x_j||y_i| + |x_i||y_j| - |y_i||y_j| &~\mathcomm{ausmultipliziert} \\
			\equiv &~ |x_i||y_j| - |x_j||y_i| &=&~ - |x_j||y_i| + |x_i||y_j| &~\mathcomm{Zusammengefasst} \\
			\equiv &~ |x_i||y_j| - |x_j||y_i| &=&~ |x_i||y_j| - |x_j||y_i| &~\mathcomm{Umsortiert} \\
			\equiv &~ 1^{|x_i||y_j| - |x_j||y_i|} &=&~ 1^{|x_i||y_j| - |x_j||y_i|} &~\mathcomm{Kodierung angewandt}
		\end{align*}
		
		Da ${|x_i|} > {|x_j|} > 0$ und ${|y_j|} > {|y_i|} > 0$ und somit ${|x_i||y_j|} > {|x_j||y_i|}$, ist $1^{|x_i||y_j| - |x_j||y_i|}$ ein gültiges Wort.
		
	\end{loesung}
\label{lastpage}
\end{document}