\documentstyle[makeidx]{article}
\makeindex
%\setlength{\oddsidemargin}{.5in}
%\setlength{\evensidemargin}{.5in}
%\setlength{\textwidth}{5.8in}
\begin{document}
%\setlength{\parindent}{0pt}
%\newcounter{bean}
%\begin{list}{\arabic{bean}.}{\usecounter{bean}\setlength{\leftmargin}{0pt}\setlength{\rightmargin}{0pt}\setlength{\listparindent}{20pt}\setlength{\parsep}{5pt}}
%\item[]

\begin{verbatim}#|

 Copyright (C) 1994 by Robert S. Boyer and J Strother Moore.  All Rights
 Reserved.

 This script is hereby placed in the public domain, and therefore unlimited
 editing and redistribution is permitted.

 NO WARRANTY

 Robert S. Boyer and J Strother Moore PROVIDE ABSOLUTELY NO WARRANTY.  THE
 EVENT SCRIPT IS PROVIDED "AS IS" WITHOUT WARRANTY OF ANY KIND, EITHER EXPRESS
 OR IMPLIED, INCLUDING, BUT NOT LIMITED TO, ANY IMPLIED WARRANTIES OF
 MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.  THE ENTIRE RISK AS TO
 THE QUALITY AND PERFORMANCE OF THE SCRIPT IS WITH YOU.  SHOULD THE SCRIPT
 PROVE DEFECTIVE, YOU ASSUME THE COST OF ALL NECESSARY SERVICING, REPAIR OR
 CORRECTION.

 IN NO EVENT WILL Robert S. Boyer or J Strother Moore BE LIABLE TO YOU FOR ANY
 DAMAGES, ANY LOST PROFITS, LOST MONIES, OR OTHER SPECIAL, INCIDENTAL OR
 CONSEQUENTIAL DAMAGES ARISING OUT OF THE USE OR INABILITY TO USE THIS SCRIPT
 (INCLUDING BUT NOT LIMITED TO LOSS OF DATA OR DATA BEING RENDERED INACCURATE
 OR LOSSES SUSTAINED BY THIRD PARTIES), EVEN IF YOU HAVE ADVISED US OF THE
 POSSIBILITY OF SUCH DAMAGES, OR FOR ANY CLAIM BY ANY OTHER PARTY.

|#

\end{verbatim}
\noindent{\sc Event}:   Start with the initial {\bf nqthm} theory.

\addvspace{18pt}

\noindent{\sc Event}:   For efficiency, compile those definitions not yet compiled.

\addvspace{18pt}

\noindent{\sc Event}:   Add the shell {\it{btm\/}}\index{btm}, with recognizer function symbol {\it{btmp\/}} and no accessors.

\addvspace{18pt}
\begin{tabbing}{\sc Definition}:\index{get} \\  
\=\+{\rm{get}}\,({\it{x\/}}, {\it{alist\/}})\index{get} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{alist\/}} $\simeq\;${{\bf{nil}}}${}$$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf elseif }{\it{x\/}} $=$ {\rm{caar}}\,({\it{alist\/}})$\;\;${\bf then }{\rm{cdar}}\,({\it{alist\/}}) \\ 
{\bf else }{\rm{get}}\,({\it{x\/}}, {\rm{cdr}}\,({\it{alist\/}}))\index{get}$\;${\bf  endif}\-\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{unsolv-subrp} \\  
\=\+{\rm{unsolv-subrp}}\,({\it{fn\/}})\index{unsolv-subrp} \\ 
$=$$\;\;\;\;$({\it{fn\/}} $\in$ {\tt{'}}{\tt{(}}\=\+{\tt{zero}}{\tt{ }}{\tt{true}}{\tt{ }}{\tt{false}}{\tt{ }}{\tt{add1}}{\tt{ }}{\tt{sub1}}{\tt{ }}{\tt{numberp}}{\tt{ }}{\tt{cons}}{\tt{ }}{\tt{car}}{\tt{ }}{\tt{cdr}} \\ 
{\tt{listp}}{\tt{ }}{\tt{pack}}{\tt{ }}{\tt{unpack}}{\tt{ }}{\tt{litatom}}{\tt{ }}{\tt{equal}}{\tt{ }}{\tt{list}}{\tt{)}}\-)\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{unsolv-apply-subr} \\  
\=\+{\rm{unsolv-apply-subr}}\,({\it{fn\/}}, {\it{lst\/}})\index{unsolv-apply-subr} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{fn\/}} $=$ {\tt{'}}{\tt{zero}}$\;\;${\bf then }{\sc{zero}} \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{true}}$\;\;${\bf then }{\sc{true}} \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{false}}$\;\;${\bf then }{\sc{false}} \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{add1}}$\;\;${\bf then }$1\;+$ {\rm{car}}\,({\it{lst\/}}) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{sub1}}$\;\;${\bf then }{\rm{car}}\,({\it{lst\/}}) $-\;1$ \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{numberp}}$\;\;${\bf then }{\rm{car}}\,({\it{lst\/}}) $\in\;${\bf{N}}${}$ \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{cons}}$\;\;${\bf then }{\rm{cons}}\,({\rm{car}}\,({\it{lst\/}}), {\rm{cadr}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{list}}$\;\;${\bf then }{\it{lst\/}} \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{car}}$\;\;${\bf then }{\rm{car}}\,({\rm{car}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{cdr}}$\;\;${\bf then }{\rm{cdr}}\,({\rm{car}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{listp}}$\;\;${\bf then }{\rm{listp}}\,({\rm{car}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{pack}}$\;\;${\bf then }{\rm{pack}}\,({\rm{car}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{unpack}}$\;\;${\bf then }{\rm{unpack}}\,({\rm{car}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{litatom}}$\;\;${\bf then }{\rm{litatom}}\,({\rm{car}}\,({\it{lst\/}})) \\ 
{\bf elseif }{\it{fn\/}} $=$ {\tt{'}}{\tt{equal}}$\;\;${\bf then }{\rm{car}}\,({\it{lst\/}}) $=$ {\rm{cadr}}\,({\it{lst\/}}) \\ 
{\bf else }{\tt{0}}$\;${\bf  endif}\-\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{ev} \\  
\=\+{\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{flg\/}} $=$ {\tt{'}}{\tt{al}} \\ 
{\bf then }\=\+{\bf if }{\it{x\/}} $\simeq\;${{\bf{nil}}}${}$ \\ 
{\bf then }\=\+{\bf if }{\it{x\/}} $\in\;${\bf{N}}${}$$\;\;${\bf then }{\it{x\/}} \\ 
{\bf elseif }{\it{x\/}} $=$ {\tt{'}}{\tt{t}}$\;\;${\bf then }{\bf{t}} \\ 
{\bf elseif }{\it{x\/}} $=$ {\tt{'}}{\tt{f}}$\;\;${\bf then }{\bf{f}} \\ 
{\bf elseif }{\it{x\/}} $=$ {\bf{nil}}$\;\;${\bf then }{\bf{nil}} \\ 
{\bf else }{\rm{get}}\,({\it{x\/}}, {\it{va\/}})\index{get}$\;${\bf  endif}\- \\ 
{\bf elseif }{\rm{car}}\,({\it{x\/}}) $=$ {\tt{'}}{\tt{quote}}$\;\;${\bf then }{\rm{cadr}}\,({\it{x\/}}) \\ 
{\bf elseif }{\rm{car}}\,({\it{x\/}}) $=$ {\tt{'}}{\tt{if}} \\ 
{\bf then }\=\+{\bf if }{\rm{btmp}}\,({\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{cadr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{btmp}$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf elseif }{\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{cadr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev} \\ 
{\bf then }{\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{caddr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev} \\ 
{\bf else }{\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{cadddr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev}$\;${\bf  endif}\- \\ 
{\bf elseif }{\rm{btmp}}\,({\rm{ev}}\,({\tt{'}}{\tt{list}}, {\rm{cdr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{btmp}$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf elseif }{\rm{unsolv-subrp}}\,({\rm{car}}\,({\it{x\/}}))\index{unsolv-subrp} \\ 
{\bf then }{\rm{unsolv-apply-subr}}\,({\rm{car}}\,({\it{x\/}}), {\rm{ev}}\,({\tt{'}}{\tt{list}}, {\rm{cdr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{unsolv-apply-subr} \\ 
{\bf elseif }{\rm{btmp}}\,({\rm{get}}\,({\rm{car}}\,({\it{x\/}}), {\it{fa\/}})\index{get})\index{btmp}$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf elseif }{\it{n\/}} $\simeq {\tt{0}}$$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf else }{\rm{ev}}\,(\=\+{\tt{'}}{\tt{al}}, \\ 
{\rm{cadr}}\,({\rm{get}}\,({\rm{car}}\,({\it{x\/}}), {\it{fa\/}})\index{get}), \\ 
{\rm{pairlist}}\,(\=\+{\rm{car}}\,({\rm{get}}\,({\rm{car}}\,({\it{x\/}}), {\it{fa\/}})\index{get}), \\ 
{\rm{ev}}\,({\tt{'}}{\tt{list}}, {\rm{cdr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\-, \\ 
{\it{fa\/}}, \\ 
{\it{n\/}} $-\;1$)\-\index{ev}$\;${\bf  endif}\- \\ 
{\bf elseif }{\rm{listp}}\,({\it{x\/}}) \\ 
{\bf then }\=\+{\bf if }{\rm{btmp}}\,({\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{car}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{btmp}$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf elseif }{\rm{btmp}}\,({\rm{ev}}\,({\tt{'}}{\tt{list}}, {\rm{cdr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{btmp}$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf else }{\rm{cons}}\,(\=\+{\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{car}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev}, \\ 
{\rm{ev}}\,({\tt{'}}{\tt{list}}, {\rm{cdr}}\,({\it{x\/}}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\-$\;${\bf  endif}\- \\ 
{\bf else }{\bf{nil}}$\;${\bf  endif}\-\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{pr-eval}$\;\;$
{\rm{pr-eval}}\,({\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{pr-eval} $=$ {\rm{ev}}\,({\tt{'}}{\tt{al}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev}
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{evlist}$\;\;$
{\rm{evlist}}\,({\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{evlist} $=$ {\rm{ev}}\,({\tt{'}}{\tt{list}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev}
\end{tabbing}

\begin{verbatim};   We now define the functions x, va, fa, and k. To do so we first define
;   SUBLIS, which applies a substitution to an s-expression.  Then we use the
;   names CIRC and LOOP in the definitions of x and fa and use SUBLIS to
;   replace those names with "new" names. It is not important whether we have
;   defined this notion of substitution correctly, since all that is required
;   is that we exhibit some x, va, fa, and k with the desired properties.

\end{verbatim}\begin{tabbing}{\sc Definition}:\index{sublis} \\  
\=\+{\rm{sublis}}\,({\it{alist\/}}, {\it{x\/}})\index{sublis} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{x\/}} $\simeq\;${{\bf{nil}}}${}$ \\ 
{\bf then }\=\+{\bf if }{\rm{assoc}}\,({\it{x\/}}, {\it{alist\/}})$\;\;${\bf then }{\rm{cdr}}\,({\rm{assoc}}\,({\it{x\/}}, {\it{alist\/}})) \\ 
{\bf else }{\it{x\/}}$\;${\bf  endif}\- \\ 
{\bf else }{\rm{cons}}\,({\rm{sublis}}\,({\it{alist\/}}, {\rm{car}}\,({\it{x\/}}))\index{sublis}, {\rm{sublis}}\,({\it{alist\/}}, {\rm{cdr}}\,({\it{x\/}}))\index{sublis})$\;${\bf  endif}\-\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{x} \\  
{\rm{x}}\,({\it{fa\/}})\index{x} $=$ {\rm{sublis}}\,({\rm{list}}\,({\rm{cons}}\,({\tt{'}}{\tt{circ}}, {\rm{cons}}\,({\it{fa\/}}, {\tt{0}}))), {\tt{'}}{\tt{(}}{\tt{circ}}{\tt{ }}{\tt{a}}{\tt{)}})\index{sublis}
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{fa} \\  
\=\+{\rm{fa}}\,({\it{fa\/}})\index{fa} \\ 
$=$$\;\;\;\;${\rm{append}}\,(\=\+{\rm{sublis}}\,(\=\+{\rm{list}}\,({\rm{cons}}\,({\tt{'}}{\tt{circ}}, {\rm{cons}}\,({\it{fa\/}}, {\tt{0}})), {\rm{cons}}\,({\tt{'}}{\tt{loop}}, {\rm{cons}}\,({\it{fa\/}}, {\tt{1}}))), \\ 
{\tt{'}}{\tt{(}}\=\+{\tt{(}}\=\+{\tt{circ}} \\ 
{\tt{(}}{\tt{a}}{\tt{)}} \\ 
{\tt{(}}\=\+{\tt{if}} \\ 
{\tt{(}}{\tt{halts}}{\tt{ }}{\tt{'}}{\tt{(}}{\tt{circ}}{\tt{ }}{\tt{a}}{\tt{)}}{\tt{ }}{\tt{(}}{\tt{list}}{\tt{ }}{\tt{(}}{\tt{cons}}{\tt{ }}{\tt{'}}{\tt{a}}{\tt{ }}{\tt{a}}{\tt{)}}{\tt{)}}{\tt{ }}{\tt{a}}{\tt{)}} \\ 
{\tt{(}}{\tt{loop}}{\tt{)}} \\ 
{\tt{t}}{\tt{)}}\-{\tt{)}}\- \\ 
{\tt{(}}{\tt{loop}}{\tt{ }}{\tt{nil}}{\tt{ }}{\tt{(}}{\tt{loop}}{\tt{)}}{\tt{)}}{\tt{)}}\-)\-\index{sublis}, \\ 
{\it{fa\/}})\-\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{va}$\;\;$
{\rm{va}}\,({\it{fa\/}})\index{va} $=$ {\rm{list}}\,({\rm{cons}}\,({\tt{'}}{\tt{a}}, {\rm{fa}}\,({\it{fa\/}})\index{fa}))
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{k}$\;\;$
{\rm{k}}\,({\it{n\/}})\index{k} $=$ ($1\;+$ {\it{n\/}})
\end{tabbing}

\begin{verbatim};   We wish to prove that having "new" program names in the function
;   environment does not effect the computation of the body of HALTS.  To state
;   this we must first define formally what we mean by "new". Then we will
;   prove the general result we need and then we will instantiate it for the
;   particular "new" program names we choose.

\end{verbatim}\begin{tabbing}{\sc Definition}:\index{occur} \\  
\=\+{\rm{occur}}\,({\it{x\/}}, {\it{y\/}})\index{occur} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{x\/}} $=$ {\it{y\/}}$\;\;${\bf then }{\bf{t}} \\ 
{\bf elseif }{\it{y\/}} $\simeq\;${{\bf{nil}}}${}$$\;\;${\bf then }{\bf{f}} \\ 
{\bf else }{\rm{occur}}\,({\it{x\/}}, {\rm{car}}\,({\it{y\/}}))\index{occur} $\vee$ {\rm{occur}}\,({\it{x\/}}, {\rm{cdr}}\,({\it{y\/}}))\index{occur}$\;${\bf  endif}\-\-
\end{tabbing}
\begin{tabbing}{\sc Definition}:\index{occur-in-defns} \\  
\=\+{\rm{occur-in-defns}}\,({\it{x\/}}, {\it{lst\/}})\index{occur-in-defns} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{lst\/}} $\simeq\;${{\bf{nil}}}${}$$\;\;${\bf then }{\bf{f}} \\ 
{\bf else }{\rm{occur}}\,({\it{x\/}}, {\rm{caddr}}\,({\rm{car}}\,({\it{lst\/}})))\index{occur} $\vee$ {\rm{occur-in-defns}}\,({\it{x\/}}, {\rm{cdr}}\,({\it{lst\/}}))\index{occur-in-defns}$\;${\bf  endif}\-\-
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  occur-occur-in-defns \\ \index{occur-occur-in-defns}
\=\+(($\neg$ {\rm{occur-in-defns}}\,({\it{fn\/}}, {\it{fa\/}})\index{occur-in-defns}) $\wedge$ ($\neg$ {\rm{btmp}}\,({\rm{get}}\,({\it{x\/}}, {\it{fa\/}})\index{get})\index{btmp})) \\ 
$\rightarrow$$\;\;\;\;$($\neg$ {\rm{occur}}\,({\it{fn\/}}, {\rm{cadr}}\,({\rm{get}}\,({\it{x\/}}, {\it{fa\/}})\index{get}))\index{occur})\-
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  lemma1 \\ \index{lemma1}
\=\+(($\neg$ {\rm{occur}}\,({\it{fn\/}}, {\it{x\/}})\index{occur}) $\wedge$ ($\neg$ {\rm{occur-in-defns}}\,({\it{fn\/}}, {\it{fa\/}})\index{occur-in-defns})) \\ 
$\rightarrow$$\;\;\;\;$({\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\rm{cons}}\,({\rm{cons}}\,({\it{fn\/}}, {\it{def\/}}), {\it{fa\/}}), {\it{n\/}})\index{ev} $=$ {\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\-
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  count-occur \\ \index{count-occur}
({\rm{count}}\,({\it{y\/}}) $<$ {\rm{count}}\,({\it{x\/}})) $\rightarrow$ ($\neg$ {\rm{occur}}\,({\it{x\/}}, {\it{y\/}})\index{occur})
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  count-get \\ \index{count-get}
{\rm{count}}\,({\rm{cadr}}\,({\rm{get}}\,({\it{fn\/}}, {\it{fa\/}})\index{get})) $<$ ($1\;+$ {\rm{count}}\,({\it{fa\/}}))
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  count-occur-in-defns \\ \index{count-occur-in-defns}
({\rm{count}}\,({\it{fa\/}}) $<$ {\rm{count}}\,({\it{x\/}})) $\rightarrow$ ($\neg$ {\rm{occur-in-defns}}\,({\it{x\/}}, {\it{fa\/}})\index{occur-in-defns})
\end{tabbing}

\begin{tabbing}{\sc Theorem}:  corollary1 \\ \index{corollary1}
\=\+{\rm{ev}}\,(\=\+{\tt{'}}{\tt{al}}, \\ 
{\rm{cadr}}\,({\rm{get}}\,({\tt{'}}{\tt{halts}}, {\it{fa\/}})\index{get}), \\ 
{\it{va\/}}, \\ 
{\rm{cons}}\,(\=\+{\rm{cons}}\,({\rm{cons}}\,({\it{fa\/}}, {\tt{0}}), {\it{def0\/}}), \\ 
{\rm{cons}}\,({\rm{list}}\,({\rm{cons}}\,({\it{fa\/}}, {\tt{1}}), {\bf{nil}}, {\rm{list}}\,({\rm{cons}}\,({\it{fa\/}}, {\tt{1}}))), {\it{fa\/}}))\-, \\ 
{\it{n\/}})\-\index{ev} \\ 
$=$$\;\;\;\;${\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{cadr}}\,({\rm{get}}\,({\tt{'}}{\tt{halts}}, {\it{fa\/}})\index{get}), {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev}\-
\end{tabbing}

\noindent{\sc Event}:   Disable lemma1.

\addvspace{18pt}
\begin{tabbing}{\sc Theorem}:  lemma2 \\ \index{lemma2}
\=\+(($\neg$ {\rm{btmp}}\,({\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{btmp}) $\wedge$ ($\neg$ {\rm{btmp}}\,({\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{k\/}})\index{ev})\index{btmp})) \\ 
$\rightarrow$$\;\;\;\;$({\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev} $=$ {\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{k\/}})\index{ev})\-
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  corollary2 \\ \index{corollary2}
({\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev} $=$ {\bf{t}}) $\rightarrow$ {\rm{ev}}\,({\it{flg\/}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{k\/}})\index{ev}
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  lemma3 \\ \index{lemma3}
\=\+(\=\+{\rm{listp}}\,({\it{x\/}}) \\ 
$\wedge$$\;\;\;\;${\rm{listp}}\,({\rm{car}}\,({\it{x\/}})) \\ 
$\wedge$$\;\;\;\;$({\rm{cdr}}\,({\it{x\/}}) $\simeq\;${{\bf{nil}}}${}$) \\ 
$\wedge$$\;\;\;\;${\rm{listp}}\,({\rm{get}}\,({\rm{car}}\,({\it{x\/}}), {\it{fa\/}})\index{get}) \\ 
$\wedge$$\;\;\;\;$({\rm{car}}\,({\rm{get}}\,({\rm{car}}\,({\it{x\/}}), {\it{fa\/}})\index{get}) $=$ {\bf{nil}}) \\ 
$\wedge$$\;\;\;\;$({\rm{cadr}}\,({\rm{get}}\,({\rm{car}}\,({\it{x\/}}), {\it{fa\/}})\index{get}) $=$ {\it{x\/}}))\- \\ 
$\rightarrow$$\;\;\;\;${\rm{btmp}}\,({\rm{ev}}\,({\tt{'}}{\tt{al}}, {\it{x\/}}, {\it{va\/}}, {\it{fa\/}}, {\it{n\/}})\index{ev})\index{btmp}\-
\end{tabbing}
\begin{tabbing}{\sc Theorem}:  expand-circ \\ \index{expand-circ}
\=\+(($\neg$ {\rm{btmp}}\,({\it{val\/}})\index{btmp}) $\wedge$ ($\neg$ {\rm{btmp}}\,({\rm{get}}\,({\rm{cons}}\,({\it{fn\/}}, {\tt{0}}), {\it{fa\/}})\index{get})\index{btmp})) \\ 
$\rightarrow$$\;\;\;\;$(\=\+{\rm{ev}}\,({\tt{'}}{\tt{al}}, {\rm{cons}}\,({\rm{cons}}\,({\it{fn\/}}, {\tt{0}}), {\tt{'}}{\tt{(}}{\tt{a}}{\tt{)}}), {\rm{list}}\,({\rm{cons}}\,({\tt{'}}{\tt{a}}, {\it{val\/}})), {\it{fa\/}}, {\it{j\/}})\index{ev} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{j\/}} $\simeq {\tt{0}}$$\;\;${\bf then }{\sc{btm}}\index{btm} \\ 
{\bf else }{\rm{ev}}\,(\=\+{\tt{'}}{\tt{al}}, \\ 
{\rm{cadr}}\,({\rm{get}}\,({\rm{cons}}\,({\it{fn\/}}, {\tt{0}}), {\it{fa\/}})\index{get}), \\ 
{\rm{pairlist}}\,(\=\+{\rm{car}}\,({\rm{get}}\,({\rm{cons}}\,({\it{fn\/}}, {\tt{0}}), {\it{fa\/}})\index{get}), \\ 
{\rm{ev}}\,(\=\+{\tt{'}}{\tt{list}}, \\ 
{\tt{'}}{\tt{(}}{\tt{a}}{\tt{)}}, \\ 
{\rm{list}}\,({\rm{cons}}\,({\tt{'}}{\tt{a}}, {\it{val\/}})), \\ 
{\it{fa\/}}, \\ 
{\it{j\/}})\-\index{ev})\-, \\ 
{\it{fa\/}}, \\ 
{\it{j\/}} $-\;1$)\-\index{ev}$\;${\bf  endif}\-)\-\-
\end{tabbing}

\begin{verbatim};   After we published a proof of the unsolvability of the halting problem in
;   the JACM, a student in one of our classes named Jonathan Bellin observed
;   that one could get a trivial proof by defining (x FA) = (BTM).  However,
;   the "idea" is that the frustrating values (x FA), (va FA), and (fa FA) are
;   supposed to be objects on which EVAL behaves normally.  This class consists
;   of those objects for which SEXP, defined below is, true.  So we added the
;   second conjunct to our statement of UNSOLVABILITY-OF-THE-HALTING-PROBLEM.

\end{verbatim}\begin{tabbing}{\sc Definition}:\index{sexp} \\  
\=\+{\rm{sexp}}\,({\it{x\/}})\index{sexp} \\ 
$=$$\;\;\;\;$\=\+{\bf if }{\it{x\/}} $=$ {\bf{t}}$\;\;${\bf then }{\bf{t}} \\ 
{\bf elseif }{\it{x\/}} $=$ {\bf{f}}$\;\;${\bf then }{\bf{t}} \\ 
{\bf elseif }{\it{x\/}} $\in\;${\bf{N}}${}$$\;\;${\bf then }{\bf{t}} \\ 
{\bf elseif }{\rm{listp}}\,({\it{x\/}})$\;\;${\bf then }{\rm{sexp}}\,({\rm{car}}\,({\it{x\/}}))\index{sexp} $\wedge$ {\rm{sexp}}\,({\rm{cdr}}\,({\it{x\/}}))\index{sexp} \\ 
{\bf elseif }{\rm{litatom}}\,({\it{x\/}})$\;\;${\bf then }{\rm{sexp}}\,({\rm{unpack}}\,({\it{x\/}}))\index{sexp} \\ 
{\bf else }{\bf{f}}$\;${\bf  endif}\-\-
\end{tabbing}

\begin{tabbing}{\sc Theorem}:  unsolvability-of-the-halting-problem \\ \index{unsolvability-of-the-halting-pr!oblem}
\=\+(\=\+({\it{h\/}} $=$ {\rm{pr-eval}}\,(\=\+{\rm{list}}\,(\=\+{\tt{'}}{\tt{halts}}, \\ 
{\rm{list}}\,({\tt{'}}{\tt{quote}}, {\rm{x}}\,({\it{fa\/}})\index{x}), \\ 
{\rm{list}}\,({\tt{'}}{\tt{quote}}, {\rm{va}}\,({\it{fa\/}})\index{va}), \\ 
{\rm{list}}\,({\tt{'}}{\tt{quote}}, {\rm{fa}}\,({\it{fa\/}})\index{fa}))\-, \\ 
{\bf{nil}}, \\ 
{\it{fa\/}}, \\ 
{\it{n\/}})\-\index{pr-eval}) \\ 
$\rightarrow$$\;\;\;\;$(\=\+(({\it{h\/}} $=$ {\bf{f}}) $\rightarrow$ ($\neg$ {\rm{btmp}}\,({\rm{pr-eval}}\,({\rm{x}}\,({\it{fa\/}})\index{x}, {\rm{va}}\,({\it{fa\/}})\index{va}, {\rm{fa}}\,({\it{fa\/}})\index{fa}, {\rm{k}}\,({\it{n\/}})\index{k})\index{pr-eval})\index{btmp})) \\ 
$\wedge$$\;\;\;\;$(({\it{h\/}} $=$ {\bf{t}}) $\rightarrow$ {\rm{btmp}}\,({\rm{pr-eval}}\,({\rm{x}}\,({\it{fa\/}})\index{x}, {\rm{va}}\,({\it{fa\/}})\index{va}, {\rm{fa}}\,({\it{fa\/}})\index{fa}, {\it{k\/}})\index{pr-eval})\index{btmp}))\-)\- \\ 
$\wedge$$\;\;\;\;$({\rm{sexp}}\,({\it{fa\/}})\index{sexp} $\rightarrow$ ({\rm{sexp}}\,({\rm{x}}\,({\it{fa\/}})\index{x})\index{sexp} $\wedge$ {\rm{sexp}}\,({\rm{va}}\,({\it{fa\/}})\index{va})\index{sexp} $\wedge$ {\rm{sexp}}\,({\rm{fa}}\,({\it{fa\/}})\index{fa})\index{sexp}))\-
\end{tabbing}


\noindent{\sc Event}:   Make the library {\tt{"unsolv"}} and compile it.

\addvspace{18pt}

%\end{list}
\printindex
\end{document}
