Extending AIT to the size of programs for computing infinite sets and to computations with oracles

A lot remains to be done! Hopefully this is just the beginning of AIT! The higher you go, the more mountains you can see to climb!

Indeed, there has been a recent wave of work on AIT, some of which C. Calude and I summarize in a recent article in Nature. [C. Calude and G. Chaitin, ``Randomness everywhere,'' Nature 400 (1999), pp. 319-320.] Building on results of Calude and collaborators, T. Slaman has recently shown that Ω can be characterized as follows. Consider a random real number r that can be computed in the limit from below. [With no requirement that there be a regulator of convergence. I.e., you compute r in the limit from below without ever knowing how close you are.] Then r is an Ω number, that is, r is the halting probability of a suitable universal self-delimiting binary computer. And Solovay [See his article ``A version of Ω for which ZFC cannot predict a single bit,'' in C. Calude and G. Paun, Finite versus Infinite, Springer-Verlag London, 2000, pp. 323-334.] has recently constructed a universal self-delimiting binary computer whose halting probability has the property that none of its bits can be determined within the usual formalization of mathematics, ZFC, which is Zermelo-Fraenkel set theory with the axiom of choice. In other words, there is a particular Ω number that completely eludes ZFC! [Calude has extended this work of Solovay's. In a nutshell, it seems that the problem resides in getting past the first 0 bit in the binary expansion of an Ω number---the initial run of 1 bits can be determined, but things crash to a halt as soon as we hit a 0 bit.]

However the open problems in AIT that I'll discuss here are of a different nature. They have to do with how to extend AIT to infinite computations. There are many open questions involving the program-size complexity of infinite sets of S-expressions.

It's important to study H(X) for infinite sets X of S-expressions, because the incompleteness results in my companion volume The Limits of Mathematics, the limitative theorems that I give there, are all formulated in terms of the information content or complexity H(FAS) of a formal axiomatic system, which is defined to be the size of the smallest program for U to generate all the theorems of the formal axiomatic system FAS. In other words, the flavor of my work on metamathematics is to limit the power of a set of mathematical axioms in terms of their information content, but I believe that the best definition of this concept is not the program-size complexity of the string of axioms, but rather that of the set of theorems that are generated from them using the rules of inference. [For this measure of the complexity of a FAS combines the complexity or information content of the axioms with that of the rules of inference, and minimizes over all possible choices of axioms and rules of inference for the theory = set of theorems in question.]

But in this volume I've concentrated on the theory of program-size complexity proper, rather than on its applications to metamathematics. I believe that extending AIT to infinite computations, to the complexity of infinite sets of S-expressions, is of interest in itself, and has intrinsic intellectual merit quite apart from the possible applications to metamathematics.

And when you start to work on this, right away you have to deal with ``oracles''. That involves extending our computing machines by allowing them to consult an oracle for the halting problem; [The oracle is used to decide whether a LISP expression x has a value/halts. If so, (oracle x) gives true; if not, it gives false. Alternatively, we can have (oracle p) tell us if U(p) halts.] that gives us our first oracle machine U'. Then there's a higher-level oracle machine U'' that has an oracle for the halting problem of U', and so forth and so on! And there's a halting probability at each level of this hierarchy:

Ω, Ω', Ω'', Ω''', ...

And at each level we get a complexity measure

H, H', H'', H''', ...

and a corresponding notion of randomness.

Now let me sketch our current knowledge. I'll outline the current version of AIT for infinite sets and point out the differences between AIT for finite and for infinite computations and where there is work to be done. Recall that the way we use U to generate an infinite set X of S-expressions instead of an individual S-expression x, is by collecting all the arguments of display instead of looking at the value returned by the LISP prefix. So U(p) = x or U(p) = X is the final value or it's the set that's displayed.

Remark on notation

We could use notation to distinguish between the complexity of an S-expression and the complexity of a set of S-expressions. We could call it ``enumeration complexity'' or ``e-complexity'', and write H_e instead of H and P_e instead of P and U_e instead of U. Then U_e(p) would be what is displayed during the execution of p, and U(p) would be the final value that's returned, and there would be no ambiguity at all!

However, I prefer to let the type of argument decide matters, so that if it's H of an individual S-expression, we mean real H, and if it's H({...}) we mean H_e. The choice is yours! If you like, you can rewrite this chapter placing e subscripts wherever they're needed.

H(X ∩ Y), H(X ∪ Y) ≤ H(X) + H(Y) + c for infinite sets X, Y of S-expressions

In finite AIT we have this basic subadditivity property:

H(x, y) ≤ H(x) + H(y) + c.

You just concatenate a minimum-size program for the S-expression x and a minimum-size program for the S-expression y and slap the prefix cons eval read-exp cons eval read-exp nil in front.

But you can't concatenate programs that never halt, instead you have to intertwine or merge their bits in the order that these bits are needed when the programs are running simultaneously, in parallel. That's how you can show that

H(X ∩ Y) ≤ H(X) + H(Y) + c
H(X ∪ Y) ≤ H(X) + H(Y) + c'

for infinite sets X and Y of S-expressions. So intertwining programs replaces concatenating them. That does the trick; we're okay.

H(X) = H(X, { k < H(X) }) + O(1) for infinite sets X of S-expressions

[Writing H(X, Y) for two sets X and Y presupposes some convention for enumerating two sets at the same time. E.g., generate X and Y simultaneously by displaying {(A: x) : x ∈ X } ∪ {(B: y) : y ∈ Y }.]

For individual S-expressions x we have

H(x) = H(x, H(x)) + O(1).

This is not the case for infinite sets X of S-expressions! For infinite sets X of S-expressions, we can only determine H(X) in the limit from below, because the program for generating X never halts and we can never be sure that we have finished reading all the bits in it! So in the case of infinite computations what we have is

H(X) = H(X, { k < H(X) }) + O(1).

So it's no longer the case that a minimum-size program tells us its size as well as its output. Now we only learn the size in the limit of infinite time, in the limit from below! This is another important difference between the finite and infinite versions of AIT.

H(X) ≠ −log₂ P(X) + O(1) for sets X of S-expressions

For individual S-expressions x we have

H(x) = −log₂ P(x) + O(1).

This is not the case for sets of S-expressions X!

In my paper on the ``Algorithmic entropy of sets,'' [Computers and Mathematics with Applications 2 (1976), pp. 233-245.] I was able to show that

H(X) ≠ −log₂ P(X) + O(1)

even for finite sets of S-expressions X. I did this by using a counting argument, by showing that sometimes there are substantially fewer finite sets X with H(X) < n than there are finite sets X with P(X) > 2⁻ⁿ.

More precisely, I extended Solovay's result [In his unpublished book-length manuscript on AIT dated May 1975.] that

# { x : H(x) < n } = 2^{n − H(n) + O(1)}.

I was able to show that

# { X : H(X) < n } = 2^{n − H({k < n}) +
O(log H({k < n}))}
# { finite X : P(X) > 2⁻ⁿ } = 2^{n − H'(n) + O(1)}.

That does the trick, because H({k < n}) = H({0, 1, 2, ..., n−1}) is sometimes much larger than H'(n), which is the size of the smallest program to compute n using a universal computer U provided with an oracle for the halting problem.

[By the way,

# { X : P(X) > 2⁻ⁿ } = 2^{n − H'({k < n}) +
O(log H'({k < n}))},

which gives us another way to show that

H(X) ≠ −log₂ P(X) + O(1).

]

So H(X) and −log₂ P(X) are different for sets X of S-expressions. Nevertheless, they are not too different. In a difficult paper, Solovay [R.M. Solovay, ``On random r.e. sets,'' in A.I. Arruda, N.C.A. da Costa, and R. Chuaqui, Non-Classical Logics, Model Theory, and Computability, North-Holland, Amsterdam, 1977, pp. 283-307.] succeeded in showing that

P(X) > 2⁻ⁿ ⇒ H(X) ≤ 3n + O(log n).

The probability α that a set of S-expressions is finite is random', that is, α looks random even if one has an oracle for the halting problem

V. Becher and S. Daicz [Private communication, unpublished.] have considered the real number α defined as the probability that U generates a finite set of S-expressions

α = ∑ _{finite X} P(X) = ∑ _{U(p) is finite} 2^−|p|,

and have shown that this is essentially just Ω', the halting probability of a universal machine with an oracle for the halting problem. Their proof involves the idea of simulating an oracle computation that halts, in the limit (see my paper ``Algorithmic entropy of sets''). At stage t the oracle answers that a program halts iff it halts within time t. If an oracle computation halts, then in the limit as t → ∞ we will simulate it properly. Then at stage t we just output t unless the fake oracle computation halts. This set will be finite if the oracle computation halts, infinite otherwise. There may be ``harmless overshoot,'' i.e., some extra bits of the program may be read by mistake, but these bits will make no difference in the final outcome. Thus there is a prefix π such that U(π p...) is finite if U'(p) halts, and is infinite if U'(p) doesn't halt. So the probability that U(π x) is finite is exactly equal to the probability that U'(x) halts, which is Ω'. Some extra considerations show that H' of the first n bits of the probability that U(x) is finite is within O(1) of H' of the first n bits of Ω'.

Higher order versions of the halting probability: Ω'', Ω''', ...

Here's an extension of the Becher, Daicz idea: β = the probability that a set is cofinite (has finite complement) is essentially just Ω''. But it's a bit of a nuisance to formulate this properly, since we're dealing with infinite sets of S-expressions rather than infinite sets of non-negative integers, to which the concept of cofiniteness has a more straightforward application. The proof uses a more elaborate version of simulating oracles by doing computations in the limit. [The new ingredient/trick is ``erasure,'' which involves changing our mind by filling in a hole that we deliberately left in a set.] For hints, see my ``Algorithmic entropy of sets'' paper.

Is there randomness in other fields of mathematics?

The halting problem has been discovered in many traditional fields of mathematics, for example, in algebra and in combinatorial topology. Is it possible that some of the machinery that has been developed to dress up Turing's halting problem as natural questions in other fields, might also work, with not too much additional effort, with the base-two bits of the halting probability Ω?

In the case of diophantine equations (elementary number theory), I have already taken the trouble to do this. [In the first half of G. Chaitin, Algorithmic Information Theory, Cambridge University Press, 1987, I did it using 360 assembler and REXX software. See http://arXiv.org/abs/chao-dyn/9312006 for a newer version using Mathematica and C code and a version of LISP close to this one.] I took advantage of work on Hilbert's 10th problem by J. Jones and Y. Matijasevic to construct a (large) exponential diophantine equation

L(k, x₁, x₂, x₃, ...) = R(k, x₁, x₂, x₃, ...).

This is an algebraic equation involving only addition, multiplication and exponentiation of integers ≥ 0, and for each integer value of k ≥ 0 one inquires if there are finitely or infinitely many solutions of L = R in integers x_i ≥ 0. My equation is constructed in such a manner that the answer will be ``finite'' if the kth bit of Ω is a 0, and it will be ``infinite'' if the kth bit of Ω is a 1. Thus Ω's randomness infects elementary number theory!

One can also manage to do this with a polynomial diophantine equation

P(k, n, x₁, x₂, x₃, ...) = 0.

This equation involves only addition, subtraction and multiplication of integers. In this case one asks for each k ≥ 0 whether there are finitely or infinitely many values of n ≥ 0 for which the diophantine equation P = 0 has a solution in integers x₁ ≥ 0, x₂ ≥ 0, x₃ ≥ 0, ...

The challenge is now to find in other fields of mathematics natural questions that are also camouflaged versions of the bits of Ω, and are therefore random in the sense of AIT. Camouflaged versions of Turing's halting problem involve questions of the form ``Does something ever happen?'' Camouflaged versions of my halting probability Ω must ask whether something occurs finitely or infinitely often.

The nice thing about this, if it could be achieved, is that one would immediately obtain as a corollary extremely delicate statistical information about the random mathematical phenomenon in question!

Final remarks

This last section has something of the flavor of a dialogue with Stephen Wolfram.

Wolfram believes that most mathematical questions are undecidable, that most involve Turing's halting problem or worse; mathematicians just concentrate on problems that can be solved, not on those that can't be! Read his thousand-page book [S. Wolfram, A New Kind of Science, to be published by Wolfram Media in 2001, hopefully. Meanwhile, take a look at http://www.wolframscience.com.] and decide for yourself!

How about some positive, optimistic results on why math works so well, instead of concentrating on pessimistic negative results about randomness in mathematics? The idea would be to try to show why naturally occurring mathematical questions can usually be settled (Fermat/Wiles!), and that incompleteness is a red herring.

But in somewhat different ways, from somewhat different perspectives, Wolfram and I are arguing that this is not the case, that maybe there is no such optimistic theory, maybe optimism is unjustified because incompleteness, undecidability and randomness are pervasive, are, as Wolfram says, ubiquitous.

Certainly he comes up with interesting evidence that universality (universal computation) is ubiquitous, so maybe so is the halting problem. Wolfram also argues against the uniqueness of living beings, because maybe everything does universal computation, everything has richly varied behavior patterns, and we're not special!

In spite of Wolfram's extremely interesting ideas, let me turn to my vision for a theoretical biology.

How about a general, abstract mathematical theory of what life is and why it must evolve? [See my papers on theoretical biology: ``To a mathematical definition of `life','' ACM SICACT News, No. 4 (January 1970), pp. 12-18; ``Toward a mathematical definition of `life','' in R. Levine and M. Tribus, The Maximum Entropy Formalism, MIT Press, 1979, pp. 477-498; ``Algorithmic information and evolution,'' in O. Solbrig and G. Nicolis, Perspectives on Biological Complexity, IUBS Press, 1991, pp. 51-60.] How about a theory of what thinking, intelligence and consciousness are? Will the notion of information, in some form or other, perhaps not in the form in this book, play a role in such theories? Are there any such theories, or are these problems, as some people I've spoken to have suggested, themselves instances of questions that go beyond the limits of mathematics? I hope not! But who knows; you don't know until you try. It would be interesting to settle it one way or another; either to come up with such a general mathematical theory, or to give convincing arguments that this isn't possible.

Indeed Wolfram has argued that most things in the physical universe perform universal computation and are therefore in some sense ``alive'', and ``intelligent'', and that trying to define our specific kind of ``life'' or ``intelligence'' is like trying to define a truck: it's a contingent historical phenomenon, ``frozen history'' the biologists call it---you don't expect to come up with a mathematical equation for trucks, or a fundamental mathematical theory of trucks, says Wolfram. He suggests that maybe we're not so unusual, maybe we're not as significant or as interesting as we thought! But I'm not convinced. I think that we should keep trying to find fundamental new ideas to help us to understand life, thought, and intelligence---don't give up! It's true that it might all just be phenomenological, ad hoc engineering, not fundamental science, and that we're really trivial, but I don't think so!

If you figure it all out, please let me know! Whether the ideas in this book (or some variant of them) play a role doesn't really matter, I just want to know the answer!

Well, that was a hard, tough climb! I hope you thought the views were worth it! Fortunately, in math you don't have the agony of getting back down after making summit, when you're exhausted, before the weather changes...

Exercises

Show by intertwining endless computations that there is a c such that for all infinite sets X and Y of S-expressions:
H(X, Y) ≤ H(X) + H(Y) + c
P(X, Y) ≥ P(X) × P(Y) × 2^−c
−log₂ P(X, Y) ≤ −log₂ P(X)P(Y) + c.
Determine the value of c!
Program in LISP the oracle machine simulation in the limit used by Becher and Daicz to prove their result about α. This will require additions to our LISP dialect, and changes to the interpreter. Hint: add a new one-argument primitive function oracle that consults the oracle and returns its answer, and a new version of try with an argument giving the expression to be used to simulate the oracle. It might be useful for this new version of try to return a chronological list of the questions that were asked and the oracle's replies.
What is the correct definition of relative complexity H(Y | X) for infinite sets of S-expressions X and Y? What is the correct definition of mutual information H(X : Y) for infinite sets of S-expressions X and Y?
Does Occam's razor apply to infinite computations? Are there few minimum-size programs that compute a specific infinite set X of S-expressions? In the finite case of an individual S-expression x we know that the number of p with H(x) = |p| for which U(p) = x is bounded. Is the number of p with H(X) = |p| for which U(p) = X also bounded? Is this result stable? That is, is the number of p with H(X) + c ≥ |p| and U(p) = X also bounded?
What is the connection between H(X) and −log₂ P(X) for infinite sets X of S-expressions? In the case of an individual S-expression x we know that
H(x) = −log₂ P(x) + O(1).
But we have seen that in the case of infinite sets X of S-expressions the situation is much more complicated. A first step might be to try to determine if Solovay's result that
P(X) > 2⁻ⁿ ⇒ H(X) ≤ 3n + O(log n)
is sharp.
In the case of infinite sets X of S-expressions, is it more fruitful to build AIT around
−log₂ P(X)
than to use the program-size complexity H(X)?!