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

\begin{document}
\maketitle

\begin{exercise}[HMU~9.3.1]
  Show that the set of Turing machine codes for~TMs that accept all inputs that are palindromes (possibly
  along with other inputs) is undecidable, that is, show that the language
  \begin{align*}
    L & = \{\langle M\rangle : \forall w\in\Sigma^*, (w = w^R \implies w\in L(M))\}
  \end{align*}
  is undecidable, where~$w^R$ denotes the reverse of the string~$w$.
\end{exercise}

\begin{exercise}[HMU~9.3.2]
  The Big Computer Corp.\ has decided to bolster its sagging market share by manufacturing a high-tech version
  of the Turing machine, called~BWTM, that is equipped with \emph{bells} and \emph{whistles}. The~BWTM is
  basically the same as your ordinary Turing machine, except that each state of the machine is labeled either
  a ``bell-state'' or a ``whistle-state''. Whenever the~BWTM enters a new state, it either rings the bell or
  blows the whistle, depending on which type of state it has just entered. Prove that it is undecidable
  whether a given~BWTM~$M$, on given input~$w$, ever blows the whistle.
\end{exercise}

\begin{exercise}[HMU~9.3.3]
  Show that the language of codes for~TMs that, when started with blank tape, eventually write a~$1$ somewhere
  on the tape is undecidable.
\end{exercise}

\begin{exercise}[HMU~9.3.5]
  Let~$L$ be the language consisting of pairs of~TM codes plus an integer~$(M_1,M_2,k)$ such that~$L(M_1)\cap
  L(M_2)$ contains at least~$k$ strings. Show that~$L$ is recursively enumerable, but not recursive.
\end{exercise}

\end{document}
