Chaitin. Algorithmic information theory

219

J. McCarthy (1960), \Recursive functions of symbolic expressions and their computation by machine I," ACM Communications 3, pp. 184{195.

J. McCarthy et al. (1962), LISP 1.5 Programmer's Manual,

Cambridge, Mass.: MIT Press.

J. McCarthy (1981), \History of LISP," in R.L. Wexelblat

(1981), History of Programming Languages, New York: Academic Press, pp. 173{197, 710{713.

R.P. O'Hara and D.R. Gomberg (1985), Modern Programming Using REXX, Englewood Cli s, NJ: Prentice-Hall.

G. Polya (1954), Induction and Analogy in Mathematics,

Princeton, NJ: Princeton University Press.

J. Rissanen (1986), \Stochastic complexity and modeling," Annals of Statistics 14, pp. 1080{1100.

R. Rucker (1987), Mind Tools, Boston: Houghton Mi in.

C.P. Schnorr (1974), private communication.

C.E. Shannon and W. Weaver (1949), The Mathematical Theory of Communication, Urbana: University of Illinois Press.

R.M. Solovay (1975), private communication.

A.M. Turing (1937), \On computable numbers, with an application to the Entscheidungsproblem," Proceedings London Mathematical Society 42, pp. 230{265. Reprinted in Davis (1965).

T. Tymoczko (1986), New Directions in the Philosophy of Mathematics, Boston: Birkh¨auser.

J.C. Webb (1980), Mechanism, Mentalism, and Metamathematics, Dordrecht: Reidel.

P.H. Winston and B.K.P. Horn (1984), LISP, Reading, Mass.: Addison-Wesley.

register machine language. This is the slowest of the three implementations; its goals are theoretical, but it is fast enough to test and debug.

(3)The third LISP implementation, like the previous one, has a 250line REXX driver; the real work is done by a 700-line 370 Assembler H expression evaluator. This is the high-performance evaluator, and it is amazingly small: less than 8K bytes of 370 machine language code, tables, and bu ers, plus a megabyte of storage for the stack, and two megabytes for the heap, so that there is another megabyte left over for the REXX driver. It gets by without a garbage collector: since all information that must be preserved from one evaluation to another (mostly function definitions) is in the form of REXX character strings, the expression evaluator can be reinitialized after each evaluation. Another reason for the simplicity and speed of this interpreter is that our version of pure LISP is \permissive;" error checking and the production of diagnostic messages are usually a substantial portion of an interpreter.

All the REXX programs referred to above need to know the set of valid LISP characters, and this information is parameterized as a small 128-character le.

An extensive suite of tests has been run through all three LISP implementations, to ensure that the three interpreters produce identical results.

This software is available from the author on request.

that left and right parentheses must balance for the rst time precisely at the end of the expression. Our task is easier than in normal LISP because we ignore blanks and all atoms are exactly one character long, and also because NIL and () are not synonyms.

Here are some examples. S0 = 0, since there are no zero-character S-expressions. S1 = , since each atom by itself is an S-expression. S2 = 1, because the empty list () is two characters. S3 = again:

(a)

S4 = 2 + 1:

(aa)

(())

S5 = 3 + 3 :

(aaa)

(a())

(()a)

((a))

S6 = 4 + 6 2 + 2:

(aaaa)

(aa())

(a()a)

(a(a))

(()aa)

(()())

((a)a)

((aa))

((()))

S7 = 5 + 10 3 + 10 :

(aaaaa)

(aaa())

(aa()a)

(aa(a))

225

(a()aa)

(a()())

(a(a)a)

(a(aa))

(a(()))

(()aaa)

(()a())

(()()a)

(()(a))

((a)aa)

((a)())

((aa)a)

((())a)

((aaa))

((a()))

((()a))

(((a)))

Our main result is that Sn=Sn−1 tends to the limit + 2. More precisely, the following asymptotic estimate holds:

In other words, it is almost, but not quite, the case that each character in an n-character S-expression can independently be an atom or a left

or right parenthesis, which would give Sn = ( + 2)n. The di erence, a p

factor of ( + 2)−2k−1:5=2 , is the extent to which the syntax of LISP S-expressions limits the multiplicative growth of possibilities. We shall also show that for n 3 the ratio Sn=Sn−1 is never less than and is never greater than ( + 2)2. In fact, numerical computer experiments suggest that this ratio increases from to its limiting value +2. Thus it is perhaps the case that Sn=Sn−1 + 2 for all n 3.

Another important fact about Sn is that one will always eventually obtain a syntactically valid S-expression by successively choosing characters at random, unless one has the bad luck to start with a right parenthesis. Here it is understood that successive characters are chosen independently with equal probabilities from the set of +2 possibilities

until an S-expression is obtained. This will either happen immediately if the rst character is not a left parenthesis, or it will happen as soon as the number of right parentheses equals the number of left parentheses. This is equivalent to the well-known fact that with probability one a symmetrical random walk in one dimension will eventually return to the origin [Feller (1970)]. Stated in terms of Sn instead of in probabilistic terminology, we have shown that

n=0

Moreover, it follows from the asymptotic estimate for Sn that this in - nite series converges as P n−1:5.

In fact, the asymptotic estimate for Sn stated above is derived by using the well-known fact that the probability that the rst return to the origin in a symmetrical random walk in one dimension occurs at epoch 2n is precisely

−

This is equivalent to the assertion that if = 0, i.e., we are forming S-expressions only out of parentheses, then

−

For we are choosing exactly half of the random walks, i.e., those that start with a left parenthesis not a right parenthesis.

Accepting this estimate for the moment (we shall give a proof later) [or see Feller (1970)], we now derive the asymptotic estimate for Sn for unrestricted . To obtain an arbitrary n-character S-expression,rst decide the number 2k (0 2k n) of parentheses that it contains. Then choose which of the n characters will be parentheses and which will be one of the atoms. There are n − 2 choose 2k − 2 ways of doing this, because the rst and the last characters must always be a left and a right parenthesis, respectively. There remain n−2k choices for the characters that are not parentheses, and one-half the number of