\documentstyle[12pt]{report}
\pagestyle{myheadings}
\def\headlineaux{\sc Math 688: Theory of Computability and Complexity \hrulefill}
\markboth{\headlineaux}{\headlineaux}

\newcommand{\assignmentNumber}{4}
\newcommand{\outdate}{13 October, 1992}
\newcommand{\userEnter}[2]{\begin{itemize}\item[$>$]
   {\bf #1 } {\em #2}\end{itemize}}
\newcommand{\naturals}{\mbox{\bf N}}
\newcommand{\compose}{\circ}

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

\section*{Resume \hfill{\parbox{3in}
    {\small\sc\begin{flushright} Date: \outdate\end{flushright}}}}

\begin{enumerate}
\item
While-programs.
\begin{enumerate}
 \item Syntax.
  \item Macros, appropriate and inappropriate use of macros.
\item Variable relabeling.
\item Equivalence with other ``program forms''.
\end{enumerate}
\item Relationship between while-programs and functions.
\begin{enumerate}
  \item Partial functions, domain of definition and extension ordering.
  \item Input/output conventions for arity $k$ functions.
  \item Non-halting of a program versus undefinedness of a function.
  \item Church's thesis, the definition of a computable function.
  \item Are all functions computable?
\end{enumerate}
  \item Enumeration of computable functions.
\begin{enumerate}
\item Definition of countability: in bijection with the naturals.
\item Counting while-programs, encodings.
\item Introduction to uncountability.
\begin{enumerate}
\item The uncountability of the reals and of partial functions.
\item Cantor diagonalization.
\end{enumerate}
\item Cardinality argument for the existence of uncomputable functions.
\item The halting function is uncomputable.
\end{enumerate}
\item Universal Functions.
\begin{enumerate}
\item Program rewriting: the string operations head, tail and concatenation  as number-theoretic functions.
\item Syntax checking.
\item Simulation of unbounded memory.
\begin{enumerate}
\item Pairing functions: a bijection from pairs of naturals to the naturals.
\item Extensions of pairing functions to n-tuples and $\infty$-tuples of
finite support.
\end{enumerate}
\item The universal function is computable.
\end{enumerate}
%this is the second part of the course

\item[\bf -]{\bf Second Half of the Course.}
\item Recursion
\begin{enumerate}
\item Recursive programs are while-program computable.
\begin{enumerate}
\item Posets of functions by extension ordering and least-upper-bounds.
\item Recursive programs are least-upper-bounds.
\item Effective least-upper-bounds are computable.
\end{enumerate}
\item The Recursion Theorem, Section 6.1.
\end{enumerate}
\item Acceptable Programming Systems.
\begin{enumerate}
\item Roger's Isomorphism Theorem, Section 6.2.
\item Turing Machines.
\item Recursive Functions.
\begin{enumerate}
\item Primitive recursive functions and loop-programs.
\item Unbounded minimization and partial recursive functions.
\end{enumerate}
\item Undecidability of certain word problems.
\end{enumerate}
\item The Theory of NP-Completeness
\begin{enumerate}
\item Deterministic and Non-deterministic Turing machines.
\item Polynomial-time transformations. Classes P and NP.
\item SAT is NP-Complete.
\item Other NP-Complete problems.
\end{enumerate}
\end{enumerate}
\end{document}