[FOM] Arithmetic-free theory of formal systems?

John McCarthy jmc at steam.stanford.edu
Mon May 17 17:50:53 EDT 2004

Lisp lists are better for expressing symbolic information than

Consider x + yz, represented in Lisp by (+ (* y z)) and represented in
a computer by a pointer structure.  In a string language, one must
parse to discover that x + yz is primarily a sum, whereas in Lisp a
sum is identified by (car exp) = (quote +).  More generally, one can
use an abstract syntax, with predicates for identifying what kind an
expression is and analytic abstract functions for finding the
constitutents of an expression and synthetic abstract functions for
building them out of parts.

These matters, including abstract syntax, are discussed in my 1963
paper "Towards a mathematical science of computation" given at the
1962 IFIPS meeting and on the web as

More information about the FOM mailing list