Randomness Through Computation: Some Answers, More Questions

by Hector Zenil (Editor)

Overview

This review volume consists of a set of chapters written by leading scholars, most of them founders of their fields. It explores the connections of Randomness to other areas of scientific knowledge, especially its fruitful relationship to Computability and Complexity Theory, and also to areas such as Probability, Statistics, Information Theory, Biology, Physics, Quantum Mechanics, Learning Theory and Artificial Intelligence. The contributors cover these topics without neglecting important philosophical dimensions, sometimes going beyond the purely technical to formulate age old questions relating to matters such as determinism and free will.The scope of Randomness Through Computation is novel. Each contributor shares their personal views and anecdotes on the various reasons and motivations which led them to the study of Randomness. Using a question and answer format, they share their visions from their several distinctive vantage points.

Product Details

ISBN-13:	9789814327749
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	02/15/2011
Pages:	440
Product dimensions:	6.10(w) x 9.10(h) x 1.10(d)

Table of Contents

Preface vii

Acknowledgments xiii

Part I Stochastic Randomness and Probabilistic Deliberations

1 Is Randomness Necessary? R. Graham 3

2 Probability is a Lot of Logic at Once: If You Don't Know Which One to Pick, Take 'em All T. Toffoli 7

3 Statistical Testing of Randomness: New and Old Procedures A. L. Rukhin 33

4 Scatter and Regularity Imply Benford's Law … and More N. Gauvrit J.-P. Delahaye 53

Part II Randomness and Computation in Connection to the Physical World

5 Some Bridging Results and Challenges in Classical, Quantum and Computational Randomness G. Longo C. Palamidessi T. Paul 73

6 Metaphysics, Metamathematics and Metabiology G. Chaitin 93

7 Uncertainty in Physics and Computation M. A. Stay 105

8 Indeterminism and Randomness Through Physics K. Svozil 109

9 The Martin-Löf-Chaitin Thesis: The Identification by Recursion Theory of the Mathematical Notion of Random Sequence J.-P. Delahaye 121

10 The Road to Intrinsic Randomness S. Wolfram 141

Part III Algorithmic Inference and Artificial Intelligence

11 Algorithmic Probability - Its Discovery - Its Properties and Application to Strong AI R. J. Solomonoff 149

12 Algorithmic Randomness as Foundation of Inductive Reasoning and Artificial Intelligence M. Hutter 159

13 Randomness, Occam's Razor, AI, Creativity and Digital Physics J. Schmidhuber 171

Part IV Randomness, Information and Computability

14 Randomness Everywhere: My Path to Algorithmic Information Theory C. S. Calude 179

15 The Impact of Algorithmic Information Theory on Our Current Views on Complexity, Randomness, Information and Prediction P. Gács 191

16 Randomness, Computability and Information J. S. Miller 197

17 Studying Randomness Through Computation A. Nies 207

18 Computability, Algorithmic Randomness and Complexity R. G. Downey 223

19 Is Randomness Native to Computer Science? Ten Years After M. Ferbus-Zanda S. Grigorieff 243

Part V Computational Complexity, Randomized Algorithms and Applications

20 Randomness as Circuit Complexity (and the Connection to Pseudorandomness) E. Allender 267

21 Randomness: A Tool for Constructing and Analyzing Computer Programs A. Kucera 275

22 Connecting Randomness to Computation M. Li 283

23 From Error-correcting Codes to Algorithmic Information Theory L. Staiger 293

24 Randomness in Algorithms O. Watanabe 297

Part VI Panel Discussions (Transcriptions)

25 Is the Universe Random? C. S. Calude J. L. Casti G. J. Chaitin P. C. W. Davits K. Svozil S. Wolfram 309

26 What is Computation? (How) Does Nature Compute? C. S. Calude G. J. Chaitin E. Fredkin A. J. Leggett R. de Ruyter T. Toffoli S. Wolfram 351

Author Index 405

Subject Index 411