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

\newcommand{\ZETTELNUMMER}{2}
\newcommand{\ABGABEDATUM}{on 10. May 2016 in the tutorial session}

\newcounter{AUFGNR}
\setcounter{AUFGNR}{1}
\newcommand{\AUFGABE}[2]{\vspace{0.3cm}\item[Problem~\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{\eps}{\varepsilon}
\newcommand{\N}{\mathbb{N}}



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


\begin{document}
\pagestyle{empty}
\hrule\medskip
\rule{0ex}{0ex}\\[-1ex]
\ZETTELNUMMER. Assignment on 

\smallskip
\noindent
\large
\textbf{Computational Complexity Theory}\hfill SoSe 2016 \\[0.5ex]
\normalsize
Wolfgang Mulzer, Claudia Dieckmann

\medskip\hrule

\smallskip
\noindent
\textbf{Due} \ABGABEDATUM

\vskip 0.5cm


\begin{description}
\AUFGABE {Simulation of Turing Machines} {10 points}

Let $L \subseteq \{0,1\}^*$ be a language,
and let $M$ be a Turing machine with $k$ tapes and work alphabet $\Gamma$.
Suppose that $M$ decides $L$ in $T(n)$ time. 
Show that there exists a Turing machine $M'$ with a single tape and
work alphabet $\Gamma = \{0, 1, \Box\}$ that decides $L$.
How much time does $M'$ need? Try to make your estimate as precise as 
possible.

\AUFGABE{Oblivious Turing Machine}{10 points}

A function $T : \N \rightarrow \N$ is called 
\emph{time-constructible} if (i) $T(n) \geq n$ for all
$n \in \N$ and (ii) there exists a Turing machine $M_T$ that computes
the function $n \mapsto T(n)$ in time $T(n)$ (as usual, the input input
and output of $M_T$ are encoded as binary numbers over $\{0,1\}$).

A Turing machine $M$ is called \emph{oblivious} if for every input $w$ and
for every number $i \in \N$, the position of $M$'s head after $i$ steps
depends only on $|w|$ and $i$ (i.e., the head movements of $M$ depend only
on the input size).

Let $L \subseteq \{0,1\}^*$ be a language, and let $M$ be a Turing machine
that decides $L$ in time $T(n)$. Suppose that $T$ is time-constructible.
Show that there exists a constant $C > 0$ and an oblivious Turing machine
$M'$ that decides $T$ in at most $CT(n)^2$ steps. Here, $C$ is a constant
that depends only on the number of tapes and the alphabet size of $M$, but
not on $n$.

\emph{Remark}: With a bit more effort, one can improve the running time of
$M'$ to $CT(n) \log T(n)$.

\AUFGABE{Undecidability}{10 points}

In your systems class, you learned that \emph{every} Boolean function
can be implemented by a circuit. However, in class we recalled that
the halting problem is undecidable. Why can't we prove that there is
no circuit for the halting problem? Does this contradict the Church-Turing
thesis? Explain your answer. 

\end{description}
\end{document}
