Information and Randomness

by Calude, Cristian S.; Chaitin, Gregory J.; Salomaa, Arto

• ISBN13: 9783540434665
• ISBN10: 3540434666
• Edition: 2nd
• Format: Hardcover
• Copyright: 2002-12-01
• Publisher: Springer-Verlag New York Inc

Summary

The book presents in a mathematical clear way the fundamentals of algorithmic information theory and a few selected applications. This 2nd edition presents new and important results obtained in recent years: the characterization of computable enumerable random reals, the construction of an Omega Number for which ZFC cannot determine any digits, and the first successful attempt to compute the exact values of 64 bits of a specific Omega Number. Finally, the book contains a discussion of some interesting philosophical questions related to randomness and mathematical knowledge. "Professor Calude has produced a first-rate exposition of up-to-date work in information and randomness." D.S. Bridges, Canterbury University, co-author, with Errett Bishop, of Constructive Analysis; "The second edition of this classic work is highly recommended to anyone interested in algorithmic information and randomness." G.J. Chaitin, IBM Research Division, New York, author of Conversations with a Mathematician; "This book is a must for a comprehensive introduction to algorithmic information theory and for anyone interested in its applications in the natural sciences." K. Svozil, Technical University of Vienna, author of Randomness & Undecidability in Physics

Table of Contents

Mathematical Background	1	(20)
Prerequisites	1	(3)
Computability Theory	4	(2)
Topology	6	(2)
Probability Theory	8	(11)
Exercises and Problems	19	(2)
Noiseless Coding	21	(12)
Prefix-free Sets	21	(3)
Instantaneous Coding	24	(6)
Exercises and Problems	30	(2)
History of Results	32	(1)
Program-size	33	(20)
An Example	33	(1)
Computer and Complexities	34	(9)
Algorithmic Properties of Complexities	43	(2)
Quantitative Estimates	45	(2)
Hating Probabilities	47	(2)
Exercises and Problems	49	(3)
History of Results	52	(1)
Computably Enumerable Instantaneous Codes	53	(42)
The Kraft-Chaitin Theorem	53	(7)
Relativized Complexities and Probabilities	60	(10)
Speed-up Theorem	70	(4)
Algorithmic Coding Theorem	74	(11)
Binary vs Non-binary Coding (1)	85	(4)
Exercises and Problems	89	(2)
History of Results	91	(4)
Random Strings	95	(52)
An Empirical Analysis	95	(7)
Chaitin's Definition of Random Strings	102	(5)
Relating Complexities K and H	107	(2)
A Statistical Analysis	109	(10)
A Computational Analysis	119	(4)
Borel Normality	123	(8)
Extensions of Random Strings	131	(5)
Binary vs Non-binary Coding (2)	136	(4)
Exercises and Problems	140	(5)
History of Results	145	(2)
Random Sequences	147	(90)
From Random Strings to Random Sequences	147	(11)
The Definition of Random Sequences	158	(11)
Characterizations of Random Sequences	169	(15)
Properties of Random Sequences	184	(20)
The Reducibility Theorem	204	(25)
The Randomness Hypothesis	229	(2)
Exercises and Problems	231	(2)
History of Results	233	(4)
Computably Enumerable Random Reals	237	(78)
Chaitin's Omega Number	237	(3)
Is Randomnes Base Invariant?	240	(13)
Most Reals Obey No Probability Laws	253	(7)
Computable and Uncomputable Reals	260	(11)
Computably Enumerable Reals, Domination and Degrees	271	(23)
A Characterization of Computably Enumerable Random Reals	294	(8)
Degree-theoretic Properties of Computably Enumerable Random Reals	302	(8)
Exercises and Problems	310	(3)
History of Results	313	(2)
Randomness and Incompleteness	315	(46)
The Incompleteness Phenomenon	315	(5)
Information-theoretic Incompleteness (1)	320	(4)
Information-theoretic Incompleteness (2)	324	(4)
Information-theoretic Incompleteness (3)	328	(4)
Coding Mathematical Knowledge	332	(3)
Finitely Refutable Mathematical Problems	335	(8)
Computing 64 Bits of a Computably Enumerable Random Real	343	(12)
Turing's Barrier Revisited	355	(3)
History of Results	358	(3)
Applications	361	(54)
The Infinity of Primes	361	(1)
The Undecidability of the Halting Problem	362	(1)
Counting as a Source of Randomness	363	(3)
Randomness and Chaos	366	(1)
Randomness and Cellular Automata	367	(16)
Random Sequences of Reals and Riemann's Zeta-function	383	(6)
Probabilistic Algorithms	389	(4)
Structural Complexity	393	(5)
What Is Life?	398	(7)
Randomness in Physics	405	(4)
Metaphysical Themes	409	(6)
Open Problems	415	(4)
Bibliography	419	(36)
Notation Index	455	(2)
Subject Index	457	(4)
Name Index	461