The Incomputable: Journeys Beyond the Turing Barrier

Description

This book questions the relevance of computation to the physical universe. Our theories deliver computational descriptions, but the gaps and discontinuities in our grasp suggest a need for continued discourse between researchers from different disciplines, and this book is unique in its focus on the mathematical theory of incomputability and its relevance for the real world. The core of the book consists of thirteen chapters in five parts on extended models of computation; the search for natural examples of incomputable objects; mind, matter, and computation; the nature of information, complexity, and randomness; and the mathematics of emergence and morphogenesis. This book will be of interest to researchers in the areas of theoretical computer science, mathematical logic, and philosophy. Front Matter....Pages i-x Introduction....Pages 1-8 Front Matter....Pages 9-9 Ivan Soskov: A Life in Computability....Pages 11-46 Physical Logic....Pages 47-61 From Quantum Foundations via Natural Language Meaning to a Theory of Everything....Pages 63-80 Front Matter....Pages 81-81 Some Recent Research Directions in the Computably Enumerable Sets....Pages 83-93 Uncomputability and Physical Law....Pages 95-104 Algorithmic Economics: Incomputability, Undecidability and Unsolvability in Economics....Pages 105-120 Front Matter....Pages 121-121 Is Quantum Physics Relevant for Life?....Pages 123-131 Trouble with Computation: A Refutation of Digital Ontology....Pages 133-140 Front Matter....Pages 141-141 Complexity Barriers as Independence....Pages 143-168 Quantum Randomness: From Practice to Theory and Back....Pages 169-181 Calculus of Cost Functions....Pages 183-216 Front Matter....Pages 217-217 Turing’s Theory of Morphogenesis: Where We Started, Where We Are and Where We Want to Go....Pages 219-235 Construction Kits for Biological Evolution....Pages 237-292