\documentstyle[12pt]{article}

\hyphenation{stack}

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

\newcommand{\naturals}{\mbox{\bf N}}

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

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

There are five 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
 \hline Total & \end{tabular} }}

\begin{enumerate}

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

Consider a program which plays tick-tack-toe. One can encode a
game board $B$ as follows. There are nine boxes in tick-tack-toe which we
will number $i=0,\ldots,8$. Define function $\tau$ which takes board $B$
and integer $i$ and equals,
\[ \tau(B,i) = \left\{ \begin{array}{ll} 1 & \mbox{if
box $i$ is empty in board $B$}, \\
2  & \mbox{if box $i$ has an {\em X} in board $B$},\\
3 & \mbox{if box $i$ has an {\em O} in board $B$}.
  \end{array} \right. \]
The game board is then represented as,
\[ \sigma(B) = \prod_{i=0}^8 pr(i)^{\tau(B,i)}. \]
Consider the function $f:\naturals\rightarrow\naturals$, 
\[  f(b) = \left\{ \begin{array}{ll} 1 & b = \sigma(B) \mbox{ and it is 
                      possible for X to win given board $B$.}\\
                      0 & \mbox{else} \end{array} \right. \]
Show that $f$ is primitive recursive. ({\sc Hint:} Loop-programs.)
}

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

Mark in each of the following boxes ``Y'' if the computation system
is equivalent in power
to while-programs, or ``N'' if it is less powerful.
\begin{itemize}
\item[\chkbox] Repeat-programs: These are while-programs except the basic
  control construction is {\em repeat ... until} rather than
  {\em while ...} . 
\item[\chkbox] A PS/2 computer whose FORTRAN, for reason of programming style, has 
forbidden the use of GOTO's. For our purposes, define FORTRAN as:
\begin{itemize}
\item Having all the usual arithmetic capabilities on an 
      infinite supply of integer variables.
\item Having an if-then construction of the form,
\begin{verbatim}
       IF (condition) THEN
          statements
       END IF
\end{verbatim}
\item Having a do-loop construction of the form,
\begin{verbatim}
       DO variable=initial,final,step
          statements
       END DO
\end{verbatim}
    The limits to the do-loop are fixed upon entry to the loop.
\item Having subroutine and functions calls only when they cannot
     result in recursion. (E.g. ``A'' calls ``B'' which calls ``A'' is not
     allowed.)
\end{itemize}
\item[\chkbox] A while-program whose arithmetic rules (set to zero, successor and
predecessor) have been replaced by the following string manipulation rules.
A variable can be initialized to the empty string, \verb.X:=''.. An ``a'' can be
appended to the string contained in a variable, \verb.X:=X||'a'.. Two strings
can be checked for unequal length. (The length of the empty string is zero.)
While and compound statements are as before.
\item[\chkbox] A Turing Machine whose tape is infinitely long {\em only in one direction}.
\end{itemize}
}


\newpage
\item{\samepage (20 Points.)
Show that the {\em Integer Programming Decision Problem} is in NP. (Do not
attempt to show it NP-complete!)

An instance of an Integer Programming Decision Problem is
given by a set of variables $\{\,X_1,\ldots,X_n\,\}$, a set
of linear equations using these variables, called the {\em constraints,}
\begin{eqnarray*}
    b_1 &\ge& a_{1,1} X_1 + a_{1,2} X_2 + \ldots + a_{1,n} X_n \\
    b_2 &\ge& a_{2,1} X_1 + a_{2,2} X_2 + \ldots + a_{2,n} X_n \\
    &\vdots& \\
    b_m &\ge& a_{m,1} X_1 + a_{m,2} X_2 + \ldots + a_{m,n} X_n,
\end{eqnarray*}
where all the $b_i$ and $a_{i,j}$ are integers,
a cost function, 
\[ c(X_1,\ldots,X_n) = c_1 X_1 + c_2 X_2 + \ldots + c_n X_n, \]
where all the $c_i$ are integers,
and an integer $B$. 

The decision problem is to answer Yes if there exists an assignment 
of {\em integers} to the $X_i$ such
that all of the constraints are true and the cost $c$ is greater or equal to $B$.

}


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

Give a bijection from pairs of integers to the naturals,
\[ \mu(i,j) = k, \;\; i,j \in {\bf Z},\; k \in\naturals.\]
({\sc Hint:} Use Kfoury, Moll and Arbib's pairing function
$\tau:\naturals^2\rightarrow\naturals$ and
build from there.)
}
\newpage
\item{\samepage (20 Points.)

If $f,g:\naturals\rightarrow\naturals$ are two functions, recall
that $f \ge g$ by extension ordering if,
\begin{enumerate}
\item The domain of definition of $f$ includes that of $g$, and,
\item for any $i$ in the domain of definition of $g$, $g(i)=f(i)$.
\end{enumerate}

The greatest-lower-bound of a 
family of partial functions 
\[  {\cal G} = \{ g_i:\naturals\rightarrow\naturals \,|\, i = 0, 1, \ldots\,\}\]
is a partial function $G$ such that,
\begin{enumerate}
\item $g_i\ge G$ for all $i$. (That is, $G$ is a lower bound of the $g_i$.)
\item For any other $G'$ such that $g_i\ge G'$ for
all $i$, $G\ge G'$. (That is, among all lower bounds for the $g_i$, $G$ is the
greatest.)
\end{enumerate}
Show that, under the assumption that the $g_i$ form a descending chain,
\[ g_0 \,\ge\, g_1\, \ge \,g_2\, \ge\, \ldots\,, \]
the greatest-lower-bound of family $\cal{G}$ exists.

Show that the greatest-lower-bound need not be computable even if all the $g_i$ are.
}

\end{enumerate}
\end{document}