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

\newcommand{\assignmentNumber}{4}
\newcommand{\outdate}{24 November, 1992}
\newcommand{\userEnter}[2]{\begin{itemize}\item[$>$]
   {\bf #1 } {\em #2}\end{itemize}}
\newcommand{\naturals}{\mbox{\bf N}}
\newcommand{\monus}{\stackrel{{}^{\scriptstyle .}}{\smash{-}}}
\newcommand{\compose}{\circ}

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

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

Errors and other suggestions for {\em A Programming Approach to Computability},
A.~J.~Kfoury, Robert~N.~Moll and Michael~A.~Arbib, published by Springer-Verlag.
\begin{enumerate}
\item Page 128. $\{A\}{\cal S}\{C\}$ in ``denominator'' of R3.
\item Page 250. Roger's Isomorphism.
\item Page 239. The definition of $\naturals$.
\item Page 85. First pred operator on the page should be \verb.X2:=pred(X1)..
\item Page 81. In the two instances of the $s^m_n:\naturals^{n+1}\rightarrow\naturals$
the exponent should be $m+1$.
\item Page 81. A better solution to the ``overwrite'' problem is the well known programmer's
trick:
\begin{verbatim}
       begin
          Xm+n := Xn ;
          Xm+n-1 := Xn-1 ;
          ...
          Xm+1 := X1 ;
          Xm := Ym ;
          ...
          X1 := Y1 ;
       end 
\end{verbatim}
\item Page 70. The subscript is wrong, it should read $\pi_2(\pi_1^{k-l}(i))$.
\item Page 24. The second flow diagram is different in two editions of the book.
In one, the leftmost branch returns to just above the first diamond, in the other,
it returns to the top.
\item Page 169. Problem 6b, typo {\em funcitons}.
\item Page 209. This definition of bounded minimization does not jive with exercise 9 of
section 2.3.
\item Page 30. An improvement is suggested: make explicit the following relations:
\begin{eqnarray*}  \min(x,y) &=& x \monus ( x \monus y ) \\
          \max(x,y) &=& x + ( y \monus x ) 
\end{eqnarray*} 
\item Page 207. First line after the first display. Close 
$succ(U^3_1(x_1,x_2,x_3)$.
\item Page 213. Missing parens around $n-1$ in the definition of $h$.
\item Page 210. Program for power has a bug for $m=1$.
\item Page 208. Choosing something other than naturals over
which to interpret variables might lead to partial primitive recursive functions(?).
Do the naturals have to be explicitly invoked somewhere?
\item Page 211. Definition 11 has too strong a requirement for $f(n)$. It must be total
else history is not defined. But if it must be primitive recursive, Theorem 12 is
pointless.
\item Page 211. Last sentence ``it gives us [a] primitive recursive
encoding for [a] finite sequence.''
\item Page 219. Picture in middle of page, one too many arrow-heads.
\item Page 240. $\alpha$ should be `$\alpha$`.
\item Page 221. Definition 23, require $n\ge 1$.
\item Page 106. Second line in the displayed derivation of $\xi_{n+1}$, $n+1$ must
be $n-1$.
\item Page 201. The start state is incorrect. Add $(q_s, B, B, R, q_0)$.
\item Page 222. The \verb.if Z <> 1. is unnecessary.
\item Page 222. What is $\pi_2(x)$ for $x$ undefined?
\item Page 232. Example 12 {\em is} ambiguous. Change S2 in S1 production
to S1.
\item Page 226. ``where $x$ and $y$ areunary encodings of $y$ and $y$''.
\item Page 205. $times(x,0)=x$.
\end{enumerate}
\end{document}
