\documentstyle[12pt]{article} % LaTeX README file
\begin{document}
\sloppy
\raggedbottom
\title
{\bf Exhibiting Randomness in Arithmetic using Mathematica \& C}
\author{\bf G. J. Chaitin}
\date{\it chaitin@watson.ibm.com} % June 4, 1993
\maketitle
In my book {\it Algorithmic Information Theory\/} I explain how I
constructed a million-character equation that proves that there is
randomness in arithmetic. My book only includes a few pages from the
monster equation, and omits the software used to construct it. This
software has now been rewritten in {\sl Mathematica}.
The {\sl Mathematica} software for my book, and its input, are here in
their entirety. The {\sl Mathematica} code is remarkably compact, but
it sometimes is slow. So one {\sl C} program plus equipment for
automatically generating another is also included in this software
package.
I used Version 2.1 of {\sl Mathematica} as described in the second
edition of Wolfram's book {\it Mathematica---A System for Doing
Mathematics by Computer,} running on an {\sl IBM RISC} System/6000
workstation.
Since the {\sl APL2} character set is not generally available, I
decided to change the symbols that denote the primitive functions in
the toy {\sl LISP} that I use in {\it Algorithmic Information Theory.}
There are seven different kinds of files:
\begin{itemize}
\item Included in this distribution:
\begin{enumerate}
\item {\tt *.m} files are {\sl Mathematica} code.
\item {\tt *.c} files are {\sl C} code.
\item {\tt *.lisp} files are toy {\sl LISP} code.
These are the four {\sl LISP} programs in my book
({\tt eval.lisp, eval2.lisp, eval3.lisp,} and {\tt omega.lisp}),
plus {\tt test.lisp}.
\item {\tt *.rm} are register machine code.
\end{enumerate}
\item These will produce:
\begin{itemize}
\item[\rm 5.] {\tt *.xrm} files are expanded register machine code
(lower level code than that in {\tt *.rm} files).
\item[\rm 6.] {\tt *.run, *.2run, *.srun, *.mrun, *.crun, *.cmrun} files
are the output from {\sl LISP} interpreter runs.
\item[\rm 7.] {\tt *.eq} files are exponential diophantine equations.
\end{itemize}
\end{itemize}
Six different {\sl LISP} interpreters are included here:
\begin{enumerate}
\item
{\tt lisp.m} is a {\sl LISP} interpreter written in nonprocedural {\sl
Mathematica} that uses {\sl Mathematica} list structures to represent
{\sl LISP} S-expressions. Bindings are kept in a fast look-up table.
{\tt lisp.m} converts an {\tt X.lisp} input file into an {\tt X.run}
output file.
\[
\mbox{\tt X.lisp}
\longrightarrow \fbox{\tt lisp.m} \longrightarrow
\mbox{\tt X.run}
\]
\item
{\tt lisp2.m} is a {\sl LISP} interpreter written in procedural {\sl
Mathematica} that uses {\sl Mathematica} list structures to
represent {\sl LISP} S-expressions. Bindings are kept in a fast
look-up table. {\tt lisp2.m} converts an {\tt X.lisp} input file into
an {\tt X.2run} output file.
\[
\mbox{\tt X.lisp}
\longrightarrow \fbox{\tt lisp2.m} \longrightarrow
\mbox{\tt X.2run}
\]
\item
{\tt slisp.m} is a {\sl LISP} interpreter written in procedural {\sl
Mathematica} that uses {\sl Mathematica} character strings to
represent {\sl LISP} S-expressions. Bindings are kept in an
association list that must be searched sequentially. {\tt slisp.m}
converts an {\tt X.lisp} input file into an {\tt X.srun} output file.
\[
\mbox{\tt X.lisp}
\longrightarrow \fbox{\tt slisp.m} \longrightarrow
\mbox{\tt X.srun}
\]
\item
{\tt lispm.m} is a {\sl Mathematica} program that simulates a {\sl
LISP} interpreter running on a register machine. {\tt lispm.m}
converts an {\tt X.lisp} input file into an {\tt X.mrun} output file.
Before running this program, {\tt xpnd.m} must be used to convert
{\tt lisp.rm} into {\tt lisp.xrm}, which is needed by this program.
\[
\mbox{\tt X.lisp}
\longrightarrow
\begin{array}[b]{c}
\mbox{\tt lisp.rm} \\
\downarrow \\
\fbox{\tt xpnd.m} \\
\downarrow \\
\mbox{\tt lisp.xrm}\\
\downarrow \\
\fbox{\tt lispm.m}
\end{array}
\longrightarrow
\mbox{\tt X.mrun}
\]
\item
{\tt clisp.m} is a {\sl Mathematica} program serving as a driver for a
{\sl LISP} interpreter written in {\sl C}. {\tt clisp.m} converts an
{\tt X.lisp} input file into an {\tt X.crun} output file.
Before running {\tt clisp.m}, the {\sl C} program {\tt lisp.c} must be
compiled using the command {\tt cc -O -olisp lisp.c}.
\[
\mbox{\tt X.lisp}
\longrightarrow
\begin{array}[b]{c}
\mbox{\tt lisp.c}\\
\downarrow \\
\fbox{\tt cc} \\
\downarrow \\
\mbox{\tt lisp} \\
\downarrow \\
\fbox{\tt clisp.m}
\end{array}
\longrightarrow
\mbox{\tt X.crun}
\]
\item
{\tt clispm.m} is a {\sl Mathematica} program serving as a driver for
a {\sl C} program that simulates a {\sl LISP} interpreter running on a
register machine. {\tt clispm.m} converts an {\tt X.lisp} input file
into an {\tt X.cmrun} output file.
Before running {\tt clispm.m}, {\tt xpnd.m} must be used to convert
{\tt lisp.rm} into {\tt lisp.xrm}. {\tt rm2c.m} must then be used to
convert {\tt lisp.xrm} into the {\sl C} program {\tt lispm.c}. {\tt
lispm.c} is then compiled using the command {\tt cc -O -olispm
lispm.c}.
\[
\mbox{\tt X.lisp}
\longrightarrow
\begin{array}[b]{c}
\mbox{\tt lisp.rm} \\
\downarrow \\
\fbox{\tt xpnd.m} \\
\downarrow \\
\mbox{\tt lisp.xrm}\\
\downarrow \\
\fbox{\tt rm2c.m} \\
\downarrow \\
\mbox{\tt lispm.c} \\
\downarrow \\
\fbox{\tt cc} \\
\downarrow \\
\mbox{\tt lispm} \\
\downarrow \\
\fbox{\tt clispm.m}
\end{array}
\longrightarrow
\mbox{\tt X.cmrun}
\]
\end{enumerate}
To run any one {\tt X.m} of these six {\sl LISP} interpreters, first
enter {\sl Mathematica} using the command {\tt math}. Then tell
{\sl Mathematica},
\[
\mbox{\tt << X.m}
\]
To run a {\sl LISP} program {\tt X.lisp}, enter
\[
\mbox{\tt run @ "X"}
\]
To run several programs, enter
\begin{center}
\verb!run /@ {"X","Y","Z"}!
\end{center}
Before changing to another {\sl LISP} interpreter, type {\tt Exit} to
exit from {\sl Mathematica}, and then begin a fresh {\sl Mathematica}
session.
Here is how to run the {\sl LISP} test program, the three {\sl LISP} in {\sl
LISP} examples in my book, and then start computing the halting
probability $\Omega$ in the limit from below:
\begin{verbatim}
math
<< clispm.m
run @ "test"
run /@ {"eval","eval2","eval3"}
Exit
math
<< clisp.m
run @ "omega"
Exit
\end{verbatim}
The six different {\sl LISP} interpreters run at vastly different
speeds, but should always produce identical results. This can easily
be checked, for example, as follows:
\begin{verbatim}
diff X.run X.crun > out
vi out
\end{verbatim}
Two different front ends are available for these six {\sl LISP}
interpreters:
\begin{enumerate}
\item
{\tt run.m} is written in procedural {\sl Mathematica}. As each
M-expression is read in, it is written out, then converted
to an S-expression that is written out and evaluated.\footnote{The
conversion from M- to S-expression mostly consists of making all
implicit parentheses explicit.}
\item
{\tt run2.m} is written in non-procedural {\sl Mathematica}. All
M-expressions are read in at once. Then each is converted to an
S-expression that is written out and evaluated.
\end{enumerate}
Which front end is used is determined by {\tt frontend.m}. Each of
the six {\sl LISP} interpreters contains a {\tt <<} of {\tt
frontend.m}. Normally {\tt frontend.m} is {\tt << run.m} and the
first front end is chosen. To select the second front end, change
this to {\tt << run2.m}.
\[
\fbox{{\sl LISP interpreter}{\tt .m}}
\mbox{\tt <<}
\fbox{\tt frontend.m}
\begin{array}{l}
\mbox{\tt <<} \fbox{\tt run.m} \\
\mbox{\tt <<} \fbox{\tt run2.m} \\
\end{array}
\]
Three register machine programs {\tt *.rm} are provided: {\tt
example.rm}, {\tt test.rm}, and {\tt lisp.rm}. {\tt example.rm} is
the tiny example given in my Cambridge book. {\tt test.rm} has each
possible register machine instruction, but it is not a program that
can be run. {\tt lisp.rm} is the {\sl LISP} interpreter used by {\tt
lispm.m} and {\tt clispm.m}, and converted into the monster
exponential diophantine equation by {\tt eq.m}.
More precisely, to convert any one of the three register machine
programs {\tt X.rm} into an exponential diophantine equation there are
two steps. First, use {xpnd.m} to convert {\tt X.rm} into {\tt
X.xrm}. Then use {\tt eq.m} to convert {\tt X.xrm} into {\tt X.eq}.
For more output, set {\tt fulloutput = True} before typing {\tt <<
eq.m}. For each conversion, a fresh copy of {\tt eq.m} must be loaded
into a clean {\sl Mathematica} session.
\[
\mbox{\tt X.rm} \longrightarrow
\fbox{\tt xpnd.m} \longrightarrow
\mbox{\tt X.xrm} \longrightarrow
\begin{array}[b]{c}
\mbox{\tt fulloutput} \\
\mbox{\tt = True \rm ?} \\
\downarrow \\
\fbox{\tt eq.m}
\end{array}
\longrightarrow
\mbox{\tt X.eq}
\]
Here is how to generate the monster equation:
\begin{verbatim}
math
<< xpnd.m
run @ "lisp"
Exit
math
[fulloutput = True]
<< eq.m
fn of fn.xrm file = lisp
Exit
\end{verbatim}
How does this software help to exhibit randomness in arithmetic?
Take the equation in {\tt lisp.eq}. Substitute 0 for {\tt
input[reg\$X]} for each register {\tt reg\$X} except for {\tt
reg\$expression}. Substitute a toy {\tt LISP} expression that halts if
and only if (the $k$th bit of the $n$th approximation to $\Omega$ is
1) for {\tt input[reg\$expression]}. (Most of the pieces for this are
in {\tt omega.lisp}.) The resulting exponential diophantine
equation is $1.
\times 10^6$ characters long and has $2. \times 10^4$ variables. It
has exactly one solution for a given value of $k$ and $n$ if the $k$th
bit of the $n$th approximation to $\Omega$ is 1. It has no solutions
for a given value of $k$ and $n$ if the $k$th bit of the $n$th
approximation to $\Omega$ is 0. Now think of $n$ as a variable rather
than as a parameter. The resulting equation has only finitely many
solutions if the $k$th bit of $\Omega$ is 0. It has infinitely
many solutions if the $k$th bit of $\Omega$ is 1.
\section*{Bibliography}
\begin{itemize}
\item[{[1]}] S. Wolfram, {\it Mathematica---A System for Doing
Mathematics by Computer,} second edition, Addison-Wesley, 1991.
\item[{[2]}] B. W. Kernighan and D. M. Ritchie, {\it The C Programming
Language,} second edition, Prentice Hall, 1988.
\item[{[3]}] G. J. Chaitin, {\it Algorithmic Information Theory,}
revised third printing, Cambridge University Press, 1990.
\item[{[4]}] G. J. Chaitin, {\it Information, Randomness \&
Incompleteness,} second edition, World Scientific, 1990.
\item[{[5]}] G. J. Chaitin, {\it Information-Theoretic
Incompleteness,} World Scientific, 1992.
\item[{[6]}] G. J. Chaitin, ``Randomness in arithmetic and the decline
and fall of reductionism in pure mathematics,'' {\it IBM Research
Report RC-18532,} November 1992.
\end{itemize}
\end{document}