Computable Analysis: An IntroductionIs the exponential function computable? Are union and intersection of closed subsets of the real plane computable? Are differentiation and integration computable operators? Is zero finding for complex polynomials computable? Is the Mandelbrot set decidable? And in case of computability, what is the computational complexity? Computable analysis supplies exact definitions for these and many other similar questions and tries to solve them. - Merging fundamental concepts of analysis and recursion theory to a new exciting theory, this book provides a solid basis for studying various aspects of computability and complexity in analysis. It is the result of an introductory course given for several years and is written in a style suitable for graduate-level and senior students in computer science and mathematics. Many examples illustrate the new concepts while numerous exercises of varying difficulty extend the material and stimulate readers to work actively on the text. |
Contents
1 Introduction | 1 |
12 Why a New Introduction? | 2 |
13 A Sketch of TTE | 3 |
132 A Naming System for Real Numbers | 4 |
134 Subsets of Real Numbers | 7 |
135 The Space C0 1 of Continuous Functions | 8 |
136 Computational Complexity of Real Functions | 9 |
14 Prerequisites and Notation | 10 |
62 Computable Operators on Functions Sets and Numbers | 163 |
63 ZeroFinding | 173 |
64 Differentiation and Integration | 182 |
65 Analytic Functions | 190 |
7 Computational Complexity | 195 |
72 Complexity Induced by the Signed Digit Representation | 204 |
73 The Complexity of Some Real Functions | 218 |
74 Complexity on Compact Sets | 230 |
2 Computability on the Cantor Space | 13 |
21 Type2 Machines and Computable String Functions | 14 |
22 Computable String Functions are Continuous | 27 |
23 Standard Representations of Sets of Continuous String Functions | 33 |
24 Effective Subsets | 43 |
3 Naming Systems | 51 |
32 Admissible Naming Systems | 62 |
33 Constructions of New Naming Systems | 75 |
4 Computability on the Real Numbers | 85 |
42 Computable Real Numbers | 101 |
43 Computable Real Functions | 108 |
5 Computability on Closed Open and Compact Sets | 123 |
52 Compact Sets | 143 |
6 Spaces of Continuous Functions | 153 |
8 Some Extensions | 237 |
82 Degrees of Discontinuity | 244 |
9 Other Approaches to Computable Analysis | 249 |
92 Grzegorczyks Characterizations | 250 |
93 The PourElRichards Approach | 252 |
94 Kos Approach | 254 |
95 Domain Theory | 256 |
96 Markovs Approach | 258 |
97 The realRAM and Related Models | 260 |
98 Comparison | 266 |
269 | |
277 | |
Other editions - View all
Common terms and phrases
bound Cauchy representation Cb(n choice function closed set compact set compact subsets computability concept computable analysis computable function computable real functions computable real numbers computable sequence computable topological space computational complexity Consider continuous functions Corollary countable Define computable Definition digit dist dom(f dom(ƒ dom(h dom(p domain effective topological space equivalent Example Exercise final topology finite follows func function f ƒ is computable infinite sequences input tape Klaus Weihrauch Lemma Let f lookahead M₁ metric space modulus of continuity modulus of convergence multi-valued function naming systems natural numbers non-empty notation open intervals open sets open subsets output tape p)-computable p)-continuous Pb,n polynomial prefix Proof properties Prove putable r.e. open rational numbers Sect Show standard representation subbase subword symbols Theorem tion translates Turing machine Type-2 machine vq)-computable words Y₁ zero Σω