Skip to main content

2000 | Buch

Computable Analysis

An Introduction

verfasst von: Prof. Dr. Klaus Weihrauch

Verlag: Springer Berlin Heidelberg

Buchreihe : Texts in Theoretical Computer Science An EATCS Series

insite
SUCHEN

Über dieses Buch

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.

Inhaltsverzeichnis

Frontmatter
1. Introduction
Abstract
All over the world numerous computers are used for real number computation. They evaluate real functions, find zeroes of functions, determine eigenvalues and integrals and solve differential equations. They perform, or at least are expected to perform, computations on sets like ℝ (the set of real numbers), ℝn, O(ℝ) (the open subsets of real numbers), K(ℝn) (the compact subsets of ℝn) or C[O; 1] (the continuous functions from the real unit interval to the real numbers). The increasing demand for reliable as well as fast software in scientific computation and engineering requires a sound and broad foundation. We agree with L. Blum et al. [BCSS96] (also in [BCSS98], however, see Sect. 9.7):
Klaus Weihrauch
2. 2. Computability on the Cantor Space
Abstract
Classically, computability is introduced explicitly for functions f :⊆ (Σ*)nΣ* on the set Σ* of finite words over an arbitrary finite alphabet Σ, for example by means of Turing machines. For computing functions on other sets M such as natural numbers, rational numbers or finite graphs, words are used as “code words” or “names” of elements of M. Under this view a machine transforms words to words without “understanding” the meaning given to them by the user. Equivalently, one can start with computable functions on the natural numbers instead of words and use numbers as “names”. Since the set Σ* of words over a finite alphabet is only countable, this method cannot be applied for introducing computability on uncountable sets M like the set ℝ of real numbers, the set of open subsets of ℝ or the set C[0; 1] of real continuous functions on the interval [0; 1].
Klaus Weihrauch
3. 3. Naming Systems
Abstract
So far we have defined computability on the sets Σ* of finite words and Σω of infinite sequences explicitly by Type-2 machines (Sect. 2.1). In TTE we introduce computability on other sets M by using finite or infinite words as “names”. Machines, therefore, still transform “concrete” sequences of symbols. Only the user of the machine interprets theses sequences as finite or infinite names of “abstract objects”. Although there are several other suggestions to define computability on sets or structures, in this book we will confine ourselves exclusively to computability concepts induced by naming systems. As we have seen, some concepts from computability theory have formally similar topological counterparts. In the following we will continue to develop computability theory, considering also the weaker topological aspects whenever advisable.
Klaus Weihrauch
4. 4. Computability on the Real Numbers
Abstract
Real numbers are the basic objects in analysis. For most non-mathematicians a real number is an infinite decimal fraction, for example π = 3●14159 .... Mathematicians prefer to define the real numbers axiomatically as follows: (ℝ, +,·,0,1, <) is, up to isomorphism, the only Archimedean ordered field satisfying the axiom of continuity [Die60]. The set of real numbers can also be constructed in various ways, for example by means of Dedekind cuts or by completion of the (metric space of) rational numbers. We will neglect all foundational problems and assume that the real numbers form a well-defined set ℝ with all the properties which are proved in analysis. We will denote the real line topology, that is, the set of all open subsets of ℝ, by τ.
Klaus Weihrauch
5. 5. Computability on Closed, Open and Compact Sets
Abstract
Since the set 2 of all subsets of ℝ has a cardinality greater than that of Σω, it has no representation. Therefore, the framework of TTE cannot be applied to define computable functions on all subsets of ℝ like sup :⊆ 2 → ℝ, which determines the least upper bound for each set X ⊆ ℝ with upper bound. In this section we select three subclasses of subsets of ℝn which have continuum cardinality, the open, the closed and the compact sets. As llsual for a subset X of ℝ, we denote the closure of X by X̄ and the open kernel or interior of X by Xo. We will use the notation In of the set Cb(n) of open rational cubes (balls) in ℝn from Definition 4.1.2. By Īn(ω) we denote the closure of the open cube In(ω).
Klaus Weihrauch
6. 6. Spaces of Continuous Functions
Abstract
This chapter is devoted to representations of continuous functions and to applications of the concepts introduced so far. In Sect. 6.1 we define and discuss several representations of spaces of continuous real functions, in particular, representations via names of realizing programs, the “compact-open” representations and the representations by uniform approximation with rational polygons. In Sect. 6.2 we prove computability of any standard operations on functions, closed, open and compact sets. In particular, we prove a computable version of Urysohn’s lemma for closed subsets of ℝn. Computability of zero-finding for real functions under various restrictions is discussed in Sect. 6.3. Sect. 6.4 is devoted to computability problems of differentiation and integration, and Sect. 6.5 contains some further results on analytic functions.
Klaus Weihrauch
7. 7. Computational Complexity
Abstract
Conventional complexity theory refines computability theory. Total recursive word functions f : Σ*Σ* or recursive subsets XΣ* are classified with respect to the resource which machines need to compute or decide them, respectively. By means of notations complexity can be transferred to other sets. Complexity theory has grown to an extensive field with numerous important results.
Klaus Weihrauch
8. 8. Some Extensions
Abstract
In this book, we study computability concepts which are induced by notations and representations. Although every representation δ :⊆ ΣωM of a set induces a computability concept, only very few of them are useful. As an important class we have studied representations constructed from computable topological spaces (Sect. 3.2). Remember that every To-space with countable base can be extended to a computable topological space by an injective notation of a subbase. Many important To-spaces with countable base can be generated from separable metric spaces (Definition 2.2.1). Therefore, it is useful to study computability on metric spaces separately. The reader who is not familiar with the mathematical concepts used in this section is referred to any standard textbook on real analysis, for example, Rudin [Rud64].
Klaus Weihrauch
9. 9. Other Approaches to Computable Analysis
Abstract
In the preceeding chapters we have developed Type-2 Theory of effectivity, TTE, which provides tools for studying various aspects of computability in analysis and, ill particular, offers a “natural” definition of computable real functions. In contrast to the computable number functions where numerous definitions coincide (Church’s Thesis) and alternatives are no longer considered seriously [Rog67, Odi89] several partly non-equivalent approaches to computable analysis have been proposed and are still being investigated. In this chapter we outline the concepts of some of these approaches and compare them with TTE. For avoiding additional technical framework we will express the original definitions in the terms used in this book whenever advisable.
Klaus Weihrauch
Backmatter
Metadaten
Titel
Computable Analysis
verfasst von
Prof. Dr. Klaus Weihrauch
Copyright-Jahr
2000
Verlag
Springer Berlin Heidelberg
Electronic ISBN
978-3-642-56999-9
Print ISBN
978-3-540-66817-6
DOI
https://doi.org/10.1007/978-3-642-56999-9