## Information and Randomness: An Algorithmic PerspectiveThe first edition of the monograph Information and Randomness: An Algorithmic Perspective by Crist ian Calude was published in 1994. In my Foreword I said: "The research in algorithmic information theory is already some 30 years old. However, only the recent years have witnessed a really vigorous growth in this area. . . . The present book by Calude fits very well in our series. Much original research is presented. . . making the approach richer in consequences than the classical one. Remarkably, however, the text is so self-contained and coherent that the book may also serve as a textbook. All proofs are given in the book and, thus, it is not necessary to consult other sources for classroom instruction. " The vigorous growth in the study of algorithmic information theory has continued during the past few years, which is clearly visible in the present second edition. Many new results, examples, exercises and open prob lems have been added. The additions include two entirely new chapters: "Computably Enumerable Random Reals" and "Randomness and Incom pleteness". The really comprehensive new bibliography makes the book very valuable for a researcher. The new results about the characterization of computably enumerable random reals, as well as the fascinating Omega Numbers, should contribute much to the value of the book as a textbook. The author has been directly involved in these results that have appeared in the prestigious journals Nature, New Scientist and Pour la Science. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Mathematical Background | 1 |

12 Computability Theory | 4 |

13 Topology | 6 |

14 Probability Theory | 8 |

15 Exercises and Problems | 19 |

Noiseless Coding | 21 |

22 Instantaneous Coding | 24 |

23 Exercises and Problems | 30 |

66 The Randomness Hypothesis | 229 |

67 Exercises and Problems | 231 |

68 History of Results | 233 |

Computably Enumerable Random Reals | 237 |

72 Is Randomness Base Invariant? | 240 |

73 Most Reals Obey No Probability Laws | 253 |

74 Computable and Uncomputable Reals | 260 |

75 Computably Enumerable Reals Domination and Degrees | 271 |

24 History of Results | 32 |

Programsize | 33 |

32 Computers and Complexities | 34 |

33 Algorithmic Properties of Complexities | 43 |

34 Quantitative Estimates | 45 |

35 Halting Probabilities | 47 |

36 Exercises and Problems | 49 |

37 History of Results | 52 |

Computably Enumerable Instantaneous Codes | 53 |

42 Relativized Complexities and Probabilities | 60 |

43 Speedup Theorem | 70 |

44 Algorithmic Coding Theorem | 74 |

45 Binary vs Nonbinary Coding 1 | 85 |

46 Exercises and Problems | 89 |

47 History of Results | 91 |

Random Strings | 95 |

52 Chaitins Definition of Random Strings | 102 |

53 Relating Complexities K and H | 107 |

54 A Statistical Analysis | 109 |

55 A Computational Analysis | 119 |

56 Borel Normality | 123 |

57 Extensions of Random Strings | 131 |

58 Binary vs Nonbinary Coding 2 | 136 |

59 Exercises and Problems | 140 |

510 History of Results | 145 |

Random Sequences | 147 |

62 The Definition of Random Sequences | 158 |

63 Characterizations of Random Sequences | 169 |

64 Properties of Random Sequences | 184 |

65 The Reducibility Theorem | 204 |

76 A Characterization of Computably Enumerable Random Reals | 294 |

77 Degreetheoretic Properties of Computably Enumerable Random Reals | 302 |

78 Exercises and Problems | 310 |

79 History of Results | 313 |

Randomness and Incompleteness | 315 |

82 Informationtheoretic Incompleteness 1 | 320 |

83 Informationtheoretic Incompleteness 2 | 324 |

84 Informationtheoretic Incompleteness 3 | 328 |

85 Coding Mathematical Knowledge | 332 |

86 Finitely Refutable Mathematical Problems | 335 |

87 Computing 64 Bits of a Computably Enumerable Random Real | 343 |

88 Turings Barrier Revisited | 355 |

89 History of Results | 358 |

Applications | 361 |

92 The Undecidability of the Halting Problem | 362 |

93 Counting as a Source of Randomness | 363 |

94 Randomness and Chaos | 366 |

95 Randomness and Cellular Automata | 367 |

96 Random Sequences of Reals and Riemanns Zetafunction | 383 |

97 Probabilistic Algorithms | 389 |

98 Structural Complexity | 393 |

99 What Is Life? | 398 |

910 Randomness in Physics | 405 |

911 Metaphysical Themes | 409 |

Open Problems | 415 |

Bibliography | 419 |

455 | |

457 | |

461 | |

### Common terms and phrases

algorithm Algorithmic Information Theory alphabet arbitrary assume binary bits Borel normal C. S. Calude c.e. real c.e. set computable real Computably Enumerable consider construct contradiction Corollary cube patterns define definition denote digits elements equivalent example exists a constant exists a natural formal Ft(x Ft+i(x function f H(string(n halting probability Halting Problem Hence induction hypothesis inequality infinite integer Invariance Theorem Kraft-Chaitin Theorem Lemma Let f lexicographical order mathematical measure natural numbers non-computable non-random non-terminal null set Omega Number open sets p.c. function prefix prefix code prefix-free set product topology program-size complexity Proof prove RANDf random real random sequence random strings real numbers register machine representation result satisfying self-delimiting semi-measure sequence of rationals sequential Martin-Lof test Show side length Solovay strings of length subset theory topology Turing Turing degree universal Chaitin computer