Computable Analysis: An Introduction

Front Cover
Springer Science & Business Media, Sep 14, 2000 - Computers - 288 pages
Is 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
References
269
Index
277
Copyright

Other editions - View all

Common terms and phrases