\documentclass[10pt,letterpaper,unboxed,cm]{hmcpset}
\usepackage[margin=1in]{geometry}
\usepackage{graphicx, xcolor}
\usepackage{varwidth, multicol}
\pagestyle{empty}
\newcommand{\cmd}[1]{\texttt{\color{blue}{#1}}}
\newcommand{\blank}{\textvisiblespace}
\newcommand{\st}{~\mid~}
\name{}
\class{CSE 105}
\assignment{Group Homework 7}
\duedate{Due: {\bf Thursday March 15, 2018} at 11:00PM (on Gradescope)}
\begin{document}
\begin{center}
\begin{minipage}[t]{5.7in}
\rule{\linewidth}{2pt}
{\sc Instructions}\newline
{\bf One member} of the group should upload your group submission to Gradescope.
During the submission process, they will be prompted to add the names of the rest
of the group members.
All group members' names and PIDs
should be on {\bf each} page of the submission.\\
Your homework must be typed. Your assignments in this class will be evaluated not only on the correctness of your answers, but on your ability to present your ideas clearly and logically. You should always explain how you arrived at your conclusions, using mathematically sound reasoning.\\
{\sc Reading} Sipser Sections 4.2, 5.1
\newline
{\sc Key Concepts} Undecidable problems, recognizable and co-recognizable problems, reductions.
\newline
\rule{\linewidth}{2pt}
\end{minipage} \hfill
\end{center}
\problemlist{}
\begin{problem}[1.]{\bf (10 points)}
{\bf True/False} Briefly justify each answer:
\begin{enumerate}
\item[a.]
Every language reduces to its complement.
\item[b.]
For languages $A, B, C$ if $A$ reduces to $B$ and $B$ reduces to $C$,
then $A$ reduces to $C$.
\item[c.]
For languages $A, B$ if $A$ reduces to $B$ and $B$ reduces to $A$ then $A=B$.
\item[d.]
For languages $A, B$ if $A$ reduces to $B$ then $B$ reduces to $A$.
\end{enumerate}
{\it Recall} reduction is defined in section 5.1 (it is {\bf not the same} as the
$m$-reduction of later sections).
\end{problem}
\begin{problem}[2.] {\bf (10 points)} Prove that the computational
problem
\[
ALL_{TM} = \{ \langle M \rangle \st \text{$M$ is a Turing machine over $\Sigma$
and $L(M) = \Sigma^*$} \}
\]
is undecidable. {\it Hint: use reductions.}
\end{problem}
\begin{problem}[3.] {\bf (10 points)} Consider the following computational problems
(from this week's Individual HW)
\begin{align*}
Z_{TM} &= \{ \langle M \rangle ~|~ \text{$M$ is a Turing machine and $0 \in L(M)$\}} \\
T2_{TM} &= \{ \langle M \rangle ~|~ \text{$M$ is a Turing machine and $|L(M)| \geq 2$}\}
\end{align*}
Prove that $T2_{TM}$ reduces to $Z_{TM}$.
\end{problem}
\end{document}