Cooper / Löwe / Sorbi New Computational Paradigms

Changing Conceptions of What is Computable
1. Auflage 2007
ISBN: 978-0-387-68546-5
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 560 Seiten

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.

Autoren/Hrsg.

Löwe, Benedikt

Sorbi, Andrea

Cooper, S. B.

Inhaltsverzeichnis

1;Contents;5
2;Preface;8
3;List of Contributors;10
4;Alan Turing’s Legacy and New Computational Paradigms;13
4.1;Alan Turing, Logical and Physical;14
4.1.1;1 Delilah day;14
4.1.2;2 The shock of the new;15
4.1.3;3 Everything is really continuous;20
4.1.4;4 Back to the nature of the physical world;23
4.1.5;References;24
5;The Turing Model of Computation and its Applications to Logic, Mathematics, Philosophy, and Computer Science;27
5.1;Computability and Numberings;28
5.1.1;Introduction;28
5.1.2;1 Computable numberings in the hyperarithmetical hierarchy;29
5.1.3;2 Isomorphism types of Rogers semilattices;36
5.1.4;References;41
5.2;Computation as Conversation;44
5.2.1;1 Information flow for children and logical dynamics;44
5.2.2;2 Multi-agent information models and epistemic logic;45
5.2.3;3 Conversation as computation: update actions;48
5.2.4;4 Dynamic-epistemic logics of informative events;50
5.2.5;5 Program structures in conversation;53
5.2.6;6 Complexity of logical tasks;54
5.2.7;7 Reversing the direction: computation as conversation;56
5.2.8;8 Merging computation and conversation;57
5.2.9;9 Toward a general theory: transformations and merges;62
5.2.10;10 Conclusions;63
5.2.11;References;65
5.3;Computation Paradigms in Light of Hilbert’s Tenth Problem;68
5.3.1;1 Statement Of The Problem: Intuitive Notion Of Algorithm;68
5.3.2;2 Equations: From Words To Numbers;71
5.3.3;3 Davis’s Conjecture: From Algorithms To Sets;71
5.3.4;4 Davis’s Conjecture: First Step To The Proof Via Arithmetization;72
5.3.5;5 Original Proof Of Davis: Post’s Normal Forms;72
5.3.6;6 Davis’s Conjecture Proved: Effectively Enumerable Sets Are Diophantine;73
5.3.7;7 Existential Arithmetization I: Turing Machines;74
5.3.8;8 Existential Arithmetization II: Register Machines;74
5.3.9;9 Existential Arithmetization III: Partial Recursive Functions;74
5.3.10;10 Universality In Number Theory: Collapse Of Diophantine Hierarchy;75
5.3.11;11 Growth Of Solutions: Speeding Up Diophantine Equations;77
5.3.12;12 Diophantine Machines: Capturing Nondeterminism;77
5.3.13;13 Unambiguity: Equations With Unique Solution;78
5.3.14;14 Diophantine Complexity: D vs. NP;79
5.3.15;15 Algorithms For Algorithms: Undecidable Properties Of Programs;80
5.3.16;16 Parallel Computations: Calculation Of A Polynomial On A Petri Net;80
5.3.17;17 A Step Above Hilbert’s Tenth Problem: Computational Chaos In Number Theory And Game Theory;81
5.3.18;18 Unification: It Is Hard To Make Things Equal;82
5.3.19;19 Simple Set: Diophantine Games Are Difficult;83
5.3.20;20 Continuous Variables: Limitations Of Computer Algebra;84
5.3.21;21 DNA Recombination And Metabolism: Models Of Computation Motivated By Biology;85
5.3.22;22 Other Kinds Of Impossibilities: Non-Algorithmical Corollaries Of Algorithmical Results;86
5.3.23;23 Future Research: Back To Diophantus;86
5.3.24;References;88
5.4;Elementary Algorithms and Their Implementations;95
5.4.1;1 Recursive (McCarthy) programs;96
5.4.2;2 Recursive machines;99
5.4.3;3 Monotone recursors and recursor isomorphism;103
5.4.4;4 The representation of abstract machines by recursors;105
5.4.5;5 Recursor reducibility and implementations;109
5.4.6;6 Machine simulation and recursor reducibility;116
5.4.7;7 Elementary (first-order) recursive algorithms;117
5.4.8;8 Appendix;121
5.4.9;References;126
5.5;Applications of the Kleene–Kreisel Density Theorem to Theoretical Computer Science;127
5.5.1;1 Introduction;127
5.5.2;2 A modern view of the Kleene–Kreisel functionals;128
5.5.3;3 The Cook–Berger Problem;134
5.5.4;4 Replacing the natural numbers with the real numbers;136
5.5.5;5 Density and probability;143
5.5.6;References;144
5.6;Church Without Dogma: Axioms for Computability;147
5.6.1;Background;147
5.6.2;1 Church Canons;148
5.6.3;2 Computors;151
5.6.4;3 Axiomatics;155
5.6.5;4 Adequacy and Philosophical Errors;158
5.6.6;References;159
5.7;Computability on Topological Spaces via Domain Representations;161
5.7.1;1 Introduction;161
5.7.2;2 Computability on topological spaces: some principles, approaches, and history;163
5.7.3;3 Approximations, orderings, and domains;167
5.7.4;4 Continuous functions and algebraic domains;170
5.7.5;5 Domain representations;171
5.7.6;6 Effectivity;174
5.7.7;7 Classes of domain representations;178
5.7.8;8 TTE and domain representability;182
5.7.9;9 Standard constructions;184
5.7.10;10 Applications;191
5.7.11;References;198
5.8;On the Power of Broadcasting in Mobile Computing;203
5.8.1;1 Introduction;203
5.8.2;2 Wireless Parallel Turing Machine;205
5.8.3;3 The Power of the Wireless Communication;210
5.8.4;4 Conclusion;216
5.8.5;References;216
6;Logic, Algorithms and Complexity;218
6.1;The Computational Power of Bounded Arithmetic from the Predicative Viewpoint;219
6.1.1;1 Introduction;219
6.1.2;2 Definitions;220
6.1.3;3 Upper bound;223
6.1.4;4 Lower bound;224
6.1.5;References;227
6.2;Effective Uniform Bounds from Proofs in Abstract Functional Analysis;229
6.2.1;1 Introduction;229
6.2.2;2 Logical metatheorems;230
6.2.3;3 Applications of proof mining in approximation theory;234
6.2.4;4 Effective computation of fixed points for functions of contractive type;241
6.2.5;5 Fixed points and approximate fixed points of nonexpansive functions in hyperbolic spaces;246
6.2.6;6 Bounds on asymptotic regularity in the uniformly convex case;256
6.2.7;References;260
6.3;Effective Fractal Dimension in Algorithmic Information Theory;265
6.3.1;1 Introduction;265
6.3.2;2 Fractal dimensions and gale characterizations;267
6.3.3;3 Finite-state dimension;276
6.3.4;4 Constructive dimension;282
6.3.5;5 Resource-bounded dimension;286
6.3.6;References;288
6.4;Metamathematical Properties of Intuitionistic Set Theories with Choice Principles;292
6.4.1;1 Introduction;292
6.4.2;2 Choice principles;297
6.4.3;3 The partial combinatory algebra Kl;299
6.4.4;4 The general realizability structure;301
6.4.5;5 Defining realizability;302
6.4.6;6 Extending the interpretation to IZF;304
6.4.7;7 Realizability for choice principles;307
6.4.8;References;316
6.5;New Developments in Proofs and Computations;318
6.5.1;1 Arithmetic in Finite Types;320
6.5.2;2 Gödel’s Dialectica Interpretation;325
6.5.3;3 Gödel’s Dialectica Interpretation With Majorants;337
6.5.4;References;344
7;Models of Computation from Nature;346
7.1;From Cells to (Silicon) Computers, and Back;347
7.1.1;1 Preliminary warnings;347
7.1.2;2 What is a computation?;348
7.1.3;3 Does nature compute?;349
7.1.4;4 The limits of current computers;350
7.1.5;5 The promises of natural computing;352
7.1.6;6 Everything goes back to Turing;353
7.1.7;7 A (simulated) wondering: why are genetic algorithms so good?;355
7.1.8;8 Adleman experiment;355
7.1.9;9 DNA computing, pros and cons;356
7.1.10;10 The marvellous DNA molecule;358
7.1.11;11 Computing by splicing;359
7.1.12;12 What does it mean to compute “in a natural way?”;361
7.1.13;13 The marvellous cell;362
7.1.14;14 A glimpse to membrane computing;364
7.1.15;15 At the edge of science fiction;367
7.1.16;16 Do we dream too much?;369
7.1.17;17 Closing remarks;371
7.1.18;References;372
7.2;Computer Science, Informatics, and Natural Computing— Personal Reflections;376
7.2.1;Acknowledgments;381
7.2.2;References;382
8;Computable Analysis and Real Computation;383
8.1;A Survey on Continuous Time Computations;384
8.1.1;1 Introduction;384
8.1.2;2 Continuous Time Models;386
8.1.3;3 ODEs and properties;394
8.1.4;4 Toward a complexity theory;403
8.1.5;5 Noise and Robustness;408
8.1.6;6 Conclusion;411
8.1.7;References;413
8.2;A Tutorial on Computable Analysis;425
8.2.1;1 Introduction;425
8.2.2;2 Preliminaries;427
8.2.3;3 Computable Real Numbers;428
8.2.4;4 Computable Functions;434
8.2.5;5 Computability Notions for Subsets of Euclidean Space;444
8.2.6;6 Representations and Topological Considerations;450
8.2.7;7 Solvability of Some Problems Involving Sets and Functions;457
8.2.8;8 Computability of Linear Operators;465
8.2.9;9 Degrees of Unsolvability;470
8.2.10;10 Computational Complexity of Real Numbers and Real Number Functions;475
8.2.11;11 Computational Complexity of Sets and Operators over the Real Numbers;481
8.2.12;Acknowledgments;485
8.2.13;References;485
8.3;A Continuous Derivative for Real-Valued Functions;492
8.3.1;1 Introduction;492
8.3.2;2 Some properties related to the dual of a Banach space;497
8.3.3;3 Ties of functions;500
8.3.4;4 The L-derivative;505
8.3.5;5 Domain for Lipschitz functions;508
8.3.6;6 L-derivative in finite dimensions;510
8.3.7;7 Computability;512
8.3.8;8 Relation with generalized gradient;514
8.3.9;9 Further work and open problems;516
8.3.10;References;517
8.4;Infinite Time Computable Model Theory;519
8.4.1;1 Introduction;519
8.4.2;2 Arithmetic on the real line;528
8.4.3;3 The infinite time computable Completeness Theorem;532
8.4.4;4 The infinite time computable Löwenheim–Skolem Theorem;539
8.4.5;5 Computable quotient presentations;543
8.4.6;6 The infinite time analog of Schröder–Cantor–Bernstein–Myhill;548
8.4.7;7 Some infinite time computable transitive models of set theory;552
8.4.8;8 Future directions;554
8.4.9;References;555
9;Index;556