New Computational Paradigms (eBook)

Changing Conceptions of What is Computable

S.B. Cooper, Benedikt Löwe, Andrea Sorbi (Herausgeber)

eBook Download: PDF

2007 | 2008
XIV, 560 Seiten
Springer New York (Verlag)
978-0-387-68546-5 (ISBN)

Infos

This superb exposition of a complex subject 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. 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 "e;computation"e; and "e;proof"e; 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.

Inhalt

Contents 5
Preface 8
List of Contributors 10
Alan Turing’s Legacy and New Computational Paradigms 13
Alan Turing, Logical and Physical 14
1 Delilah day 14
2 The shock of the new 15
3 Everything is really continuous 20
4 Back to the nature of the physical world 23
References 24
The Turing Model of Computation and its Applications to Logic, Mathematics, Philosophy, and Computer Science 27
Computability and Numberings 28
Introduction 28
1 Computable numberings in the hyperarithmetical hierarchy 29
2 Isomorphism types of Rogers semilattices 36
References 41
Computation as Conversation 44
1 Information flow for children and logical dynamics 44
2 Multi-agent information models and epistemic logic 45
3 Conversation as computation: update actions 48
4 Dynamic-epistemic logics of informative events 50
5 Program structures in conversation 53
6 Complexity of logical tasks 54
7 Reversing the direction: computation as conversation 56
8 Merging computation and conversation 57
9 Toward a general theory: transformations and merges 62
10 Conclusions 63
References 65
Computation Paradigms in Light of Hilbert’s Tenth Problem 68
1 Statement Of The Problem: Intuitive Notion Of Algorithm 68
2 Equations: From Words To Numbers 71
3 Davis’s Conjecture: From Algorithms To Sets 71
4 Davis’s Conjecture: First Step To The Proof Via Arithmetization 72
5 Original Proof Of Davis: Post’s Normal Forms 72
6 Davis’s Conjecture Proved: Effectively Enumerable Sets Are Diophantine 73
7 Existential Arithmetization I: Turing Machines 74
8 Existential Arithmetization II: Register Machines 74
9 Existential Arithmetization III: Partial Recursive Functions 74
10 Universality In Number Theory: Collapse Of Diophantine Hierarchy 75
11 Growth Of Solutions: Speeding Up Diophantine Equations 77
12 Diophantine Machines: Capturing Nondeterminism 77
13 Unambiguity: Equations With Unique Solution 78
14 Diophantine Complexity: D vs. NP 79
15 Algorithms For Algorithms: Undecidable Properties Of Programs 80
16 Parallel Computations: Calculation Of A Polynomial On A Petri Net 80
17 A Step Above Hilbert’s Tenth Problem: Computational Chaos In Number Theory And Game Theory 81
18 Unification: It Is Hard To Make Things Equal 82
19 Simple Set: Diophantine Games Are Difficult 83
20 Continuous Variables: Limitations Of Computer Algebra 84
21 DNA Recombination And Metabolism: Models Of Computation Motivated By Biology 85
22 Other Kinds Of Impossibilities: Non-Algorithmical Corollaries Of Algorithmical Results 86
23 Future Research: Back To Diophantus 86
References 88
Elementary Algorithms and Their Implementations 95
1 Recursive (McCarthy) programs 96
2 Recursive machines 99
3 Monotone recursors and recursor isomorphism 103
4 The representation of abstract machines by recursors 105
5 Recursor reducibility and implementations 109
6 Machine simulation and recursor reducibility 116
7 Elementary (first-order) recursive algorithms 117
8 Appendix 121
References 126
Applications of the Kleene–Kreisel Density Theorem to Theoretical Computer Science 127
1 Introduction 127
2 A modern view of the Kleene–Kreisel functionals 128
3 The Cook–Berger Problem 134
4 Replacing the natural numbers with the real numbers 136
5 Density and probability 143
References 144
Church Without Dogma: Axioms for Computability 147
Background 147
1 Church Canons 148
2 Computors 151
3 Axiomatics 155
4 Adequacy and Philosophical Errors 158
References 159
Computability on Topological Spaces via Domain Representations 161
1 Introduction 161
2 Computability on topological spaces: some principles, approaches, and history 163
3 Approximations, orderings, and domains 167
4 Continuous functions and algebraic domains 170
5 Domain representations 171
6 Effectivity 174
7 Classes of domain representations 178
8 TTE and domain representability 182
9 Standard constructions 184
10 Applications 191
References 198
On the Power of Broadcasting in Mobile Computing 203
1 Introduction 203
2 Wireless Parallel Turing Machine 205
3 The Power of the Wireless Communication 210
4 Conclusion 216
References 216
Logic, Algorithms and Complexity 218
The Computational Power of Bounded Arithmetic from the Predicative Viewpoint 219
1 Introduction 219
2 Definitions 220
3 Upper bound 223
4 Lower bound 224
References 227
Effective Uniform Bounds from Proofs in Abstract Functional Analysis 229
1 Introduction 229
2 Logical metatheorems 230
3 Applications of proof mining in approximation theory 234
4 Effective computation of fixed points for functions of contractive type 241
5 Fixed points and approximate fixed points of nonexpansive functions in hyperbolic spaces 246
6 Bounds on asymptotic regularity in the uniformly convex case 256
References 260
Effective Fractal Dimension in Algorithmic Information Theory 265
1 Introduction 265
2 Fractal dimensions and gale characterizations 267
3 Finite-state dimension 276
4 Constructive dimension 282
5 Resource-bounded dimension 286
References 288
Metamathematical Properties of Intuitionistic Set Theories with Choice Principles 292
1 Introduction 292
2 Choice principles 297
3 The partial combinatory algebra Kl 299
4 The general realizability structure 301
5 Defining realizability 302
6 Extending the interpretation to IZF 304
7 Realizability for choice principles 307
References 316
New Developments in Proofs and Computations 318
1 Arithmetic in Finite Types 320
2 Gödel’s Dialectica Interpretation 325
3 Gödel’s Dialectica Interpretation With Majorants 337
References 344
Models of Computation from Nature 346
From Cells to (Silicon) Computers, and Back 347
1 Preliminary warnings 347
2 What is a computation? 348
3 Does nature compute? 349
4 The limits of current computers 350
5 The promises of natural computing 352
6 Everything goes back to Turing 353
7 A (simulated) wondering: why are genetic algorithms so good? 355
8 Adleman experiment 355
9 DNA computing, pros and cons 356
10 The marvellous DNA molecule 358
11 Computing by splicing 359
12 What does it mean to compute “in a natural way?” 361
13 The marvellous cell 362
14 A glimpse to membrane computing 364
15 At the edge of science fiction 367
16 Do we dream too much? 369
17 Closing remarks 371
References 372
Computer Science, Informatics, and Natural Computing— Personal Reflections 376
Acknowledgments 381
References 382
Computable Analysis and Real Computation 383
A Survey on Continuous Time Computations 384
1 Introduction 384
2 Continuous Time Models 386
3 ODEs and properties 394
4 Toward a complexity theory 403
5 Noise and Robustness 408
6 Conclusion 411
References 413
A Tutorial on Computable Analysis 425
1 Introduction 425
2 Preliminaries 427
3 Computable Real Numbers 428
4 Computable Functions 434
5 Computability Notions for Subsets of Euclidean Space 444
6 Representations and Topological Considerations 450
7 Solvability of Some Problems Involving Sets and Functions 457
8 Computability of Linear Operators 465
9 Degrees of Unsolvability 470
10 Computational Complexity of Real Numbers and Real Number Functions 475
11 Computational Complexity of Sets and Operators over the Real Numbers 481
Acknowledgments 485
References 485
A Continuous Derivative for Real-Valued Functions 492
1 Introduction 492
2 Some properties related to the dual of a Banach space 497
3 Ties of functions 500
4 The L-derivative 505
5 Domain for Lipschitz functions 508
6 L-derivative in finite dimensions 510
7 Computability 512
8 Relation with generalized gradient 514
9 Further work and open problems 516
References 517
Infinite Time Computable Model Theory 519
1 Introduction 519
2 Arithmetic on the real line 528
3 The infinite time computable Completeness Theorem 532
4 The infinite time computable Löwenheim–Skolem Theorem 539
5 Computable quotient presentations 543
6 The infinite time analog of Schröder–Cantor–Bernstein–Myhill 548
7 Some infinite time computable transitive models of set theory 552
8 Future directions 554
References 555
Index 556

Produkt-Details

• Erscheint lt. Verlag: 28.11.2007
• Zusatzinfo: XIV, 560 p.
• Verlagsort: New York
• Sprache: englisch
• Themenwelt: Geisteswissenschaften
• Themenwelt: Mathematik / Informatik ► Informatik ► Theorie / Studium
• Themenwelt: Mathematik / Informatik ► Mathematik ► Angewandte Mathematik
• Themenwelt: Mathematik / Informatik ► Mathematik ► Logik / Mengenlehre
• Themenwelt: Naturwissenschaften ► Physik / Astronomie
• Themenwelt: Technik
• Schlagworte: algorithms • Analysis • Complexity • Complexity theory • Computability Theory • Computer • Computer Science • Information Theory • Logic • Mathematical Logic • model Theory • Philosophy • Proof theory
• ISBN-10: 0-387-68546-4 / 0387685464
• ISBN-13: 978-0-387-68546-5 / 9780387685465