A Computable Universe: Understanding and Exploring Nature As Computation

by Hector Zenil (Editor)

Overview

This volume, with a foreword by Sir Roger Penrose, discusses the foundations of computation in relation to nature.It focuses on two main questions:The contributors are world-renowned experts who have helped shape a cutting-edge computational understanding of the universe. They discuss computation in the world from a variety of perspectives, ranging from foundational concepts to pragmatic models to ontological conceptions and philosophical implications.The volume provides a state-of-the-art collection of technical papers and non-technical essays, representing a field that assumes information and computation to be key in understanding and explaining the basic structure underpinning physical reality. It also includes a new edition of Konrad Zuse's “Calculating Space” (the MIT translation), and a panel discussion transcription on the topic, featuring worldwide experts in quantum mechanics, physics, cognition, computation and algorithmic complexity.The volume is dedicated to the memory of Alan M Turing — the inventor of universal computation, on the 100th anniversary of his birth, and is part of the Turing Centenary celebrations.

Product Details

ISBN-13:	9789814374293
Publisher:	World Scientific Publishing Company, Incorporated
Publication date:	12/21/2012
Pages:	856
Product dimensions:	6.60(w) x 9.20(h) x 1.90(d)

Table of Contents

Foreword R. Penrose xiii

Preface xxxvii

Acknowledgements xliii

1 Introducing the Computable Universe H. Zenil 1

Historical, Philosophical & Foundational Aspects of Computation 21

2 Origins of Digital Computing: Alan Turing, Charles Babbage, & Ada Lovelace D. Swade 23

3 Generating, Solving and the Mathematics of Homo Sapiens. E. Post's Views on Computation L. De Mol 45

4 Machines R. Turner 63

5 Effectiveness N. Dershowitz E. Falkovich 77

6 Axioms for Computability: Do They Allow a Proof of Church's Thesis? W. Sieg 99

7 The Mathematician's Bias ? and the Return to Embodied Computation S. B. Cooper 125

8 Intuitionistic Mathematics and Realizability in the Physical World A. Bauer 143

9 What is Computation? Actor Model versus Turing's Model C. Hewitt 159

Computation in Nature & the Real World 187

10 Reaction Systems: A Natural Computing Approach to the Functioning of Living Cells A. Ehrenfeucht J. Kleijn M. Koutny G. Rozenberg 189

11 Bacteria, Turing Machines and Hyperbolic Cellular Automata M. Margenstern 209

12 Computation and Communication in Unorganized Systems C. Teuscher 231

13 The Many Forms of Amorphous Computational Systems J. Wiedermann 243

14 Computing on Rings G. J. Martínez A. Adamatzky H. V. McIntosh 257

15 Life as Evolving Software G. J. Chaitin 277

16 Computability and Algorithmic Complexity in Economics K. V. Velupillai S. Zambelli 303

17 Blueprint for a Hypercomputer F. A. Doria 333

Computation & Physics & the Physics of Computation 345

18 Information-Theoretic Teleodynamics in Natural and Artificial Systems A. F. Beavers C. D. Harrison 347

19 Discrete Theoretical Processes (DTP) E. Fredkin 365

20 The Fastest Way of Computing All Universes J. Schmidhuber 381

21 The Subjective Computable Universe M. Hutter 399

22 What Is Ultimately Possible in Physics? S. Wolfram 417

23 Universality, Turing Incompleteness and Observers K. Sutner 435

24 Algorithmic Causal Sets for a Computational Spacetime T. Bolognesi 451

25 The Computable Universe Hypothesis M. P. Szudzik 479

26 The Universe is Lawless or "Pantôn chrêmatôn metron anthrôpon einai" C. S. Calude F. W. Meyerstein A. Salomaa 525

27 Is Feasibility in Physics Limited by Fantasy Alone? C. S. Calude K. Svozil 539

The Quantum, Computation & Information 549

28 What is Computation? (How) Does Nature Compute? D. Deutsch 551

29 The Universe as Quantum Computer S. Lloyd 567

30 Quantum Speedup and Temporal Inequalities for Sequential Actions M. Zukowski 583

31 The Contextual Computer A. Cabello 595

32 A Gödel-Turing Perspective on Quantum States Indistinguishable from Inside T. Breuer 605

33 When Humans Do Compute Quantum P. Zizzi 617

Open Discussion Section 629

34 Open Discussion on A Computable Universe A. Bauer T. Bolognesi A. Cabello C. S. Calude L. De Mol F. Doria B. Fredkin C. Hewitt M. Hutter M. Margenstern K. Svozil M. Szudzik C. Teuscher S. Wolfram H. Zenil 631

Live Panel Discussion (transcription) 671

35 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 673

Zusc's Calculating Space 727

36 Calculating Space (Rechnender Raum) K. Zuse 729

Afterword to Konrad Zuse's Calculating Space A. German H. Zenil 787

Index 795