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

\newcommand{\ZETTELNUMMER}{8}
\newcommand{\ABGABEDATUM}{am 12. Juni 2015 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 2015 \\[0.5ex]
\normalsize
Wolfgang Mulzer

\medskip\hrule

\smallskip
\noindent
\textbf{Abgabe} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE{Entscheidbarkeit I}{10 Punkte}

Betrachten Sie die folgenden Sprachen \"uber $\Sigma = \{0,1\}$.
Hierbei ist $M$ jeweils eine Turing-Maschine.
\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$ akzeptiert $w$ nach mindestens $k$ Schritten.}\,\}$
\item  
$L_3 = \{\,(0^k, \langle M \rangle) \mid 
\text{$\exists w \in \{0,1\}^*:$ die TM $M$  akzeptiert $w$ in $\leq k$ 
Schritten.}\,\}$
\end{enumerate}

Welche der drei Sprachen sind  entscheidbar? 
Welche der drei Sprachen sind rekursiv aufz\"ahlbar? 
Begr\"unden Sie Ihre Antworten jeweils durch Angabe einer entsprechenden 
Turing-Maschine oder einer geeigneten Reduktion. 

\AUFGABE{Halteproblem}{10 Punkte}

In der Vorlesung haben wir die Unentscheidbarkeit
des Halteproblems durch eine Reduktion von der 
Universalsprache bewiesen. In dieser Aufgabe soll ein alternativer
Beweis betrachtet werden.

Angenommen, es existiert eine Turing-Maschine $M_H$, die das
Halteproblem entscheidet. Betrachten Sie die folgende Turing-Maschine
$X$:

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

\emph{Programm f\"ur $X$}:
F\"uhre $M_H$ mit der Eingabe $(\langle M \rangle, \langle M \rangle)$ aus.
Wenn $M_H$ die Eingabe akzeptiert, beginne eine Endlosschleife.
Wenn $M_H$ 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}

Seien $L_1, L_2, L_3 \subseteq \Sigma^*$ Sprachen.
Beweisen Sie die folgenden Eigenschaften der Relation $\leq$:
\begin{enumerate}
  \item Wenn $L_1 \leq L_2$ und $L_2$ entscheidbar ist, dann ist
    $L_1$ entscheidbar.
  \item Wenn $L_1 \leq L_2$ und $L_2$ semi-entscheidbar ist, dann ist
    $L_1$ semi-entscheidbar.
  \item Wenn $L_1 \leq L_2$ und $L_1$ nicht entscheidbar ist, dann ist
    $L_2$ nicht entscheidbar.
  \item Wenn $L_1 \leq L_2$ und $L_1$ nicht semi-entscheidbar ist, dann ist
    $L_2$ nicht semi-entscheidbar.
  \item Wenn $L_1 \leq L_2$
    und $L_2 \leq L_3$, dann auch $L_1 \leq L_3$.
\end{enumerate}

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

Betrachten Sie die folgenden Sprache $L \subseteq \{1\}^*$:
\[
  \{ 1^n \mid \text{der Dezimalbruch von $e = 2.7182\dots$ enth\"alt
   $n$ aufeinanderfolgende Zweien}\}.
\]
Zeigen Sie, dass $L$ entscheidbar ist. Was lernen Sie daraus \"uber
die Definition von Berechenbarkeit?

\emph{Hinweis}: Zeigen Sie zun\"achst: wenn 
$1^n \in L$ f\"ur ein $n \in \N$ ist, dann gilt auch
$1^{m} \in L$ f\"ur alle  $m = 1, \dots, n$.

\end{description}

\end{document}
