Ebook: New Computational Paradigms: Changing Conceptions of What is Computable

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

---

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

---

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

Content:
Front Matter....Pages i-xiii
Alan Turing, Logical and Physical....Pages 3-15
Computability and Numberings....Pages 19-34
Computation as Conversation....Pages 35-58
Computation Paradigms in Light of Hilbert's Tenth Problem....Pages 59-85
Elementary Algorithms and Their Implementations....Pages 87-118
Applications of the Kleene–Kreisel Density Theorem to Theoretical Computer Science....Pages 119-138
Church Without Dogma: Axioms for Computability....Pages 139-152
Computability on Topological Spaces via Domain Representations....Pages 153-194
On the Power of Broadcasting in Mobile Computing....Pages 195-209
The Computational Power of Bounded Arithmetic from the Predicative Viewpoint....Pages 213-222
Effective Uniform Bounds from Proofs in Abstract Functional Analysis....Pages 223-258
Effective Fractal Dimension in Algorithmic Information Theory....Pages 259-285
Metamathematical Properties of Intuitionistic Set Theories with Choice Principles....Pages 287-312
New Developments in Proofs and Computations....Pages 313-340
From Cells to (Silicon) Computers, and Back....Pages 343-371
Computer Science, Informatics, and Natural Computing—Personal Reflections....Pages 373-379
A Survey on Continuous Time Computations....Pages 383-423
A Tutorial on Computable Analysis....Pages 425-491
A Continuous Derivative for Real-Valued Functions....Pages 493-519
Infinite Time Computable Model Theory....Pages 521-557
Back Matter....Pages 559-559

---

In recent years, classical computability has expanded beyond its original scope to address issues related to computability and complexity in algebra, analysis, and physics. The deep interconnection between "computation" and "proof" has originated much of the most significant work in constructive mathematics and mathematical logic of the last 70 years. Moreover, the increasingly compelling necessity to deal with computability in the real world (such as computing on continuous data, biological computing, and physical models) has brought focus to new paradigms of computation that are based on biological and physical models. These models address questions of efficiency in a radically new way and even threaten to move the so-called Turing barrier, i.e. the line between the decidable and the un-decidable.

This book examines new developments in the theory and practice of computation from a mathematical perspective, with topics ranging from classical computability to complexity, from biocomputing to quantum computing. The book opens with an introduction by Andrew Hodges, the Turing biographer, who analyzes the pioneering work that anticipated recent developments concerning computation’s allegedly new paradigms. The remaining material covers traditional topics in computability theory such as relative computability, theory of numberings, and domain theory, in addition to topics on the relationships between proof theory, computability, and complexity theory. New paradigms of computation arising from biology and quantum physics are also discussed, as well as the computability of the real numbers and its related issues.

This book is suitable for researchers and graduate students in mathematics, philosophy, and computer science with a special interest in logic and foundational issues. Most useful to graduate students are the survey papers on computable analysis and biological computing. Logicians and theoretical physicists will also benefit from this book.

Content:
Front Matter....Pages i-xiii
Alan Turing, Logical and Physical....Pages 3-15
Computability and Numberings....Pages 19-34
Computation as Conversation....Pages 35-58
Computation Paradigms in Light of Hilbert's Tenth Problem....Pages 59-85
Elementary Algorithms and Their Implementations....Pages 87-118
Applications of the Kleene–Kreisel Density Theorem to Theoretical Computer Science....Pages 119-138
Church Without Dogma: Axioms for Computability....Pages 139-152
Computability on Topological Spaces via Domain Representations....Pages 153-194
On the Power of Broadcasting in Mobile Computing....Pages 195-209
The Computational Power of Bounded Arithmetic from the Predicative Viewpoint....Pages 213-222
Effective Uniform Bounds from Proofs in Abstract Functional Analysis....Pages 223-258
Effective Fractal Dimension in Algorithmic Information Theory....Pages 259-285
Metamathematical Properties of Intuitionistic Set Theories with Choice Principles....Pages 287-312
New Developments in Proofs and Computations....Pages 313-340
From Cells to (Silicon) Computers, and Back....Pages 343-371
Computer Science, Informatics, and Natural Computing—Personal Reflections....Pages 373-379
A Survey on Continuous Time Computations....Pages 383-423
A Tutorial on Computable Analysis....Pages 425-491
A Continuous Derivative for Real-Valued Functions....Pages 493-519
Infinite Time Computable Model Theory....Pages 521-557
Back Matter....Pages 559-559
....