\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 -- Homework~3
}
\author{\relax}
\date{\today}

\begin{document}
\maketitle

\begin{exercise}[HMU~8.2.2]
  Design Turing machines for the following languages.
  \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}[HMU~8.2.3]
  Design a Turing machine that takes as input a number~$N$ in binary and adds~$1$ to it. To be precise, the
  tape initially contains a~\$ followed by~$N$ in binary. The head is initially scanning the~\$ in
  state~$q_0$. Your Turing machine should halt with~$N+1$ in binary on its tape, scanning the leftmost symbol
  of~$N+1$, in state~$q_f$. You may destroy the~\$ in creating~$N+1$, if necessary. For instance,
  $q_0\$10011\mapsto\$q_f10100$ and~$q_0\$11111\mapsto q_f100000$.
  \begin{enumerate}
  \item Give the transitions of your Turing machine, and explain the purpose of each state.
  \item Show the sequence of instantaneous descriptions (IDs) of your Turing machine when given input~\$111.
  \end{enumerate}
\end{exercise}

\begin{exercise}[HMU~8.2.5]
  Recall that the language~$L(M)$ defined by a Turing machine~$M$ is the set of input strings~$x$ such
  that~$M$ on input~$x$ halts in an accepting state. ($M$ halts when there is no entry in the transition
  function for the current state symbol pair.)

  Consider the Turing machine~$M$ with states~$\{q_0,q_1,q_2,q_f\}$, input alphabet~$\{0,1\}$, tape
  alphabet~$\{0,1,B\}$, start state~$q_0$, accepting state~$q_f$, and transition function~$\delta$. For each
  of the following transition functions~$\delta$, \emph{informally but clearly describe} the language~$L(M)$
  if~$\delta$ consists of the following set of rules.
  \begin{enumerate}
  \item $\delta$ is given by
    \begin{align*}
      \delta(q_0,0) & = (q_1,1,R); &
      \delta(q_1,1) & = (q_0,0,R); &
      \delta(q_1,B) & = (q_f,B,R).
    \end{align*}
  \item $\delta$ is given by
    \begin{align*}
      \delta(q_0,0) & = (q_0,B,R); &
      \delta(q_0,1) & = (q_1,B,R);\\
      \delta(q_1,1) & = (q_1,B,R); &
      \delta(q_1,B) & = (q_f,B,R).
    \end{align*}
  \item $\delta$ is given by
    \begin{align*}
      \delta(q_0,0) & = (q_1,1,R); &
      \delta(q_1,1) & = (q_2,0,L);\\
      \delta(q_2,1) & = (q_0,1,R); &
      \delta(q_1,B) & = (q_f,B,R).
    \end{align*}
  \end{enumerate}
\end{exercise}

\begin{exercise}[HMU~8.4.3]
  \emph{Informally but clearly describe} nondeterministic Turing machines (multiple tape, if you like) that
  accept the following languages. Try to take advantage of nondeterminism to avoid iteration and save time in
  the nondeterministic sense. That is, prefer to have your nondeterministic Turing machine
  nondeterministically branch a lot, while each branch is short.
  \begin{enumerate}
  \item The language of all strings of~$0$'s and~$1$'s that have some string of length~100 that repeats, not
    necessarily consecutively. Formally, this language is the set of strings of~$0$'s and~$1$'s of the
    form~$wxyxz$, where~$\lvert x\rvert = 100$, and~$w$, $y$ and~$z$ are strings of arbitrary length (possibly
    zero).
  \item The language of all strings of the form~$w_1\# w_2\# \cdots \# w_n$ for any~$n$ such that each~$w_i$
    is a string of~$0$'s and~$1$'s, and for some~$j$, $w_j$ is the integer~$j$ in binary.
    \label{it:wj}
  \item The language of all strings of the same form as~\ref{it:wj}, but for at least two values of~$j$, we
    have~$w_j$ equal to~$j$ in binary.
  \end{enumerate}
\end{exercise}

\end{document}
