\documentclass[10pt]{article}

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

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

\thispagestyle{empty}

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

\maketitle

\newpage

\section*{Aufgabe 1}
Sind $L$ und $\overline{L}$ semi-entscheidbar, so hält die TM auf allen Eingaben $w \in L$ an.
Somit ist die einzigste für Entscheidbarkeit fehlende Bedingung erfüllt. \QED

\section*{Aufgabe 2}
Wir verwenden eine 1-Band-Turingmaschine (1 Lese-/Schreibkopf), die auf diesem
Band zwei Spuren verwaltet. Dies läßt sich sehr einfach durch ein neues
Bandalphabet realisieren, wobei jeder Bandposition ein Tupel $(a,b)$
zugeordnet wird. Ferner führen wir ein neues Markiersymbol $\Psi$ in das
Bandalphabet ein.
$$ \Gamma' = \Gamma^2 \vee \{\Psi\} $$
\textbf{Notation: } Im folgenden verwenden wir die Bezeichnung
UTM für die zu emulierende unbeschränkte Turingmaschine und BTM für die
zu bauende einseitig beschränkte Turingmaschine. \\[0.25cm]
\textbf{Initialisierung: } Alle Werte auf der
Startposition und rechts von der Startposition auf dem Band unserer UTM
werden ab der Startposition unserer BTM in die erste Komponente des Tupels
eingetragen. In die zweite Komponente des Tupels an der Position 1
(Startposition) unserer BTM tragen wir das neue Symbol $\Psi$ ein.
Alle Werte links von der Startposition auf dem Band unserer UTM werden
ab Position 2 in die zweite Komponente des Tupels auf dem Band der BTM
eingetragen (Reihenfolge an der Startposition gespiegelt). \\[0.25cm]
\textbf{Weitere neue Definitionen:} Wir führen eine neue Zustandsmenge
$Q'$ ein. Wir betrachten die neuen Zustände als Tupel eines Zustandes
der UTM und einem Wert aus $\{0,1\}$. Dieser neue Wert gibt uns an,
ob wir uns mit unserer BTM auf einer Lese-/Schreibposition links von bzw.
auf der Startposition der UTM befinden (Wert 0, erste Tupelkomponente
auf dem Band unserer BTM ist zu verwenden) oder rechts davon (Wert 1,
zweite Tupelkomponente auf dem Band unserer BTM ist zu verwenden) befinden.
$$ Q' = Q \times \{0,1\} $$
Somit brauchen wir ebenfalls einen neuen Startzustand $q_0'$. Dieser
ergibt sich trivial, da wir mit unserer BTM im selben Zustand beginnen
wollen, in dem auch die UTM beginnen würde.
$$ q_0' = (q_0, 0) $$
Ferner muss die Menge der akzeptierende Endzustände $F$ angepaßt werden.
Dies ist ebenfalls trivial, da es für den akzeptierenden Endzustand
egal ist, ob wir uns links oder rechts von bzw. auf der Startposition der
UTM befinden.
$$ F' = \bigcup_{q \in F} \{ (q,0), (q,1) \} $$
Anschließend muss die Übergangsfunktion $\delta$ angepaßt werden.
$$ \delta'(\tilde{q},\tilde{a}) = \delta'((q,r),(a,b)) = ((q',r'),(a',b'),d) = (\tilde{q}',\tilde{a}',d) $$
\begin{eqnarray*}
    \tilde{q},\tilde{q}' \in Q' & \Longleftrightarrow & \tilde{q},\tilde{q}' \in Q \times \{0,1\} \\
    \tilde{a},\tilde{a}' \in \Gamma' & \Longleftrightarrow & \tilde{a},\tilde{a}' \in \Gamma\times\Gamma \\
    q,q' \in Q & & r,r' \in \{0,1\} \\
    a,a',b,b' \in \Gamma & & d \in \{L,N,R\}
\end{eqnarray*}
Im folgenden beschreiben wir mit Pseudocode die Realisierung der neuen Übergangsfunktion $\delta'$, welche
ihre Eingabe in den Symbolen $q,r,a,b$ erhält und das Ergebnis in den Symbolen $q',r',a',b',d$ zurückgibt.
\begin{alltt}
if (r=0) \{

    (q', a', d) := \(\delta\)(q, a)
    b' := b
    if ((d = L) \(\wedge\) (b = \(\Psi\))) \{
        d  := R
        r' := 1
    \} else \{
        r' := 0
    \}
    
\} else \{

    if (b = \(\Psi\)) \{
        q' := q
        a' := a
        b' := b
        r' := 0
        d  := N
    \} else \{
        (q', b', d) := \(\delta\)(q, b)
        a' := a
        r' := 1
        if (d = L) \{
            d := R
        \} else \{
            if (d = R) \{
                d := L
            \}
        \}
    \}
    
\}
\end{alltt}
Die gesuchte Turingmaschine ist mit den oben eingeführten Symbolen
$$ M' = (Q',\Sigma,\Gamma',q_0',\delta',F') $$

\section*{Aufgabe 3}
\emph{Vorbetrachtung:} Die Turingmaschine M gerät in eine Schleife, wenn M zum
zweiten mal eine bestimmte Konfiguration erreicht. Dieses Kriterium gilt nur,
wenn die Turingmaschine auf einem beidseitig beschränktem Band arbeitet,
wie es in der Aufgabe gegeben ist.

\noindent $|\Gamma|^{s(n)}$ ist die Anzahl der möglichen verschiedenen Bandinhalte
unter der Voraussetzung, dass nur die Bandzellen $1 \ldots s(n)$ verwendet
werden. $s(n)$ ist die Anzahl der möglichen Positionen, die der Lesekopf
einnehmen kann. Somit ist $|Q|\cdot|\Gamma|^{s(n)}\cdot s(n)$ die Anzahl
der möglichen verschiedenen Konfigurationen, die die Turingmaschine M auf
einer Eingabe der Länge $n$ annehmen kann. Nach obiger Vorbetrachtung darf
die Turingmaschine, damit sie nicht in eine Schleife eintreten kann und
somit überhaupt stoppen kann, die selbe Konfiguration nicht zweimal erreichen.
Nach Voraussetzung soll M auf einer Eingabe der Länge $n$ stoppen. Somit
stoppt sie spätestens nach $|Q|\cdot|\Gamma|^{s(n)}\cdot s(n)$ Schritten,
da es keine weitere noch nicht vorher erreichte Konfiguration gibt. \QED

\section*{Aufgabe 4}
Um zu zeigen, dass $f^{-1}(1)$ rekursiv aufzähltbar ist, müssen wir zeigen,
dass man eine Turingmaschine konstruieren kann, welche diese Sprache
akzeptiert.

\noindent Idee für Turingmaschine:
\begin{itemize}
    \item Turingmaschine produziert Prefix $p$ der Dezimaldarstellung von $\pi$
    \item sucht Eingabe in $p$
    \item wenn erfolgreich, Eingabe akzeptieren
    \item anderenfalls, wiederhole mit größerem Prefix
\end{itemize}
Die Turingmaschine die den Prefix erzeugt, ist nach Aufgabenstellung gegeben
(mit endlicher Laufzeit). Eine vergleichende Suche ist trivialerweise mit
einer Turingmaschine realisierbar. Da der jeweils durchsuchte Prefix endlich
ist, läßt sich die Suche innerhalb des Prefixes auch in endlicher Zeit realisieren. \QED

\section*{Aufgabe 5}
\begin{enumerate}[(a)]
    \item Sei eine Funktion gegeben, die wie folgt von $\SetN\to\SetN^2$ bzw.
          von $\SetN^2\to\SetN$ abbildet. Die fortlaufenden Werte aus $\SetN$
          werden diagonal von rechts oben nach links unten immer linienweise
          eingetragen. Die Funktion ist bijektiv, da die Zuordnung zwischen
          $\SetN$ und $\SetN^2$ offensichtlich in beide Richtungen eindeutig
          ist und auch jedes Element beider Mengen erreicht wird.          
          $$ \begin{array}{c|ccccc}
                & 0 & 1 & 2 & 3 & 4 \\ \hline
              0 & 0 & 1 & 5 & 6 & 10 \\
              1 & 2 & 4 & 7 & 11 \\
              2 & 3 & 8 & 12 \\
              3 & 9 & 13 \\
              4 & 14 \\
          \end{array} $$
          Wir zeigen die Realisierbarkeit der Berechnung der Funktion und der
          Umkehrfunktion mittels RAM durch Implementierung eines Programms,
          das diese Abbildungen berechnet. \\[0.1cm]          
          \textbf{Berechnung von $f_2(n)=(i,j)$} Sei \texttt{c(1)=n}
          gegeben. Das Ergebnis steht nach der Ausführung in \texttt{c(2)=i}
          und \texttt{c(3)=j}. \\[0.1cm]
          \texttt{// wenn c(0)=0, dann fertig} \\
          \texttt{1: LOAD 1} \\
          \texttt{2: IF c(0) = 0 GOTO 23} \\
          \texttt{// wenn c(2)=i=0, dann neue Diagonale beginnen} \\
          \texttt{3: LOAD 2} \\
          \texttt{4: if c(0) = 0 GOTO 15} \\
          \texttt{// sonst, diagonal nach links unten wandern} \\
          \texttt{5: CSUB 1} \\
          \texttt{6: STORE 2} \\
          \texttt{7: LOAD 3} \\
          \texttt{8: CADD 1} \\
          \texttt{9: STORE 3} \\
          \texttt{// c(1)=n dekrementieren und neu vergleichen} \\
          \texttt{10: LOAD 1} \\
          \texttt{11: CSUB 1} \\
          \texttt{12: STORE 1} \\
          \texttt{13: GOTO 2} \\
          \texttt{// neue Diagonale beginnen} \\
          \texttt{14: LOAD 3} \\
          \texttt{15: CADD 1} \\
          \texttt{16: STORE 2} \\
          \texttt{17: CLOAD 0} \\
          \texttt{18: STORE 3} \\
          \texttt{// c(1)=n dekrementieren und neu vergleichen} \\
          \texttt{19: LOAD 1} \\
          \texttt{20: CSUB 1} \\
          \texttt{21: STORE 1} \\
          \texttt{22: GOTO 2} \\
          \texttt{// Berechnung beendet} \\
          \texttt{23: END} \\[0.1cm]
          \textbf{Berechnung von $f_2^{-1}(i,j)=n$} Seien \texttt{c(1)=i} und
          \texttt{c(2)=j} gegeben. Das Ergebnis steht nach der Ausführung in
          \texttt{c(3)=n}. \\[0.1cm]
          \texttt{// wenn c(1)=c(4) und c(2)=c(5) dann fertig} \\
          \texttt{1: LOAD 1} \\
          \texttt{2: SUB 4} \\
          \texttt{3: STORE 6} \\
          \texttt{4: LOAD 4} \\
          \texttt{5: SUB 1} \\
          \texttt{6: ADD 6} \\
          \texttt{7: IF c(0) > 0 GOTO 14} \\
          \texttt{8: LOAD 2} \\
          \texttt{9: SUB 5} \\
          \texttt{10: STORE 6} \\
          \texttt{11: LOAD 5} \\
          \texttt{12: SUB 2} \\
          \texttt{13: ADD 6} \\
          \texttt{14: IF c(0) = 0 GOTO 32} \\
          \texttt{// noch keine Übereinstimmung} \\
          \texttt{// inkrementiere c(3)=n} \\
          \texttt{15: LOAD 3} \\
          \texttt{16: CADD 1} \\
          \texttt{17: STORE 3} \\
          \texttt{// wenn c(4)=i'=0, neue Diagonale beginnen} \\
          \texttt{18: LOAD 4} \\
          \texttt{19: if c(0) = 0 GOTO 26} \\
          \texttt{// diagonal nach links unten wandern} \\
          \texttt{20: CSUB 1} \\
          \texttt{21: STORE 4} \\
          \texttt{22: LOAD 5} \\
          \texttt{23: CADD 1} \\
          \texttt{24: STORE 5} \\
          \texttt{25: GOTO 1} \\
          \texttt{// neue Diagonale beginnen} \\
          \texttt{26: LOAD 5} \\
          \texttt{27: CADD 1} \\
          \texttt{28: STORE 4} \\
          \texttt{29: CLOAD 0} \\
          \texttt{30: STORE 5} \\
          \texttt{31: GOTO 1} \\
          \texttt{// Berechnung beendet} \\
          \texttt{32: END} \\[0.1cm]
          Beweis der Berechenbarkeit mittels Implementation erbracht. \QED
    \item Das Abbildungsprinzip aus Aufgabenteil (a) läßt sich trivialerweise auf $\SetN\to\SetN^k$ erweitern. \QED
\end{enumerate}

\end{document}
