\documentclass[a4paper,twoside,12pt]{article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts,amstext}
\usepackage{amsmath}
\usepackage{ngerman}
\usepackage{graphicx}
\usepackage{fullpage}

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 13. Juni 2014 bis 10 Uhr in die
Tutorenf\"acher}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Aufgabe~\arabic{AUFGNR}]\stepcounter{AUFGNR} #1\hfill\emph{#2}}


\newcommand{\floor}[1]{\left\lfloor{#1}\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil{#1}\right\rceil}
\newcommand{\half}[1]{\frac{#1}{2}}
\newcommand{\N}{\mathbb{N}}


\renewcommand{\labelenumi}{(\alph{enumi})}
\renewcommand{\labelenumii}{(\roman{enumii})}


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Aufgabenblatt zur Vorlesung

\smallskip
\noindent
\large
\textbf{Grundlagen der theoretischen Informatik}\hfill SoSe 2014 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}

\AUFGABE{Entscheidbarkeit I}{10 Punkte}

Bestimmen Sie f\"ur jede der folgenden Sprachen, ob sie entscheidbar ist.
Bestimmen Sie auch f\"ur jede der folgenden Sprachen, ob sie rekursiv aufz\"ahlbar
ist. Begr\"unden Sie Ihre Antwort jeweils durch Angabe einer entsprechenden 
Turingmaschine oder einer geeigneten Reduktion.
\begin{enumerate} 
\item 
$L_1 = \{\,(0^k, \langle M \rangle, w) \mid 
\text{$M$ akzeptiert $w$ nach h\"ochstens $k$ Schritten.}\,\}$ 
\item  
$L_2 = \{\,(0^k, \langle M \rangle, w) \mid 
\text{$M$ hat $w$ nach $k$ Schritten noch nicht akzeptiert.}\,\}$
\item  
$L_3 = \{\,(0^k, \langle M \rangle, w) \mid 
\text{$M$ akzeptiert $w$ nach mindestens $k$ Schritten.}\,\}$

\end{enumerate}

\AUFGABE{Halteproblem}{10 Punkte}

In der Vorlesung haben Sie einen Beweis f\"ur die Unentscheidbarkeit
des Halteproblems gesehen, der durch eine Reduktion von der 
Universalsprache funktioniert. In dieser Aufgabe soll ein alternativer
Beweis betrachtet werden.

Nehmen Sie an, es existiert eine Turing Maschine $M$, die das
Halteproblem entscheidet. Betrachten Sie die Turing-Maschine
$X$, die folgenderma\ss{}en arbeitet:

\emph{Eingabe}: Die Kodierung $\langle Y \rangle$ einer Turingmaschine.

\emph{Programm f\"ur $X$}:
F\"uhre $M$ mit der Eingabe $(\langle Y \rangle, \langle Y \rangle)$ aus.
Wenn $M$ die Eingabe akzeptiert, beginne eine Endlosschleife.
Wenn $M$ die Eingabe verwirft, gehe in den Zustand $q_\text{ja}$.

\begin{enumerate}
  \item Beschreiben Sie, was passiert, wenn wir die Turing-Maschine $X$ mit der
    Eingabe $\langle X \rangle$ ausf\"uhren.
  \item Folgern Sie, dass das Halteproblem nicht entscheidbar ist.
    Beschreiben Sie dabei genau die einzelnen Schritte des logischen 
    Arguments und an welcher Stelle der indirekte Beweis zum Einsatz kommt.
\end{enumerate}


\AUFGABE{Reduktionen}{10 Punkte}


\begin{enumerate}
  \item 
     Beweisen Sie, dass die Relation $\leq$ transitiv ist (d.h.,
     wenn f\"ur Sprachen $L_1$, $L_2$ und $L_3$ gilt: $L_1 \leq L_2$
     und $L_2 \leq L_3$, dann ist auch $L_1 \leq L_3$).
  \item  Beweisen Sie: Ist $L_1$ entscheidbar und $L_2$ eine beliebige
  Sprache mit $L_2 \neq \emptyset$, $L_2 \neq \Sigma^*$, dann gilt
  $L_1 \le L_2$.
\end{enumerate}




\AUFGABE{Entscheidbarkeit II}{freiwillig, 10 Zusatzpunkte}

Betrachten Sie die folgenden Sprache $L$:
    \[
       \{ 1^n \mid \text{die Dezimaldarstellung von $\pi = 3.1415\dots$ enth\"alt
          $n$ aufeinanderfolgende Sechsen}\}.
    \]
    Zeigen Sie, dass $L$ entscheidbar ist. Was lernen Sie daraus \"uber
    die Definition von Berechenbarkeit?

    \emph{Hinweis}: \"Uberlegen Sie zun\"achst, dass wenn das 
    Wort $1^n$ in $L$ ist, auch alle W\"orter $1^{m}$ f\"ur $m \leq n$ 
    in $L$ liegen m\"ussen.



\end{description}
\end{document}
