\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
}
\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}\}$.
  \item There is a Turing machine~$M$ such that~$L = \{x : M\text{ halts on input } x\}$.
  \end{enumerate}
\end{exercise}

\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{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{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.
  \end{enumerate}
\end{exercise}

\end{document}
