Learning to love uncertainty

Conversations with a Mathematician

三月 15, 2002

Randomness is a concept that seems to be strongly in conflict with the most basic ideals of mathematics - the pursuit of complete precision and of absolute certainty checked by mathematical proof. Many mathematicians have been reluctant to accept randomness, just as many physicists have been reluctant to accept the uncertainty that lies at the heart of quantum theory. Gregory Chaitin's achievement has been to discover a precise mathematical definition of randomness, based on ideas taken from theoretical computer science. His informal explanation is as follows.

Choose your favourite general-purpose programming language - it does not matter which, so long as there is no restriction on the range of numbers that a program can print, one digit at a time. Each program itself consists of a certain number of characters, which have to be read into the computer before the program starts. Some programs in the language print numbers that are shorter than their own length, some longer, and some the same. For example, it is easy to write a very short program that prints the digit 1 followed by a million zeroes. Such a number would hardly be considered random. After a few hundred zeroes, it is too easy to guess correctly what the next digit will be. But a different program that just prints the number 10 is rather longer than two characters. The shortest such program is something such as "print(10)", which has nine characters. So 10 could be regarded as a random number. Certainly, even given that the first digit is 1, there are no good grounds to guess what the second digit will be. Chaitin defines a number to be random if it is shorter than all the programs that will print it out. According to this definition, very small numbers (such as 10) are all random. On the other hand, the number consisting of the first million digits of the decimal expansion of the real number pi is not random; there already exist quite short programs that will print it. But that is an exception. By far the majority of numbers longer than a million digits are random according to this definition. An interesting feature of the definition is that it does not depend on the concept of probability. Furthermore, it gives an effective way of proving that a particular number is non-random: just write a program shorter than it, that outputs that number. But Chaitin has shown that there is absolutely no way of giving a checkable mathematical proof that a large number is actually random. This he proved to be impossible for any number that is longer than the computer program that would be capable of checking the proof.

These ideas are simply and engagingly explained in the first section of this book, a transcript of a talk given by Chaitin in 1999 at the University of Massachusetts Lowell. They justify the phrase "the limits of reason", which appears in the subtitle. The technical ideas are extended in two further lecture transcripts. They define Chaitin's famous number called omega as the probability that a probabilistically generated program (for example, one typed by monkeys at a keyboard) will ever terminate. This number is so random that no program can ever be written to print out even one of its digits.

But there is worse to come. Even if a mathematician knew or firmly believed that the 17th digit is a 1, it would be impossible to write a checkable proof of this proposition. Even if every digit except the 17th were known, it would still be impossible for a mathematician to find the 17th digit. And the same for any other digit. And although each digit is forever unknowable, Chaitin has proved that exactly half of them (in the limit) are even digits, and half of them are odd. Technically, propositions about the value of each digit constitute an infinite set of independently undecidable propositions. These and related results are a generalisation and explanation of the pioneering discoveries of Gödel and Turing.

Chaitin's undecidability results are defined in terms of computers and probabilities, subjects that many mathematicians are happy to ignore. So Chaitin has translated his result right into the core of mathematical practice, which has always been the solution of algebraic equations. Some equations are known to have no solutions (for example, x = x + 1); some have just one solution (for example, 2x = 4); some have a finite number of solutions (for example, x² - 3x + 2 = 0); and some have an infinite number of solutions (for example, (x + 1)²= x² + 2x + 1). Chaitin has constructed an equation for which it is mathematically undecidable whether it has a finite or an infinite number of solutions. Actually, he got a computer to write out the equation as it is about 200 pages long.

But again, there is worse to come. The equation has an extra unknown, which can be set to any whole number. If you set it to 17, the remaining equation will have an infinite number of solutions just if the 17th digit of Chaitin's omega is a 1. Similarly for all the other digits. Since the digits of omega are undecidable, Chaitin has given us an infinite set of independently undecidable propositions, lurking right in the central core of mathematics.

All these ideas are explained (with some overlap) in three sections of the book. The remaining eight sections are much shorter. They are mainly transcripts of interviews with Chaitin conducted by journalists in various countries over the past ten years. As the author admits, there is a lot of repetition here, but it is compensated by the immediacy and the liveliness of the spoken word, and the drama of human interaction. We learn about his father, his childhood in Manhattan and Buenos Aires, and his first engagement with the problem of randomness at the age of 15. His early absorption with mathematics made him shy with girls, but since then he has learnt to enjoy life to the full. He talks of street carnivals, cafes, champagne, hill climbing and beautiful women; and asserts that his pleasure in mathematics is similar to these. There are brief analogies drawn with physical science, but almost nothing on art or music, and no pictures or songs.

He tells stories of his meetings with other contemporary mathematicians, his failure to meet Gödel, and his recollection of reading of the deaths of Russell and Einstein. He repeatedly drops the names of earlier mathematicians - Hilbert, Gauss, Borel, Hardy, Pascal and others. In some cases he briefly describes their work or recounts an anecdote about their lives. Many of the anecdotes are interesting, but most of the references will be significant only to those who are already familiar with the name and the ideas associated with it.

In the preface, which was written specially for this collection, the author claims he would have loved reading this book as a teenager turning into a mathematician. He hopes to show that maths and science are fun, and asks the reader to tell him whether he has succeeded. Yes, his enjoyment of the topics of his own research is infectious. This is a suitable bedside book for a teenager whose library already contains some more coherently written books in popular mathematics and science. It might encourage an extension of the library to include an earlier book by Chaitin himself.

Professor Sir Tony Hoare is a computer scientist, now working for Microsoft.

Conversations with a Mathematician: Math, Art, Science and the Limits of Reason

Author - Gregory J. Chaitin
ISBN - 185233 549 1
Publisher - Springer
Price - £15.00
Pages - 158

请先注册再继续

为何要注册?

  • 注册是免费的,而且十分便捷
  • 注册成功后,您每月可免费阅读3篇文章
  • 订阅我们的邮件
注册
Please 登录 or 注册 to read this article.