Computable Universe, A

This volume, with a foreword by Sir Roger Penrose, discusses the foundations of computation in relation to nature.

It focuses on two main questions:

• What is computation?
• How does nature compute?

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.

Contents:

• Foreword (R Penrose)
• Preface
• Acknowledgements
• Introducing the Computable Universe (H Zenil)
• Historical, Philosophical & Foundational Aspects of Computation:
  • Origins of Digital Computing: Alan Turing, Charles Babbage, & Ada Lovelace (D Swade)
  • Generating, Solving and the Mathematics of Homo Sapiens. E Post's Views on Computation (L De Mol)
  • Machines (R Turner)
  • Effectiveness (N Dershowitz & E Falkovich)
  • Axioms for Computability: Do They Allow a Proof of Church's Thesis? (W Sieg)
  • The Mathematician's Bias — and the Return to Embodied Computation (S B Cooper)
  • Intuitionistic Mathematics and Realizability in the Physical World (A Bauer)
  • What is Computation? Actor Model versus Turing's Model (C Hewitt)
• Computation in Nature & the Real World:
  • Reaction Systems: A Natural Computing Approach to the Functioning of Living Cells (A Ehrenfeucht, J Kleijn, M Koutny & G Rozenberg)
  • Bacteria, Turing Machines and Hyperbolic Cellular Automata (M Margenstern)
  • Computation and Communication in Unorganized Systems (C Teuscher)
  • The Many Forms of Amorphous Computational Systems (J Wiedermann)
  • Computing on Rings (G J Martínez, A Adamatzky & H V McIntosh)
  • Life as Evolving Software (G J Chaitin)
  • Computability and Algorithmic Complexity in Economics (K V Velupillai & S Zambelli)
  • Blueprint for a Hypercomputer (F A Doria)
• Computation & Physics & the Physics of Computation:
  • Information-Theoretic Teleodynamics in Natural and Artificial Systems (A F Beavers & C D Harrison)
  • Discrete Theoretical Processes (DTP) (E Fredkin)
  • The Fastest Way of Computing All Universes (J Schmidhuber)
  • The Subjective Computable Universe (M Hutter)
  • What Is Ultimately Possible in Physics? (S Wolfram)
  • Universality, Turing Incompleteness and Observers (K Sutner)
  • Algorithmic Causal Sets for a Computational Spacetime (T Bolognesi)
  • The Computable Universe Hypothesis (M P Szudzik)
  • The Universe is Lawless or “Pantôn chrêmatôn metron anthrôpon einai” (C S Calude, F W Meyerstein & A Salomaa)
  • Is Feasibility in Physics Limited by Fantasy Alone? (C S Calude & K Svozil)
• The Quantum, Computation & Information:
  • What is Computation? (How) Does Nature Compute? (D Deutsch)
  • The Universe as Quantum Computer (S Lloyd)
  • Quantum Speedup and Temporal Inequalities for Sequential Actions (M Żukowski)
  • The Contextual Computer (A Cabello)
  • A Gödel-Turing Perspective on Quantum States Indistinguishable from Inside (T Breuer)
  • When Humans Do Compute Quantum (P Zizzi)
• Open Discussion Section:
  • Open Discussion on A Computable Universe (A Bauer, T Bolognesi, A Cabello, C S Calude, L De Mol, F Doria, E Fredkin, C Hewitt, M Hutter, M Margenstern, K Svozil, M Szudzik, C Teuscher, S Wolfram & H Zenil)
• Live Panel Discussion (transcription):
  • 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)
• Zuse's Calculating Space:
  • Calculating Space (Rechnender Raum) (K Zuse)
  • Afterword to Konrad Zuse's Calculating Space (A German & H Zenil)

Readership: Graduate students who are specialized researchers in computer science, information theory, quantum theory and modern philosophy and the general public who are interested in these subject areas.