DOES GOD PLAY DICE?

A mini-conference on Randomness and Constructive Mathematics has been held at Auckland University, New Zealand (under the aegis of the new School of Mathematical and Information Sciences) on Tuesday 16 February 1993.

This conference was organised in honor of G. J. Chaitin, from IBM's Thomas Watson Research Center (New York), founder of algorithmic information theory, who was visiting Auckland University from the 13rd to the 20th of February.

The title of the colloquium Does God Play Dice? is a reference to Einstein's well known comment

questioning the probabilistic nature of quantum theory. This theory, as you no doubt know, pertains to events involving atoms and particles smaller than atoms, events such as collisions or the emission of radiation. In all these situations the theory is able to tell what will probably happen and not what will certainly happen. It is important to note that Einstein was not questioning the use of probabilities in quantum theory (as a measure of temporary ignorance or error), but the implication that the individual microscopic events are themselves indeterminate, unpredictable, random. [It appears that the ancient Greeks and Romans would not object to the idea that the microscopic universe is essentially governed by chance - in fact they made their Gods play dice quite literally, by throwing dice in their temples, to see the will of Gods; the Emperor Claudius even wrote a book on the art of winning at dice. However, from the point of view of Christianity, playing dice with God was definitely a pagan practice -- it violates the first commandment. St. Augustine is reported to say that nothing happens by chance, because everything is controlled by the will of God.]

The classical idea of casuality (i.e. the idea that the present state is the effect of an anterior state and cause of the state which is to follow) implies that in order to predict the future we must know the present, with enough precision. But, for quantum events this is impossible in view of Heisenberg's Uncertainty Principle. It was thought, however, that order reigned at human dimensions, but, in more recent times, with chaos theory and non-linear dynamics, we have got used to the fact that non-predictability is omnipresent in the physical world.

All these facts have undermined our familiar ideas about space, time, matter, casuality. So, it appears that God plays indeed dice with the physical universe.

What about the mathematical universe, our supreme model of solidity and rigor? In 1987, Chaitin showed that even elementary arithmetic has a random structure. Refining work done by Gödel and Turing, but following an original path, Chaitin designed a new mathematical theory of information called algorithmic information theory. Given the central place of arithmetic in mathematics, it seems that God also plays dice with mathematics.

Turing's fundamental result is that the halting problem is unsolvable. Chaitin's fundamental result is that the halting probability is algorithmically random, i.e. the digits of the number Omega expressing the halting probability form a binary random sequence. Omega

embodies an enormous amount of wisdom in a very small space ... inasmuch as its first few thousands digits, which could be written on a small piece of paper, contain the answers to more mathematical questions than could be written down in the entire universe.

Throughout history mystics and philosophers have sought a compact key to universal wisdom, a finite formula or text which, when known and understood, would provide the answer to every question. The use of the Bible, the Koran and the I Ching for divination and the tradition of the secret books of Hermes Trismegistus, and the medieval Jewish Cabala exemplify this belief or hope. Such sources of universal wisdom are traditionally protected from casual use by being hard to find, hard to understand when found, and dangerous to use, tending to answer more questions and deeper ones than the searcher wishes to ask. The esoteric book is, like God, simple yet undescribable. It is omniscient, and transforms all who know it ... Omega is in many senses a cabalistic number. It can be known of, but not known, through human reason. To know it in detail, one would have to accept its uncomputable digit sequence on faith, like words of a sacred text.

We won't go any further into this, but quote a review of Chaitin's work stating that

Chaitin's article makes the world shake just a little.

• R. W. Doran (Auckland University). Welcome
• G. J. Chaitin (IBM Research Center, New York). Randomness in Arithmetic Abstract: God not only plays dice in quantum mechanics, but even with the whole numbers!

• D. S. Bridges (Waikato University, Hamilton). The Computational Content of Mathematics Abstract: Which theorems of pure mathematics have computational proof, and which do not? In order to answer this question, I first give background to Church's thesis that the computable partial functions from N to N are precisely those that are partial recursive (or, equivalently, Turing machine computable). I then discuss recursive and recursively enumerable sets, and the undecidability of the Halting Problem. This will lead to computable real numbers, computable decimal expansions, computable functions on the computable real number line, the recursive failure of the Heine-Borel theorem, and the recursive Lebesgue measure of the recursive unit interval. The talk ends with a look at two provocative examples of `computable' functions which raise questions about the use of classical logic in computability theory.

• G. J. Chaitin (IBM Research Center, New York). The Berry Paradox Abstract: In the same manner that Gödel's proof is based on the paradox of the liar, my information-theoretic incompleteness theorems are based on the Berry paradox.

• W. J. Walker (Auckland University). The Arithmetic Fourier Transform Abstract: The Arithmetic Fourier Transform (AFT) is an algorithm for the computation of Fourier coefficients which may be implemented using addition operations with very few multiplications and which does not involve exponential or trigonometric functions. The algorithm is obtained using Möbius inversion. Recently the verification of the algorithm has been extended from a class of smooth functions to step functions for which the convergence is very slow. Nevertheless the step function form of the algorithm has proved a useful tool for deriving theoretical results about a certain class of digital filters.
• M. Lennon (Auckland University). Randomness in the Integers Abstract: The multiplicative properties of the integers show a puzzling lack of regularities. The prime number theorem and theorems on factorisation of numbers indicate that arguments based on statistical considerations are usually correct. This talk will explore various results concerning prime factorisation of integers.
• C. Calude (Auckland University). Two Questions on Chaitin's Model of Randomness Abstract: i ) Using a topological argument we show that Chaitin's definition of random strings is better that Kolmogorov's one. ii ) We prove that the usual positional representations of a real number are either random, in Chaitin's sense, for all bases or not so for any base. The first part of the talk reports joint work done with C. Campeanu (Bucharest University, Romania) while the second one refers to joint results obtained with H. Jürgensen (The University of Western Ontario, Canada).