\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\\
  Solution
}
\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.
    \label{it:equal}
  \item $\{a^nb^nc^n : n\geq 1\}$.
    \label{it:abc}
  \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$.
    \label{it:wwR}
  \end{enumerate}
\end{exercise}

\begin{solution}
  We start with item~\ref{it:equal}.

  The idea is to keep a signed unary counter on the second tape (the sign is kept in a state) and keep track
  of the difference between the number of~$0$'s and~$1$'s read.

  The transitions are given in Table~\ref{tab:equal}.

  \medskip

  For item~\ref{it:abc}, we use a unary counter on the second tape to count the~$a$'s and use it to check if
  the number of~$b$'s and~$c$'s is the same.

  The transitions are given by
  \begin{center}
    \begin{tabular}{>{$\displaystyle}r<{$}|*{4}{>{$\displaystyle}c<{$}}}
      & q_0 & q_1 & q_2 & q_f\\    
      \hline
      (a,a) & - & - & - & -\\
      (a,b) & - & - & - & -\\
      (a,c) & - & - & - & -\\
      (a,B) & (q_0,a,a,R,R) & - & - & -\\
      (b,a) & - & (q_1,b,a,R,L) & - & -\\
      (b,b) & - & - & - & -\\
      (b,c) & - & - & - & -\\
      (b,B) & (q_1,b,B,S,L) & - & - & -\\
      (c,a) & - & - & (q_2,c,a,R,R) & -\\
      (c,b) & - & - & - & -\\
      (c,c) & - & - & - & -\\
      (c,B) & - & (q_2,c,B,S,R) & - & -\\
      (B,a) & - & - & - & -\\
      (B,b) & - & - & - & -\\
      (B,c) & - & - & - & -\\
      (B,B) & - & - & (q_f,B,B,R,R)
    \end{tabular}
  \end{center}
  where~$q_0$ is the initial state and~$q_f$ is the

  \medskip

  For item~\ref{it:wwR}, the idea is to copy the input to the second tape then compare the input with the
  reverse of the second tape. We also need to ensure that the word has even length.

  The transitions are given in Table~\ref{it:wwR}.
  \begin{landscape}
    \begin{table}[htb]
      \begin{tabular}{>{$\displaystyle}r<{$}|*{9}{>{$\displaystyle}c<{$}}}
        & (0,0) & (0,1) & (0,B) & (1,0) & (1,1) & (1,B) & (B,0) & (B,1) & (B,B)\\
        \hline
        q_0 & - & - & (q_+,0,1,R,R) & - & - & (q_-,1,1,R,R) & - & - & (q_f,B,B,R,R)\\
        q_+ & - & - & (q_+,0,1,R,R) & - & - & (p_+,1,B,S,L) & - & - & -\\
        p_+ & - & - & - & - & (q_+,1,B,R,S) & (q_0,1,B,R,R) & - & - & -\\
        q_- & - & - & (p_-,0,B,S,L) & - & - & (q_-,1,1,R,R) & - & - & -\\
        p_- & - & (q_-,0,B,R,S) & (q_0,0,B,R,R) & - & - & - & - & - & -\\
        q_f & - & - & - & - & - & - & - & - & -
      \end{tabular}
      \caption{Transitions for item~\ref{it:equal}. In the above~$q_0$ is the initial state and~$q_f$ is the
        accepting state.}
      \label{tab:equal}
    \end{table}

    \begin{footnotesize}
    \end{footnotesize}

    \begin{table}[htb]
      \begin{tabular}{>{$\displaystyle}r<{$}|*{9}{>{$\displaystyle}c<{$}}}
        & (0,0) & (0,1) & (0,B) & (1,0) & (1,1) & (1,B) & (B,0) & (B,1) & (B,B)\\
        \hline
        q_0 & - & - & (q_1,0,0,R,R) & - & - & (q_1,1,1,R,R) & - & - & (q_2,B,B,L,S)\\
        q_1 & - & - & (q_0,0,0,R,R) & - & - & (q_0,1,1,R,R) & - & - & -\\
        q_2 & - & - & (q_2,0,B,L,S) & - & - & (q_2,1,B,L,S) & - & - & (q_3,B,B,R,L)\\
        q_3 & (q_3,0,0,R,L) & - & - & (q_3,1,1,R,L) & - & - & - & (q_f,B,B,R,L)\\
        q_f & - & - & - & - & - & - & - & - & -
      \end{tabular}
      \caption{Transitions for item~\ref{it:wwR}. In the above~$q_0$ is the initial state and~$q_f$ is the
          accepting state.}
        \label{tab:wwR}
    \end{table}
  \end{landscape}
\end{solution}

\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}\}$.
    \label{it:more}
  \item $L = \{w\in\{0,1\}^* : w\text{ contains exactly twice as many zeroes as ones}\}$.
    \label{it:twice}
  \end{enumerate}
\end{exercise}

\begin{solution}
  For item~\ref{it:more}, we essentially do the same as in Exercise~1a of~HW3.

  The transition function is given by
  \begin{center}
    \begin{tabular}{>{$\displaystyle}r<{$}|*{4}{>{$\displaystyle}c<{$}}}
      & 0 & 1 & B & \ast\\
      \hline
      q_0 & (q_1,\ast,R) & (q_2,\ast,R) & (q_f,B,L) & (q_0,\ast,R)\\
      q_1 & (q_1,0,R) & (q_3,\ast,L) & (q_f,B,L) & (q_1,\ast,R)\\
      q_2 & (q_3,\ast,L) & (q_2,1,R) & - & (q_2,\ast,R)\\
      q_3 & (q_3,0,L) & (q_3,1,L) & (q_0,B,R) & (q_3,\ast,L)\\
      q_f & - & - & - & -
    \end{tabular}
  \end{center}
  where~$q_0$ is the initial state and~$q_f$ is the accepting state.

  \medskip

  For item~\ref{it:twice}, the idea is also similar to the one in Exercise~1a of~HW3.
  \begin{center}
    \begin{tabular}{>{$\displaystyle}r<{$}|*{4}{>{$\displaystyle}c<{$}}}
      & 0 & 1 & B & \ast\\
      \hline
      q_s & (q_0,\ast,R) & (q_1,\ast,R) & (q_f,B,L) & (q_0,\ast,R)\\
      q_0 & (q_0,0,R) & (q_{01},\ast,R) & - & (q_0,\ast,R)\\
      q_1 & (q_{01},\ast,R) & (q_{11},\ast,R) & - & (q_1,\ast,R)\\
      q_{01} & (q_{01},0,R) & (q_r,\ast,L) & - & (q_{01},\ast,R)\\
      q_{11} & (q_r,\ast,L) & (q_{11},1,R) & - & (q_{11},\ast,R)\\
      q_r & (q_r,0,L) & (q_r,1,L) & (q_s,B,R) & (q_r,\ast,L)\\
      q_f & - & - & - & -
    \end{tabular}
  \end{center}
  where~$q_s$ is the initial state and~$q_f$ is the accepting state.
\end{solution}

\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{solution}
  For each~$\sigma\in\Gamma$, we introduce a new symbol~$\ast$ and a new state~$q_\sigma$. We also
  introduce three new states~$q_s$, $q_r$ and~$q_f$. The subroutine is activated by transitioning to~$q_s$ with the
  head on the space in which one wants to create an extra cell and is finished in state~$q_f$ with the head on
  the new cell created (which will have a blank symbol). We also assume that the calling machine never writes
  blank symbols (this can be achieved by replacing all blank symbols written with a new symbol~$\widetilde{B}$
  that represents it).

  The transitions of the subroutine are given by
  \begin{align*}
    \forall\sigma\in\Gamma, \delta(q_s,\sigma) & = (q_\sigma,\ast,R);\\
    \forall\sigma,\tau\in\Gamma\setminus\{B\}, \delta(q_\sigma,\tau,R) = (q_\tau,\sigma,R);\\
    \delta(q_\sigma,B) & = (q_r,\sigma,L);\\
    \forall\sigma\in\Gamma,\delta(q_r,\sigma) = (q_r,\sigma,L);\\
    \delta(q_r,\ast) & = (q_f,B,S).
  \end{align*}
\end{solution}

\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}

\begin{solution}
  The algorithm is as follows.

  We first move~$1^n$ to the second tape (so that the first tape becomes blank). Then we write a~$1$ on the
  first tape. Then we consecutively write a new~$1$ on the first tape and subtract~$1$ from the second tape
  (treating it as a binary number). Since~$1^n$ is the binary number representation of the number~$2^n - 1$,
  this algorithm correctly ends with~$1^{2^n}$ on the first tape.
\end{solution}
\end{document}