\documentstyle[12pt]{article}

\pagestyle{myheadings}
\def\headlineaux{\sc Math 688: Theory of Computability and Complexity\hrulefill}
\markboth{\headlineaux}{\headlineaux}


\begin{document}
\begin{titlepage}\begin{centerline}{\Huge \framebox{Burton Rosenberg}}
\end{centerline}\end{titlepage}

\section*{Midterm \hfill{\parbox{3in}
    {\small\sc\begin{flushright} October 20, 1992. 5:30--8:00 PM\end{flushright}}
}}

There are seven problems for a total of 100 points.
Good luck.
\\[.5in]
{\Large Name: \hrulefill}
\\[.5in]

\center{
{\Large
\begin{tabular}{c|c}
Problem & Credit \\ \hline\hline
 1 & \\ \hline 2 & \\ \hline 3 & \\ \hline
 4 & \\ \hline 5 & \\ \hline 6 & \\ \hline
 7 & \\ \hline 
 \hline Total & \end{tabular} }}

\begin{enumerate}

\newpage
\item{\samepage (10 Points.)

Are there more numbers than even numbers? To resolve this, either
find a bijection between the naturals $\{\,0, 1, 2, \ldots\,\}$
and the even, positive numbers $\{\,0, 2, 4, \ldots\,\}$ or prove
that none exists. What does this mean for the cardinality of the
two sets: the set of naturals and the set of even naturals?
}

\newpage
\item{\samepage (10 Points.)

Consider the following function:
\[ f(n) = \left\{\begin{array}{ll} n/3 & \mbox{if $n$ is divisible by $3$,}\\
            \bot & \mbox{else.} \\ \end{array}\right. \]
Give two different {\em total} functions $g_1$ and $g_2$ defined $N\rightarrow N$ which
are extensions of $f$.
}

\newpage
\item{\samepage (20 Points.)
\newcommand{\chkbox}{\framebox{\phantom{M}}}

For each of the following mark ``u'' if the set is uncountable, 
``c'' if it is countable.
\begin{itemize}
\item[\chkbox] The set of all real numbers.
\item[\chkbox] The set of all integers, both positive and negative.
\item[\chkbox] Fix a real $\epsilon>0$, positive but no matter how small. 
The set of all reals in the interval $[1, 1+\epsilon]$.
\item[\chkbox] The set of all subsets of the natural numbers.
\item[\chkbox] The set of all {\em finite} subset of the natural numbers.
\end{itemize}
}

\newpage
\item{\samepage (15 Points.)

Prove: It is undecidable whether an arbitrary while-program halts on some 
input value. I.e., the following function is not computable:
\[ f(i) = \left\{\begin{array}{ll} 1, & \mbox{if DOM$(\varphi_i)\ne\emptyset$;}\\
         0, & \mbox{otherwise,} \\ \end{array} \right. \]
where $\varphi_i$ is the $i$-th computable unary function in our standard enumeration.
}

\newpage
\item{\samepage (15 Points.)

Write a while-program which computes the maximum of two numbers. I.e., the program
moves to X1 the larger of the values in X1 and X2:
\[ \mbox{X1 := max( X1, X2 )} \]
Use no macros!
}

\newpage
\item{\samepage (15 Points.)

We define a new binary operation on functions, called {\em meet}. Given two
partial functions $f$ and $g$, the meet of $f$ and $g$, $f\wedge g$, is the 
largest partial function $h$ such that $h\le f$ and $h\le g$.
That is, if $h'$ is another partial function such that $h'\le f$
and $h'\le g$, then $h'\le h$. In fact,
\[ (f\wedge g)(i) = \left\{ \begin{array}{ll} f(i)\mbox{ or }g(i) &
     \mbox{when both are defined and equal,} \\
                   \bot & \mbox{elsewise.} \\ \end{array} \right. \]
Show that if $f$ and $g$ are computable, then $f\wedge g$ is computable.
}

\newpage
\item{\samepage (15 Points.)

Use Church's Thesis to give an informal but rigorous argument that if a set of
numbers cannot be effectively generated, then it is undecidable whether an arbitrary
number is in the set.
}
\end{enumerate}
\end{document}