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.