\documentclass{article}
\usepackage{graphics}
\usepackage{fancyhdr}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[topbottom,singlearrows]{../logicsym}
\usepackage{multicol}
\usepackage{alltt}


\newcommand{\coursenumber}{081}
\newcommand{\coursetitle}{Computability and Logic}

\topmargin  18pt  	% 27pt
\headheight 12pt  	% 12pt
\headsep    35pt 	% 45pt
\textheight 8.0in
\textwidth  6.2in

\oddsidemargin   22pt      % Left margin on odd-numbered pages.
\evensidemargin  22pt      % Left margin on even-numbered pages.
\marginparwidth  72pt       % Width of marginal notes.
\marginparsep    11pt      % Horizontal space between outer margin and 
                           % marginal note

\pagestyle{fancy}
\lhead{CSCI \coursenumber}
\chead{}
\rhead{\semester}
\lfoot{}
\cfoot{\thepage}
\rfoot{}
\renewcommand{\headrulewidth}{0pt}
\renewcommand{\footrulewidth}{0pt}
\newcommand{\semester}[0]{
     \ifnum\month>7{Fall}\fi
     \ifnum\month<8{Spring}\fi\  \number\year
}

\begin{document}

\begin{center}{\Large Homework 11}\\ \vspace{1 ex} Due midnight,
Thursday, 4/23/2015 \end{center}

\vspace{2 ex}
\noindent

Please submit your homework solutions online at  
\texttt{http://www.dci.pomona.edu/tools-bin/cs081upload.php}.  If you 
have more than one file to be turned in, please put it in a folder 
and zip it up before turning it in.

\vspace{2 ex}

\begin{enumerate}
    
    \item (10 points) \textbf{Decidability}
    
    Recall that $L^{*}$ is defined as $\{w_{1}\ldots w_{n}\ |\ \forall 1 
    \leq i \leq n, w_{i} \in L\}$
    
    \begin{enumerate}
	\item Assume $L$ is a decidable language.  Show that $L^{*}$ is also 
	decidable.
    
	\item Assume $L$ is a semi-decidable language.  Show that
	$L^{*}$ is also semi-decidable.
    
    \end{enumerate}
    
    \item (5 points) \textbf{Trick question!}
    
    Is there a Turing machine $M$ satisfying the following condition?
    \begin{itemize}
	\item[]
	The machine $M$ halts on each input word $w$, and it accepts
	the word $w$ if and only if there is a proof of
	$P=\mathit{NP}$.
    \end{itemize}
    
    \item (10 points) \textbf{Decidability}
    
    A language $L$ is \emph{co-semi-decidable} if its complement
    $\overline L$ is semi-decidable.  Let $A$ and $B$ be disjoint
    co-semi-decidable languages.  Show that there is a decidable
    language $S$ such that $A\subseteq S$ and $B\subseteq \overline
    S$.  Hint:  Think about the value of $\overline A \cup \overline 
    B$ and how you can use that to get a decidable language 
    satisfying the given constraints.

    \item (10 points) \textbf{Reduction}
    
    Prove that the following question is undecidable.  Given a Turing
    machine $M$, is $L(M)$ finite?  (Do not use Rice's Theorem in your proof.)
    
    \item (10 points) \textbf{Reduction}
    
    One of the following sets is semi-decidable, and the other is not.
    Which is which?  Give proofs for both.
    \begin{enumerate}
	\item
	$\{M\mid\textrm{$L(M)$ contains at least 481 elements}\}$

	\item
	$\{M\mid\textrm{$L(M)$ contains at most 480 elements}\}$
    \end{enumerate}
    Hint: Recall that a set is decidable if and only if both it and
    its complement are semi-decidable.  Use the contrapositive to 
    show one of these is not semi-decidable.  (Do not use Rice's 
    Theorem in your proof.)
\end{enumerate}

\end{document}
