Springer-Verlag, EATCS Monographs on Theoretical Computer Science
                Series Eds.: W.Brauer, G. Rozenberg, A.Salomaa

            INFORMATION AND RANDOMNESS. AN ALGORITHMIC PERSPECTIVE

          by Cristian Calude, The University of Auckland, New Zealand

Forewords by G.J.Chaitin and A.Salomaa

  ``Algorithmic information theory (AIT) is the result of putting Shannon's
information theory and Turing's computability theory into a cocktail shaker and
shaking vigorously" says G.J.Chaitin, one of the founders of this theory. (AIT)
provides a mathematical definitio of what it means for a string or sequence of
bits to be random, unpredictable, typical. It is also relevant for Logic (a new
light on G\"{o}del's incompleteness phenomenon is obtained by analysing the
information-theoretic power of axiomatic systems), Physics (a characterization
of chaotic physical motion), Biology (How likely is life to appear and evolve?
How common is life in the Universe?), Metaphysics (Is the Universe ordered,
rational or random?).
  ``This book, benefiting as it does from Cristian Calude's own research in AIT
and from his experience teaching AIT in university courses around the world,
should help to make the detailed mathematical techniques of AIT accessible to
a much wider audience.'' (G.J.Chaitin)

 Contents: Mathematical Background; Noiseless Coding; Program Size;
           Recursively Enumerable Instantaneous Codes; Random Strings;
           Random Sequences; Applications; Open Problems; Bibliography.
 
  For a more detailed Table of Contents, please open the following URL:
 
http://www.cs.utwente.nl/data/amast/newsletter/sample/issue04/full/IRAPbook.txt

  Readership: Theoretical Computer Science; Mathematics; Logic; Science and
Philosophy

XVI + 238 pages, Pub date: September 1994, Springer-Verlag, ISBN 3-540-57456-5,
DM 68.00, A$ 60.00, NZ$ 72.50 (Price at July 1994)

DETAILED CONTENTS

Mathematical Background
 Prerequisites
 Recursive Function Theory
 Topology
 Probability Theory

Noiseless Coding
 Prefix-Free Sets
 Instantaneous Coding
 Exercises and Problems
 History of Results

Program Size
 An Example
 Computers and Complexities
 Algorithmic Properties of Complexities
 Quantitative Estimates
 Halting Probabilities
 Exercises and Problems
 History of Results

Recursively Enumerable Instantaneous Codes
 The Kraft-Chaitin Theorem
 Relativized Complexities and Probabilities
 Speed-Up Theorem
 Coding Theorem
 Binary vs Non-Binary Coding
 Exercises and Problems
 History of Results

Random Strings
 Empirical Analysis
 Chaitin's Definition of Random Strings
 Relating Complexities  K and  H
 A Statistical Analysis
 A Computational Analysis
 Borel Normality
 Extensions of Random Strings
 Exercises and Problems
 History of Results

Random Sequences
 From Random Strings to Random Sequences
 The Definition of Random Sequences
 Characterizations of Random Sequences
 Properties of Random Sequences
 Reducibility Theorem
 Chaitin's Omega Number
 Is Randomness Robust?
 Exercises and Problems
 History of Results

Applications
 Three Information-Theoretic Proofs
 Information-Theoretic Incompleteness
 Coding Mathematical Knowledge
 Randomness in Mathematics
 Probabilistic Algorithms
 Structural Complexity
 What Is Life?
 Randomness in Physics
 Metaphysical Themes

Open Problems

Bibliography

Notation Index
Subject Index
Author Index