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.
Description-Table Of Contents
1. Introducing the computable universe / H. Zenil -- 2. Origins of digital computing: Alan Turing, Charles Babbage, & Ada Lovelace / D. Swade -- 3. Generating, solving and the mathematics of Homo sapiens. E. Post's views on computation / L. De Mol -- 4. Machines / R. Turner -- 5. Effectiveness / N. Dershowitz & E. Falkovich -- 6. Axions for computability: do they allow a proof of Church's thesis / W. Sieg -- 7. The mathematician's bias - and the return to embodied computation / S. B. Cooper -- 8. Intuitionistic mathematics and realizability in the physical world / A. Baver -- 9. What is computation? Actor model versus Turing's model / C. Hewitt -- 10. Reaction systems: a natural computing approach to the functioning of living cells / A. Ehrenfeucht ... [et al.] -- 11. Bacteria, Turing machines and hyperbolic cellular automata / M. Margenstern -- 12. Computation and communication in unorganized systems / C. Teuscher -- 13. The many forms of amorphous computational systems / J. Wiedermann -- 14. Computing on rings / G. J. Martinez, A. Adamatzky & H. V. McIntosh -- 15. Life as evolving software / G. J. Chaitin -- 16. Computability and algorithmic complexity in economics / K. V. Velupillai & S. Zambelli -- 17. Blueprint for a hypercomputer / F. A. Doria -- 18. Information-theoretic teleodynamics in natural and artificial systems / A. F. Beavers & C. D. Harrison -- 19. Discrete theoretical processes (DTP) / E. Fredkin -- 20. The fastest way of computing all universes / J. Schmidhuber -- 21. The subjective computable universe / M. Hutter -- 22. What is ultimately possible in physics / S. Wolfram -- 23. University, Turing incompleteness and observers / K. Sutner -- 24. Algorithmic causal sets for a computational spacetime / T. Bolognesi -- 25. The computable universe hypothesis / M. P. Szudzik -- 26. The universe is lawless or """"panton chrematon metron anthropon einai"""" / C. S. Calude, F. W. Meyerstein & A. Salomaa -- 27. Is feasibility in physics limited by fantasy alone? / C. S. Calude & K. Svozil -- 28. What is computation? (How) does nature compute? / D. Deutsch -- 29. The universe as quantum computer / S. Lloyd -- 30. Quantum speedup and temporal inequalities for sequential actions / M. Zukowski -- 31. The contextual computer / A. Cabello -- 32. A Godel-Turing perspective on quantum states indistinguishable from inside / T. Breuer -- 33. When humans do compute quantum / P. Zizzi -- 34. Open discussion on a computable universe / A. Bauer ... [et al.] -- 35. What is computation? (How) does nature compute? / C. S. Calude ... [et al.] -- 36. Calculating space (Rechnender Raum) / K. Zuse -- Afterword to Konrad Zuse's Calculating Space / A. German & H. Zenil.
