\documentclass[10pt]{article}

\usepackage{ngerman,a4}
\usepackage{amstext}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
\usepackage{alltt}
\usepackage[latin1]{inputenc}

\thispagestyle{empty}

\title{Theoretische Informatik - Übungsblatt 3 \\
	Übungsgruppe 7 - Mi, 16-18 Uhr \\
	Elena Kvassova}
\author{Jan Hendrik Dithmar (Matrikelnummer 2031259) \\
	Dirk Heine (Matrikelnummer 2030941)}
\date{}

\begin{document}

\newcommand{\AND}{\ensuremath{\wedge}}
\newcommand{\OR}{\ensuremath{\vee}}
\newcommand{\SetR}{\ensuremath{\mathbb{R}}}
\newcommand{\SetN}{\ensuremath{\mathbb{N}}}
\newcommand{\SetZ}{\ensuremath{\mathbb{Z}}}
\newcommand{\SetQ}{\ensuremath{\mathbb{Q}}}
\newcommand{\QED}{\ensuremath{\hspace*{\fill}\square}}
\newcommand{\FLASH}{\ensuremath{\hspace*{\fill}\lightning}}

\maketitle

\newpage

\section*{Aufgabe 1}
\begin{enumerate}[(a)]
    \item   Eine Relation $\circ$ heißt transitiv, wenn gilt
            $a \circ b \quad\wedge\quad b \circ c \quad\Longrightarrow\quad a \circ c$
            Es ist offensichtlich, dass für die Relation $\le$
            aus $a \le b$ und $b \le c$ folgt
            $a \le b \le c \quad\Longrightarrow\quad a \le c$. \QED
    \item   Aus $f^{-1}(L_2)=L_1$ folgt direkt, dass die Funktion $f$ für
            jedes $w \in L_1$ definiert ist. Die Bildmenge $f(L_1)$ ist nicht
            notwendigerweise gleich $L_2$, sie kann auch kleiner sein. Sie
            wird jedoch auf jeden Fall Teilmenge von $L_2$ sein, da anderenfalls
            die Voraussetzung verletzt würde.
            \begin{eqnarray*}
                \left( w \in L_1 \Leftrightarrow f(w) \in L_2 \right) & \Longrightarrow & f(L_1) \subseteq L_2 \\
                                                                      & \Longrightarrow & f^{-1}(L_2) = L_1 \\
                f^{-1}(L_2) = L_1 & \Longrightarrow & f(L_1) \subseteq L_2 \\
                                  & \Longrightarrow & \left( w \in L_1 \Leftrightarrow f(w) \in L_2) \right)
            \end{eqnarray*} \QED
    \item   Folgende Relation ist offensichtlich richtig
            \begin{eqnarray*}
                f(L_1) = L_2 & \Longrightarrow & \left( w \in L_1 \Rightarrow f(w) \in L_2 \right) \\
            \end{eqnarray*}
            Aus $f(L_1) = L_2$ folgt jedoch \emph{nicht}, dass $f(w) \in L_2 \Rightarrow w \in L_1$,
            da es $w \not\in L_1$ geben kann, für die $f(w) \in L_2$ gilt. \FLASH
    \item   Nach Voraussetzung ist $L_1$ auf $L_2$ reduzierbar, das heißt es gibt
            eine Turingmaschine $M_f$, die von einem Wort $w \in L_1$ auf ein Wort
            $w'=f(w) \in L_2$ abbildet. Ferner existiert eine Turingmaschine $M_2$,
            die jedes Wort aus $L_2$ akzeptiert. Damit $L_1$ rekursiv aufzählbar ist, muss
            es eine Turingmaschine $M$ geben, die für jedes Wort aus $L_1$
            akzeptiert. Wir konstruieren $M$ mit der Eingabe $w$ wie folgt:
            \begin{itemize}
                \item berechnen $w'=f(w)$ mittels $M_f$
                \item setze Eingabe $w'$ für Turingmaschine $M_2$
                \item $M$ akzeptiert ursprüngliche Eingabe $w$, wenn $M_2$ die Eingabe $w'$ akzeptiert
            \end{itemize}
            Es ist offensichtlich, dass $M$ alle Wörter aus $L_1$ akzeptiert.
            Somit ist bewiesen, dass unter den genannten Voraussetzungen $L_1$
            rekursiv aufzählbar ist (Beweis durch Konstruktion). \QED
\end{enumerate}

\section*{Aufgabe 2}
\begin{enumerate}[(a)]
    \item   Mit $a_i$ gleich der Länge des Wortes $x_i$ und $b_i$ gleich
            der Länge des Wortes $y_1$ reduziert sich das Problem auf
            $$ \exists k_1,\ldots,k_n\in\SetN_{\ge 0} \quad\Bigg|\quad \sum_{i=1}^n k_i \cdot a_i = \sum_{i=1}^n k_i \cdot b_i \text{ mit } \sum_{i=1}^n k_i > 0 $$
            Vermutung: entscheidbar, läuft auf die Entscheidung der Lösbarkeit dieses Gleichungssystems hinaus
    \item   Vermutung: nicht entscheidbar
    \item   Wenn man sich auf Wortpaare gleicher Länge beschränkt, ist das
            Post'sche Korrespondenzproblem \emph{entscheidbar}. Damit die aus
            den Tupeln gebildeten Zeichenketten $x_{i_1}x_{i_2}\ldots$ und
            $y_{i_1}y_{i_2}\ldots$ gleich sein können, müssen sie mindestens
            mit dem selben Wort beginnen, also muss $x_{i_1} = y_{i_1}$
            gelten. Es muss also ein Tupel $(x_j,y_j)$ mit $x_j = y_j$
            gefunden werden. Die Existenz eines solchen Tupels lässt sich
            aufgrund der Endlichkeit der Anzahl dieser Tupel in endlicher
            Zeit entscheiden. Wurde eine solcher Index $j$ gefunden, ist
            trivialerweise bereits eine Lösung gefunden, nämlich die
            $n=1$ elementige Folge von Indices $i_1=j$. Wird kein solcher
            Index gefunden, gibt es keine Lösung. \QED
\end{enumerate}

\section*{Aufgabe 3}
Wir zeigen die Existenz der Funktion $p$ durch Konstruktion einer Turingmaschine,
die $p$ berechnet. Die durch die Gödelnummer beschriebene Turingmaschine $P_w$
verwendet den Startzustand $q_1$ (wechselt ohne Änderung zu $q_3$, den akzeptierenden
Endzustand $q_2$, eine Reihe von Zuständen (Anzahl gleich der Länge des Wortes $w$), von denen jeder
genau ein Zeichen des Wortes schreibt und dann einen Schritt nach rechts geht,
und zwei Zustände zum Finden des Anfangs der Ausgabe. Wir verwenden zur
Realisierung eine 3-Band-Turingmaschine. Die Konstruktion dieser Turingmaschine
funktioniert wie folgt:
\begin{enumerate}
    \item   auf Band 1 befindet sich das Wort $w$, die Bänder 2 und 3 sind noch leer,
            Band 2 wird temporär die Ausgabe enthalten und Band 3 temporär die aktuelle
            Zustandsnummer $i \ge 1$ als Folge von $i$ Nullen
    \item   schreibe auf Band 2
            \begin{itemize}
                \item dreimal eine 1 (jeweils nach rechts gehen, Beginn der Gödelnummer)
                \item schreibe Gödelcode für $(q_1, B) \to (q_3, B, N)$ (der Standzustand für $P_w$; da das Band zu Beginn leer ist, braucht nur die Eingabe B berücksichtig werden)
                \item für den akzeptierende Endzustand $q_2$ von $P_w$ braucht nach Definition Gödelnummer nichts geschrieben zu werden (keine Aktion im Endzustand)
            \end{itemize}
    \item   schreibe auf Band 3 dreimal eine 0 und gehe jeweils einen Schritt nach rechts (Initialisierung der aktuellen Zustandsnummer mit 3)
    \item   \label{LOOP}wenn von Band 1 ein B gelesen wird (Wortende erreicht), dann gehe zu \ref{RAUS}
    \item   sonst kopiere Inhalt Band 3 (Folge von Nullen) ab aktueller Position auf Band 2 (aktuelle Zustandsnummer)
    \item   schreibe eine 1 auf Band 2 (Trennzeichen)
    \item   schreibe dreimal 0 auf Band 2 ($P_w$ liest ein B)
    \item   schreibe eine 1 auf Band 2 (Trennzeichen)
    \item   hänge an die Zustandsnummer auf Band 3 eine 0 an (die aktuelle Zustandsnummer wird inkrementiert)
    \item   kopiere Inhalt Band 3 auf Band 2 (nachfolgende Zustandsnummer)
    \item   schreibe eine 1 auf Band 2 (Trennzeichen)
    \item   wenn das aktuelle Zeichen von Band 1 eine 0 ist, schreiben wir eine 0 auf Band 2, wenn es eine 1 ist schreiben wir zwei Nullen
    \item   schreibe eine 1 auf Band 2 (Trennzeichen)
    \item   schreibe drei Nullen auf Band 2 ($P_w$ soll einen Schritt nach rechts machen)
    \item   schreibe zweimal eine 1 auf Band 2 (Ende Gödelcode)
    \item   gehe zu \ref{LOOP}
    \item   \label{RAUS}schreibe auf Band 2 die entsprechenden Gödelcodes, so
            dass die Turingmaschine $P_w$ bis zum Beginn ihrer Ausgabe nach
            links läuft und auf dem ersten Zeichen der Ausgabe stehen bleibt
            und zum Zustand $q_2$ von $P_w$ springt (bestehend aus zwei
            Zuständen, der erste trägt die auf Band 3 enthaltene Zustandsnummer,
            der zweite die nachfolgende)
    \item   schreibe dreimal eine 1 (Abschluß der Gödelnummer)
    \item   kopiere Inhalt von Band 2 auf Band 1 und laufe solange nach links,
            bis Lesekopf auf dem ersten Zeichen der Ausgabe steht, springe
            dann zu unserem akzeptierenden Endzustand    
\end{enumerate}

\section*{Aufgabe 4}
\begin{enumerate}[(a)]
    \item   Die Aussage lässt sich wie folgt formulieren:
            $$ \forall k>1 \quad\exists p,q \quad|\quad p+q = 2 \cdot k \text{ mit} $$
            $$ p,q \in \Big\{\: n\in\SetN_{\ge 2} \:\Big|\: \nexists a,b\in\{2,\ldots,n-1\}: a \cdot b = n \:\Big\} $$
    \item   
    Seien $a,b,n,r_i \in \SetN$. Seien ferner $q_1,q_2\in\SetN$ derart, dass
    $$ \nexists n \neq 1: q_1 = n \cdot a \:\wedge\: q_2 = n \cdot b $$
    Es gilt
    $$ \forall q_1,q_2,r_i \text{ mit } 0 \le r_i \le q_i \quad\exists x \text{ mit } 0 \le x \le q_1q_2 $$
    $$ \text{ so dass } \exists n \text{ mit } q_i n = x - r_i \text{ für } i\in\{1,2\} $$
\end{enumerate}

\end{document}
