\documentclass[11pt, a4paper, notitlepage, onecolumn, oneside, openany]{article}

\input{packages}
\input{layout}
\input{common_math}
\input{theorem_names_en}

\setlist[enumerate]{label={(\alph*)}, ref={(\alph*)}}
\setlist[description]{labelindent={2em}}


% Number algorithms under problems
\makeatletter
\renewcommand\thealgocf{%
  \theproblem.\arabic{algocf}}
\@addtoreset{algocf}{problem}
\makeatother


\title{%
  CMSC~28100-1 / MATH~28100-1\\
  Introduction to Complexity Theory\\
  Fall~2017 -- Bonus Homework
}
\author{\relax}
\date{\today}

\begin{document}
\maketitle

\begin{exercise}[HMU~8.4.1] Informally but clearly describe multitape Turing machines that accept each of the
  following languages from HW3, Exercise~1. Try to make your Turing machines run in time~$O(n)$.
  \begin{enumerate}
  \item The set of strings with an equal number of~$0$'s and~$1$'s.
  \item $\{a^nb^nc^n : n\geq 1\}$.
  \item $\{ww^R : w\text{ is any string of~$0$'s and~$1$'s}\}$, where~$w^R$ is the reverse of a string. For
    instance, we have~$10010^R = 01001$.
  \end{enumerate}
\end{exercise}

\begin{exercise}
  Design (single tape) Turing machines for the following languages.
  \begin{enumerate}
  \item $L = \{w\in\{0,1\}^* : w\text{ contains more zeroes than ones}\}$.
  \item $L = \{w\in\{0,1\}^* : w\text{ contains exactly twice as many zeroes as ones}\}$.
  \end{enumerate}
\end{exercise}

\begin{exercise}[HMU~8.3.2]
  A common operation in Turing machine programs involves ``shifting over'': ideally, we would like to create
  an extra cell at the current head position, in which we could store some character. However, we cannot edit
  the tape in this way. Rather, we need to move the contents of each of the cells to the right of the current
  head position one cell right, and then go our way back to the current head position. Show how to perform
  this operation. Hint: leave a special symbol to mark the position to which the head must return.
\end{exercise}

\begin{exercise}
  Give a sufficiently detailed description of how to construct a (multitape) Turing machine which computes the
  exponentiation function~$f(n) = 2^n$. You can assume the input~$n$ is given in unary form~$1^n$, and your
  Turing machine should produce a unary representation of the number~$2^n$ (i.e., your machine has to
  produce~$1^{2^n}$), and halt.
\end{exercise}


\end{document}
