## 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. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

1 | |

Computability on the Cantor Space | 13 |

Naming Systems 51 | 50 |

Computability on the Real Numbers | 85 |

Computability on Closed Open and Compact Sets | 123 |

Spaces of Continuous Functions | 153 |

Computational Complexity | 195 |

Some Extensions | 237 |

Other Approaches to Computable Analysis | 249 |

269 | |

277 | |

### Other editions - View all

### Common terms and phrases

A C R admissible representations Cauchy representation choice function closed set compact set compact subsets computability concept computable function computable real functions computable real numbers computable sequence computable topological space computational complexity Consider continuous functions Corollary countable Define computable Definition dom(f dom(h dom(p domain effective topological space equivalent Example Exercise f C R f is computable final topology finite follows function f C X infinite sequences input tape Lemma Let f lookahead 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 polynomial prefix Proof properties Prove pseudometric space putable r.e. open rational numbers recursive open Sect standard representation subbase subword symbols Theorem tion Turing machine Type-2 machine words