Exploring Randomness (Discrete Mathematics and Theoretical Computer Science) [Hardcover]

Gregory J. Chaitin (Author)

Book Description

ISBN-10: 1852334177 | ISBN-13: 978-1852334178 | Publication Date: December 7, 2001 | Edition: 2nd printing

This essential companion to Chaitin's successful books The Unknowable and The Limits of Mathematics, presents the technical core of his theory of program-size complexity. The two previous volumes are more concerned with applications to meta-mathematics. LISP is used to present the key algorithms and to enable computer users to interact with the authors proofs and discover for themselves how they work. The LISP code for this book is available at the author's Web site together with a Java applet LISP interpreter. "No one has looked deeper and farther into the abyss of randomness and its role in mathematics than Greg Chaitin. This book tells you everything hes seen. Don miss it." John Casti, Santa Fe Institute, Author of Goedel: A Life of Logic.'

Editorial Reviews

Review

From the reviews:

"In this book on algorithmic information theory, the author compares his concept of randomness (for recursive functions) which is based on the complexity (length) of the generating algorithm (program) with other concepts (by Martin-Löw, Solovay) and discusses its relation to incompleteness and the halting problem. Algorithms (needed for proof) are described in a (small) dialect of LISP. The style mostly is that of a lecture, lively and readable." (P. Schmitt, Monatshefte für Mathematik, Vol. 141 (1), 2004)

"Chaitin is the main architect of a new branch of mathematics called algorithmic information theory, or ‘AIT’. … in Exploring Randomness, he develops algorithmic theory, further revealing its technical core. This is important work, with implications that go far beyond the arcane arguments of one branch of mathematics. … As one gets to the substance … it is difficult to resist Chaitin’s enthusiastic style and obvious intelligence. Beyond the technicalities of the argument, the reader is quickly drawn into a fundamental new landscape of ideas." (Jacques F. Vallee, Journal of Scientific Exploration, Vol. 16 (4), 2002)

"Chaitin’s latest three books form a nice triangular base to support and explore the concepts underlying algorithmic information theory (AIT) – a clever blend of Gödel, Turing, and Shannon that Chaitin developed in his late teens … . this set of three volumes packages the material in a nice, quite digestible fashion … . Chaitin’s results demonstrate that not only there is no structure to foundation of mathematics, the foundation is in fact random." (The Mathematica Journal, April, 2002)

"The book is devoted to a Lisp formalism for exploring the basic ideas, concepts and results on program-size complexity and random sequences. The book contains a wealth of exercises, ranging from the ‘mathematical equivalent of finger warm-ups for pianists’ to substantial programming projects, from open questions to questions the author cannot even formulate. Highly recommended to anyone interested in understanding algorithmic information theory through programming." (Cristian S. Calude, Zentralblatt MATH, Vol. 963, 2002)

"This book uses LISP to explore the theory of randomness, called algorithmic information theory (AIT). This is the third of Chaitin’s book … . The common theme of the books is the study of H(x), the size in bits of the smallest program for calculating x … . Each book has a different emphasis. This book gives a detailed discussion of the metamathematical implications of these ideas and presents the technical core of Chaitin’s algorithmic theory." (Book News on the Internet, October, 2001)

"This is revolutionary, explosive stuff. … Chaitin challenges readers to follow his lead and forge their own path into the black hole of randomness, the ‘darkness at the edge of mathematics’. When Chaitin wrote ‘explore’, he well and truly meant it. An exhilarating, mind-blowing book from one of the great ideas men of mathematics and computer science." (Marcus Chown, New Scientist, January, 2002)

Product Details

• Hardcover: 174 pages
• Publisher: Springer; 2nd printing edition (December 7, 2001)
• Language: English
• ISBN-10: 1852334177
• ISBN-13: 978-1852334178
• Product Dimensions: 9.1 x 6.5 x 0.7 inches
• Shipping Weight: 13.6 ounces (View shipping rates and policies)
• Average Customer Review: 3.5 out of 5 stars  See all reviews (2 customer reviews)
• Amazon Best Sellers Rank: #800,322 in Books (See Top 100 in Books)
  • #27 in Books > Computers & Technology > Programming > Languages & Tools > Lisp

More About the Author

Discover books, learn about writers, read author blogs, and more.

Customer Reviews

Most Helpful Customer Reviews

33 of 51 people found the following review helpful:

4.0 out of 5 stars A message from the author, September 4, 2001

By 

G. J. Chaitin (Yorktown Heights, NY USA) - See all my reviews
(REAL NAME)   

This review is from: Exploring Randomness (Discrete Mathematics and Theoretical Computer Science) (Hardcover)

Hello, I'm Gregory Chaitin and I'm the author of
Exploring RANDOMNESS, which is my attempt to explain
the technical heart of my theory of algorithmic
information as understandably as possible. To make
my theory more concrete, I've converted it into a
theory of the size in bits of real computer programs,
programs that you can actually run. See also my
new book, "Conversations with a Mathematician: Math,
Art, Science and the Limits of Reason", which is a
collection of my most wide-ranging and non-technical
lectures and interviews.---Gregory Chaitin, IBM Research
Division

0 of 4 people found the following review helpful:

3.0 out of 5 stars Just for LISP and randomness, May 12, 2010

By 

Ludovicus (Beachwood, OH USA) - See all my reviews

Amazon Verified Purchase

This review is from: Exploring Randomness (Discrete Mathematics and Theoretical Computer Science) (Hardcover)

The treatment of LISP and randomness is interesting.
But it is deplorable the propagation of his inacceptable
mesure of the complexity of a sequence as the size in bits
of the minimum program that reproduces it.
According to that, the complexity of the sequence of a
polynomial of 10th degree is greater than the complexity
of the sequence of prime numbers.
The list of the coeficients of the polynomial needs more bits
that the whole program for prime numbers.
Ludovicus