Information and Randomness: An Algorithmic Perspective

Front Cover
Springer Science & Business Media, Sep 12, 2002 - Computers - 467 pages
0 Reviews
The 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
Notation Index
455
Subject Index
457
Name Index
461
Copyright

Common terms and phrases

References to this book

All Book Search results »