Information and Randomness: An Algorithmic Perspective (Texts in Theoretical Computer Science. An EATCS Series) (Hardcover)

~ Cristian S. Calude (Author) "We denote by N, Q, I and R, respectively, the sets of natural, rational, irrational and real numbers; N+ = N \ {0} and R+..." (more)
Key Phrases: natural positional representations, increasing computable sequence, halting probability, Invariance Theorem, Omega Number, Intermediate Step (more...)

Editorial Reviews

Review

From the reviews of the second edition:

"This book, benefiting from the author’s research and teaching experience in Algorithmic Information Theory (AIT) should help to make the detailed mathematical techniques of AIT accessible to a much wider audience." (PHINEWS, Vol. 2, October 2002)

Product Description

Presents in a mathematically clear way the fundamentals of algorithmic information theory and a few selected applications to mathematical logic.

Product Details

• Hardcover: 450 pages
• Publisher: Springer; 2nd edition (November 11, 2002)
• Language: English
• ISBN-10: 3540434666
• ISBN-13: 978-3540434665
• Product Dimensions: 9.4 x 6.3 x 0.9 inches
• Shipping Weight: 1.6 pounds (View shipping rates and policies)
• Average Customer Review: 5.0 out of 5 stars  See all reviews (1 customer review)
• Amazon.com Sales Rank: #1,523,930 in Books (See Bestsellers in Books)

Customer Reviews

Most Helpful Customer Reviews

11 of 14 people found the following review helpful:

5.0 out of 5 stars Classical ideas with modern use., October 9, 2004

By	Palle E T Jorgensen "Palle Jorgensen" (Iowa City, Iowa United States) - See all my reviews (REAL NAME)

I stumbled over this (lovely) book a little by accident. As I kept reading, my enthusiasm for the book gradually increased. While the book is addressed perhaps more to students in computation and in CS, it is very attractive also as a text to be used in mainstream mathematics, and in probability theory.

It begins with a new look at the classical Kolmogorov construction of measures on infinite product spaces, and asks for explicit ways of labeling them with a class of certain concrete numerical functions. Then it moves onto noiseless coding theory (from communications science), but it stays rooted firmly in classical ideas from Shannon-Kolmogorov communication and information theory.

It is indeed pleasing to see that God still plays dice, not only in quantum theory, but also in such classical areas of math as in number theory.
From the foreword: "...putting Shannon's information theory and Turing's computability theory into a cocktail shaker, and shaking vigorously..."

The book is a second edition 2002, with a number of attractive additions to the first edition from 1994. It will likely work equally well in a course, as for self-study.
The main portion in the book focuses on classical and modern topics in computability, and its connections to randomness; covering concrete halting problems, chaos, cellular automata, algorithms, and their complexity.
Palle Jorgensen, October 2004.