Computable Analysis

by Weihrauch, Klaus; Brauer, W.; Rozenberg, G.; Salomaa, A.

• ISBN13: 9783540668176
• ISBN10: 3540668179
• Format: Hardcover
• Copyright: 2000-12-01
• Publisher: Springer Verlag

Summary

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.

Table of Contents

Introduction	1	(12)
The Aim of Computable Analysis	1	(1)
Why a New Introduction?	2	(1)
A Sketch of TTE	3	(7)
A Model of Computation	3	(1)
A Naming System for Real Numbers	4	(1)
Computable Real Numbers and Functions	4	(3)
Subsets of Real Numbers	7	(1)
The Space C[0; 1] of Continuous Functions	8	(1)
Computational Complexity of Real Functions	9	(1)
Prerequisites and Notation	10	(3)
Computability on the Cantor Space	13	(38)
Type-2 Machines and Computable String Functions	14	(13)
Computable String Functions are Continuous	27	(6)
Standard Representations of Sets of Continuous String Functions	33	(10)
Effective Subsets	43	(8)
Naming Systems	51	(34)
Continuity and Computability Induced by Naming Systems	51	(11)
Admissible Naming Systems	62	(13)
Constructions of New Naming Systems	75	(10)
Computability on the Real Numbers	85	(38)
Various Representations of the Real Numbers	85	(16)
Computable Real Numbers	101	(7)
Computable Real Functions	108	(15)
Computability on Closed, Open and Compact Sets	123	(30)
Closed Sets and Open Sets	123	(20)
Compact Sets	143	(10)
Spaces of Continuous Functions	153	(42)
Various representations	153	(10)
Computable Operators on Functions, Sets and Numbers	163	(10)
Zero-Finding	173	(9)
Differentiation and Integration	182	(8)
Analytic Functions	190	(5)
Computational Complexity	195	(42)
Complexity of Type-2 Machine Computations	195	(9)
Complexity Induced by the Signed Digit Representation	204	(14)
The Complexity of Some Real Functions	218	(12)
Complexity on Compact Sets	230	(7)
Some Extensions	237	(12)
Computable Metric Spaces	237	(7)
Degrees of Discontinuity	244	(5)
Other Approaches to Computable Analysis	249	(20)
Banach/Mazur Computability	249	(1)
Grzegorczyk's Characterizations	250	(2)
The Pour-El/Richards Approach	252	(2)
Ko's Approach	254	(2)
Domain Theory	256	(2)
Markov's Approach	258	(2)
The real-RAM and Related Models	260	(6)
Comparison	266	(3)
References	269	(8)
Index	277