\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


\DeclareMathOperator{\Inf}{Inf}
\DeclareMathOperator{\Tot}{Tot}

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

\begin{document}
\maketitle

\begin{definition*}
  A Turing machine \emph{transducer} is a Turing machine that outputs strings, rather than accepting or
  rejecting. That is, if~$M$ is a Turing machine, then~$M$ computes the function which takes an input~$x$ to
  the value that is left on the tape when~$M$ halts. If~$M$ does not halt on input~$x$, then the function
  computed by~$M$ is undefined on~$x$. A function~$f$ that is computed by a Turing machine transducer is
  called \emph{partial computable} (partial, since~$M$ may not halt on some inputs, and then~$f$ is undefined
  on those inputs).
\end{definition*}

\begin{exercise}\label{ex:recenum}
  In class and in the book, you were given the following definition of a recursively enumerable language.

  A language~$L$ is recursively enumerable if there is a Turing machine~$M$ such that~$M$ accepts exactly
  those strings in~$L$. (On strings not in~$L$, the machine~$M$ may either reject or not halt.)

  Show that each of the following conditions is equivalent to~$L$ being recursively enumerable (in the above
  sense).

  \begin{enumerate}
  \item There is a partial computable function~$f$ such that~$L$ is the range of~$f$, that is, we have~$L =
    \{f(x) : x\in\Sigma^*\}$. Such an~$f$ is called an \emph{enumerator} of~$L$ since when~$f$ is run on all
    strings in parallel, it enumerates/lists the elements of~$L$ (possibly with repetitions).
    \label{it:enum}
  \item There is a partial computable function~$f$ such that~$L$ is the domain of~$f$, that is, we have~$L =
    \{x : f(x)\text{ is defined}\}$.
    \label{it:domain}
  \item There is a Turing machine~$M$ such that~$L = \{x : M\text{ halts on input } x\}$.
    \label{it:halts}
  \end{enumerate}
\end{exercise}

\begin{solution}
  Let us first prove that if~$L$ is recursively enumerable, then~\ref{it:enum} holds.

  Indeed, if~$M$ is a Turing machine with~$L(M) = L$, then an algorithm for the enumerator~$f$ is the
  following.

  \begin{algorithm}[H]
    \caption{Enumerator of~$L(M)$.}
    \label{alg:enum}
    \DontPrintSemicolon
    Given an input~$x\in\Sigma^*$, run~$M$ on~$x$.\;
    \lIf{$M$ accepts~$x$}{Stop with output~$x$.}
    \lElse{Loop forever.}
  \end{algorithm}

  Clearly the algorithm above computes the partial function defined by
  \begin{align*}
    f(x) & =
    \begin{dcases*}
      x, & if~$x\in L(M)$;\\
      \infty, & if~$x\notin L(M)$;
    \end{dcases*}
  \end{align*}
  where~$f(x) = \infty$ denotes that~$f(x)$ is undefined. Hence the range of~$f$ is~$L(M)$.

  \medskip

  Let us now prove that~\ref{it:enum} implies~\ref{it:domain}.

  Let~$E$ be a Turing machine that computes a partial function~$f$ whose range is~$L$ and consider the following
  algorithm.

  \begin{algorithm}[H]
    \caption{Function whose domain is~$L$.}
    \DontPrintSemicolon
    Given an input~$x\in\Sigma^*$, do the following.\;
    \For{$n\leftarrow 0,1,\ldots$}{
      Let~$S_n$ be the set of all words of length at most~$n$.\;
      \For{$y\in S_n$}{
        Run~$E$ on input~$y$ for~$n$ steps.\;
        \If{$E$ stops with output~$x$}{Stop with output~$\oldepsilon$.}
      }
    }
  \end{algorithm}

  Clearly the algorithm above computes the partial function defined by
  \begin{align*}
    g(x) & =
    \begin{dcases*}
      \oldepsilon, & if~$x$ is in the range of~$f$;\\
      \infty, & if~$x$ is not in the range of~$f$.
    \end{dcases*}
  \end{align*}
  Hence the domain of~$g$ is equal to the range of~$f$.

  \medskip

  Let us now prove that~\ref{it:domain} implies~\ref{it:halts}.

  Let~$D$ be a Turing machine that computes a partial function~$g$ whose domain is~$L$. Then~$D$ halts if and
  only if its input is in~$L$.

  \medskip

  Finally, let us prove that~\ref{it:halts} implies that~$L$ is recursively enumerable. Let~$H$ be a Turing
  machine that halts if and only if its input is in~$L$.

  Then the algorithm that runs~$H$ in its input and accepts if~$H$ halts ($H$ can either accept or
  reject) corresponds to a Turing machine~$M$ such that~$L(M) = L$.
\end{solution}

\begin{exercise}\label{ex:rec}
  In this exercise, we will show the recursive analogue of item~\ref{it:enum} of Exercise~\ref{ex:recenum}.

  First, fix a computable enumeration~$(x_n)_{n\in\NN}$ of~$\Sigma^*$ without repetitions, that is, the
  following hold.
  \begin{itemize}
  \item For every~$n\neq m$, we have~$x_n\neq x_m$.
  \item We have~$\Sigma^* = \{x_n : n\in\NN\}$.
  \item There is a Turing machine~$E$ that halts on every input and if the input is a binary representation
    of~$n\in\NN$, the tape contains~$x_n$ when~$E$ halts, i.e., the machine~$E$ computes the function~$\langle
    n\rangle\mapsto x_n$.
  \end{itemize}

  This induces an order of the words in~$\Sigma^*$ given by
  \begin{align*}
    x_n \leq x_m & \iff n \leq m.
  \end{align*}

  Show that a language~$L$ is recursive if and only if there is an enumerator~$f$ for~$L$ such that~$f$ is
  \emph{monotone}, that is, for every~$x,y\in\Sigma^*$ with~$x\leq y$, we have~$f(x)\leq f(y)$, where
  when~$f(x)$ is undefined, we interpret as~$f(x) = +\infty$.

  Hint: it is useful to separate the case when~$L$ is finite.
\end{exercise}

\begin{solution}
  Suppose~$L$ is recursive, that is, suppose that there exists a Turing machine~$M$ that decides~$L$. Consider
  the following algorithm.

  \begin{algorithm}[H]
    \caption{Monotone enumerator of~$L(M)$.}
    \DontPrintSemicolon
    Given an input~$x\in\Sigma^*$, run~$E$ on~$n=0,1,\ldots$ until~$E(n) = x$ (that is, we have~$x_n = x$).\;
    $k\leftarrow 0$.\;
    \For{$i\leftarrow 0,1,\ldots$}{
      Let~$x = E(i)$ (i.e., we have~$x_i = x$).\;
      Run~$M$ on~$x$.\;
      \If{$M$ accepts~$x$}{
        \lIf{$k = n$}{Stop with output~$x$.}
        \lElse{$k\leftarrow k + 1$}
      }
    }
  \end{algorithm}

  Clearly the algorithm above only enumerates words in~$L(M)$.

  Let
  \begin{align*}
    I & =
    \begin{dcases*}
      \NN, & if~$L(M)$ is infinite;\\
      \{0,1,\ldots,\lvert L(M)\rvert-1\}, & if~$L(M)$ is finite;
    \end{dcases*}
  \end{align*}
  and let~$(n_i)_{i\in I}$ be such that~$n_i < n_j$ if~$i<j$ and~$L(M) = \{x_{n_i} : i\in I\}$. Note that
  if~$f$ is the partial function of the algorithm above, then we have
  \begin{align*}
    f(x_i) & = x_{n_i}
  \end{align*}
  for every~$i\in I$. This implies that~$f$ is a monotone enumerator for~$L(M)$.

  \medskip

  Suppose now that~$f$ is a monotone enumerator for~$L$ and let~$M$ be a Turing machine associated
  with~$f$. If~$L$ is finite, then~$L$ is clearly recursive, so suppose~$L$ is infinite.

  Consider the following algorithm.
  
  \begin{algorithm}[H]
    \caption{Deciding~$L$ from monotone enumerator.}
    \DontPrintSemicolon
    Given an input~$x\in\Sigma^*$, run~$E$ on~$n=0,1,\ldots$ until~$E(n) = x$ (that is, we have~$x_n = x$).\;
    $k\leftarrow 0$.\;
    \For{$i\leftarrow 0,1,\ldots$}{
      Let~$x = E(i)$ (i.e., we have~$x_i = x$).\;
      Run~$M$ on~$x$.\;
      \If{$M$ outputs~$y$}{
        \lIf{$x = y$}{Accept.}
        \Else{
          Run~$E$ on~$m=0,1,\ldots$ until~$E(m) = y$.\;
          \lIf{$m > n$}{Reject.}
        }
      }
    }
  \end{algorithm}

  First note that since~$L$ is infinite, then~$M$ must always halt (otherwise, if it does not halt for~$x_n$,
  then we have~$f(x_m)=\infty$ for every~$m\geq n$, which would mean that~$L$ is finite). Also, for every
  input~$x$, since~$f(x_0)<f(x_1)<\cdots$, we know that there exists~$m\in\NN$ large enough so
  that~$f(x_m)\geq x$. Taking the minimum such~$m\in\NN$, we get that~$x$ is enumerated by~$f$ if and only
  if~$f(x_m)=x$, which is precisely what is checked by the algorithm above.
\end{solution}

\begin{exercise}
  Show that every infinite recursively enumerable language~$L$ contains an infinite subset~$L'\subseteq L$
  such that~$L'$ is recursive.

  Hint: use Exercises~\ref{ex:recenum} and~\ref{ex:rec}.
\end{exercise}

\begin{solution}
  Let~$M$ be a Turing machine that computes an enumerator for~$L$ and let us construct a monotone enumerator
  for an infinite language~$L'\subseteq L$. Using the notation of Exercise~\ref{ex:rec}, consider the
  following algorithm.

  \begin{algorithm}[H]
    \caption{Monotone enumerator from~$M$.}
    \DontPrintSemicolon
    Given an input~$x\in\Sigma^*$, run~$E$ on~$n=0,1,\ldots$ until~$E(n) = x$ (that is, we have~$x_n = x$).\;
    $\ell\leftarrow -1$.\;
    $k\leftarrow 0$.\;
    \For{$s\leftarrow 0,1,\ldots$}{
      \For{$i\leftarrow 0$ \KwTo $s$}{
        Run~$M$ on~$x_i$ for~$s$ steps.
        \If{$M$ outputs~$y$}{
          Run~$E$ on~$m=0,1,\ldots$ until~$E(m) = y$.\;
          \If(\label{lin:if}){$m > \ell$}{
            $\ell\leftarrow m$.\;
            \lIf{$k = n$}{Output~$y$.\;}
            $k\leftarrow k+1$.\;
          }
        }
      }
    }
  \end{algorithm}

  Clearly the algorithm above only enumerates words inside~$L$. We claim now that the algorithm above always
  halts. Indeed, since~$L$ is infinite, we know that for~$i$ large enough, we must
  have~$M(x_i)>x_\ell$. This means whatever is the value of~$\ell$, for~$s$ large enough, the algorithm will
  test true in line~\ref{lin:if}, this will cause either~$k$ to be incremented or~$M$ to output. Since~$k$ can
  only be incremented at most~$n$ times before outputting, it follows that the algorithm always halts.

  It remains to prove that the algorithm above is a monotone enumerator~$f$.

  Note first that~$\ell$ can only increase its value and it does so every time line~\ref{lin:if} tests true.

  Note that if~$n_1 < n_2$, then the algorithm above runs exactly the same for~$x_{n_1}$ and~$x_{n_2}$
  while~$k<n_1$. This means that if~$f(x_{n_1}) = x_r$, then when running on input~$x_{n_2}$, right before~$k$
  is set to~$n_1+1$, we know that~$\ell$ is set to~$r$. Since the value of~$\ell$ only increases and we know
  that if~$f(x_{n_2}) = x_m$, then we must have~$m > \ell\geq r$, it follows that~$f(x_{n_1}) < f(x_{n_2})$.

  Therefore~$f$ is monotone.
\end{solution}

\begin{exercise}
  Consider the following two languages.
  \begin{align*}
    \Inf & = \{\langle M\rangle : L(M) \text{ is infinite}\};\\
    \Tot & = \{\langle M\rangle : M\text{ halts on all inputs}\}.
  \end{align*}

  \begin{enumerate}
  \item Give a reduction from~$\Inf$ to~$\Tot$.
    \label{it:InfTot}
  \item Give a reduction from~$\Tot$ to~$\Inf$.
    \label{it:TotInf}
  \item Using the generalized/second Rice's Theorem (a.k.a.\ Rice--Shapiro Theorem), show that neither~$\Inf$
    nor its complement~$\overline{\Inf}$ are recursively enumerable.
    \label{it:Inf}
  \item Using items~\ref{it:InfTot} and~\ref{it:Inf}, show that neither~$\Tot$ nor its
    complement~$\overline{\Tot}$ are recursively enumerable.
    \label{it:Tot}
  \item Using the Rice--Shapiro Theorem directly (i.e., without using the previous items), show that
    neither~$\Tot$ nor its complement~$\overline{\Tot}$ are recursively enumerable.
    \label{it:TotRS}
  \end{enumerate}
\end{exercise}

\begin{solution}
  For item~\ref{it:InfTot}, consider the following algorithm that uses a~$\Tot$-oracle.

  \begin{algorithm}[H]
    \caption{Algorithm for~$\Inf$, using~$\Tot$-oracle.}
    \SetKwProg{Alg}{Algorithm}{:}{}
    \DontPrintSemicolon
    On input~$\langle M\rangle$, do the following.\;
    Consider the Turing machine~$M'$ associated with the following algorithm:\;
    \Alg{M'}{
      On input~$x$, let~$n = \lvert x\rvert$ be the length of~$x$.\;
      \For{$t\leftarrow 0,1,\ldots$}{
        Let~$S_t$ be the set of all words of length greater or equal to~$n$ but smaller or equal to~$n+t$.\;
        \For{$y\in S_t$}{
          Run~$M$ on~$y$ for~$t$ steps.\;
          \lIf{$M$ accepts}{Accept.}
        }
      }
    }
    \If{$\langle M'\rangle\in\Tot$}{Accept.}
    \Else{Reject.}
  \end{algorithm}

  Note that the~$\Tot$-oracle algorithm above always halts.

  Consider an input~$\langle M\rangle$ in~$\Inf$. Then we claim that the machine~$M'$ built by the algorithm
  on input~$\langle M\rangle$ is in~$\Tot$.

  Indeed, since~$L(M)$ is infinite, whatever is the input~$x$ of~$M'$, we know that there exists~$y\in L(M)$
  such that~$\lvert y\rvert\geq\lvert x\rvert$, which means that for~$t$ large enough, we have both~$y\in S_t$
  and~$M$ accepts~$y$ in at most~$t$ steps, so~$M'$ must accept~$x$. Therefore~$M'$ accepts all words, that
  is, we have~$L(M')=\Sigma^*$, which implies that~$M'$ halts in all inputs, hence~$\langle
  M'\rangle\in\Tot$.

  But then the algorithm above accepts~$\langle M\rangle$.

  Consider now an input~$\langle M\rangle$ that is not in~$\Inf$. Then we claim that the machine~$M'$ built by
  the algorithm on input~$\langle M\rangle$ is not in~$\Tot$.

  Indeed, since~$L(M)$ is finite, we know that~$M'$ cannot accept any input~$x$ of length greater than the
  largest length of a word in~$L(M)$, since~$M'$ only tests words that are of length greater or equal
  to~$\lvert x\rvert$. But~$M'$ never explicitly rejects any word, so it must loop forever in these large
  length words, hence~$\langle M'\rangle\notin\Tot$.

  But then the algorithm above rejects~$\langle M\rangle$.

  Therefore, the algorithm above decides~$\Inf$ with the help of a~$\Tot$-oracle.

  \medskip

  For item~\ref{it:TotInf}, consider the following algorithm that uses an~$\Inf$-oracle.
  
  \begin{algorithm}[H]
    \caption{Algorithm for~$\Tot$, using~$\Inf$-oracle.}
    \SetKwProg{Alg}{Algorithm}{:}{}
    \DontPrintSemicolon
    On input~$\langle M\rangle$, do the following.\;
    Consider the Turing machine~$M'$ associated with the following algorithm:\;
    \Alg{M'}{
      On input~$x$, let~$n = \lvert x\rvert$ be the length of~$x$.\;
      Let~$S_n$ be the set of all words of length at most~$n$.\;
      Run~$M$ on all words in~$S_n$.\;
      If~$M$ halts on all these words, accept.
    }
    \lIf{$\langle M'\rangle\in\Inf$}{Accept.}
    \lElse{Reject.}
  \end{algorithm}

  Note that the~$\Inf$-oracle algorithm above always halts.

  Consider an input~$\langle M\rangle$ in~$\Tot$. Then we claim that the machine~$M'$ built by the algorithm
  on input~$\langle M\rangle$ is in~$\Inf$.

  Indeed, since~$M$ always halts, it follows that~$M'$ will always accept any input, hence~$L(M')=\Sigma^*$,
  which is infinite.

  But then the algorithm above accepts~$\langle M\rangle$.

  Consider now an input~$\langle M\rangle$ that is not in~$\Tot$. Then we claim that the machine~$M'$ built by
  the algorithm on input~$\langle M\rangle$ is not in~$\Inf$.

  Indeed, since~$M$ does not always halt, there exists a word~$x$ such that~$M$ does not halt on~$x$, which
  implies that~$M'$ will never halt in any word of length at least~$\lvert x\rvert$ (since it will run~$M$
  on~$x$). Therefore~$L(M')$ can only contain words of length less than~$\lvert x\rvert$, i.e., it must be a
  finite language, hence~$\langle M'\rangle\notin\Inf$.

  But then the algorithm above rejects~$\langle M\rangle$.

  Therefore, the algorithm above decides~$\Tot$ with the help of an~$\Inf$-oracle.

  \medskip

  Let us now solve item~\ref{it:Inf}.

  Consider the set~$P_\infty$ of all recursively enumerable languages that are infinite. Note that
  \begin{align*}
    \Inf & = \{\langle M\rangle : L(M)\in P_\infty\}.
  \end{align*}

  However, note that for every~$L\in P_\infty$ and every~$L'\subseteq L$ finite, we have~$L'\notin P_\infty$
  (since~$L'$ is finite). So by Rice--Shapiro Theorem, we get that~$\Inf$ is not recursively enumerable.

  Let then~$P_f$ be the set of all recursively enumerable languages that are finite. Note that
  \begin{align*}
    \overline{\Inf} & = \{\langle M\rangle : L(M)\in P_f\}.
  \end{align*}

  Take any~$L\in P_f$ and note that~$\Sigma^*\supseteq L$, but~$\Sigma^*\notin P_f$ (as it is infinite). Hence
  by Rice--Shapiro Theorem, we get that~$\overline{\Inf}$ is not recursively enumerable.

  \medskip

  We now proceed to item~\ref{it:Tot}.

  Suppose toward a contradiction that~$\Tot$ is recursively enumerable, then we can replace the~$\Tot$-oracle
  of item~\ref{it:InfTot} with a Turing machine~$M$ such that~$L(M)=\Tot$ and the resulting algorithm will
  accept every input in~$\Inf$ and either reject or loop forever in every input not in~$\Inf$. This implies
  that~$\Inf$ is recursively enumerable, which is a contradiction with item~\ref{it:Inf}.

  Suppose now toward a contradiction that~$\overline{\Tot}$ is recursively enumerable and let~$T$ be a Turing
  machine such that~$L(T)=\overline{\Tot}$, then we can replace the last two lines of the algorithm in
  item~\ref{it:InfTot} with ``Run~$T$ on~$\langle M'\rangle$, if~$M'$ accepts, accept; otherwise reject.'',
  and the resulting algorithm will accept every input in~$\overline{\Inf}$ and either reject or loop forever
  in every input not in~$\overline{\Inf}$. This implies that~$\overline{\Inf}$ is recursively enumerable,
  which is a contradiction with item~\ref{it:Inf}.

  \medskip

  Finally, let us solve item~\ref{it:TotRS}.

  Let~$P = \{\Sigma^*\}$ be the set of languages that contains only the language of all words. Note
  that~$\Sigma^*$ does not have any finite sublanguage that is also in~$P$, so by the Rice--Shapiro Theorem,
  we know that~$L_P = \{\langle M\rangle : L(M)\in P\} = \{\langle M\rangle : L(M) = \Sigma^*\}$ is not
  recursively enumerable.

  Suppose toward a contradiction that~$\Tot$ is recursively enumerable and let~$M_T$ be a Turing machine such
  that~$L(M_T)=\Tot$. Consider the following algorithm.

  \begin{algorithm}[H]
    \caption{Recognizing~$L_P$ from~$\Tot$.}
    \label{alg:Tot}
    \SetKwProg{Alg}{Algorithm}{:}{}
    \DontPrintSemicolon
    On input~$\langle M\rangle$, consider the Turing machine~$M'$ associated with the following algorithm:\;
    \Alg{M'}{
      On input~$x$, run~$M$ on~$x$.\;
      \If{$M$ accepts}{Accept.}
      \Else{Loop forever.}
    }
    Run~$M_T$ on~$\langle M'\rangle$.
    \If{$M_T$ accepts}{Accept.}
    \Else{Reject.}
  \end{algorithm}

  Note that the machine~$M'$ constructed by the algorithm above on input~$\langle M\rangle$ satisfies~$L(M) =
  L(M')$ and~$M'$ never explicitly rejects an input. This means that~$\langle M'\rangle\in\Tot$ if and only
  if~$L(M') = \Sigma^*$. This implies that~$M_T$ accepts~$\langle M'\rangle$ if and only if~$L(M) = \Sigma^*$,
  so the algorithm above accepts exactly the words in~$L_P$, a contradiction.

  Therefore~$\Tot$ is recursively enumerable.

  Let now~$P' = \{L\subseteq\Sigma^* : L\text{ is recursively enumerable and } L\neq\Sigma^*\}$ be the set of
  all recursively languages that do not contain all the words. Clearly~$\Sigma^*$ is not in~$P$ and for any
  language~$L$ in~$P$ (e.g., for~$\varnothing\in P$), we have~$L\subseteq\Sigma^*$. By the Rice--Shapiro
  Theorem, we know that~$L_{P'} = \{\langle M\rangle : L(M)\in P'\} = \{\langle M\rangle : L(M)\neq\Sigma^*\}$
  is not recursively enumerable.

  Suppose toward a contradiction that~$\overline{\Tot}$ is recursively enumerable and let~$M_T$ be a Turing
  machine such that~$L(M_T)=\overline{\Tot}$. Consider Algorithm~\ref{alg:Tot} again but with this definition
  of~$M_T$. Again, we know that the~$M'$ constructed by the algorithm is such that~$L(M) = L(M')$ and
  furthermore, we know that~$\langle M'\rangle\in\Tot$ if and only if~$L(M')=\Sigma^*$. This implies
  that~$M_T$ accepts~$\langle M'\rangle$ if and only if~$L(M)\neq\Sigma^*$, so Algorithm~\ref{alg:Tot} accepts
  exactly the words in~$L_{P'}$, a contradiction.
\end{solution}

\end{document}
