2. Computability on the Cantor Space
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,
- PDF / 25,245,965 Bytes
- 295 Pages / 439.32 x 666.12 pts Page_size
- 45 Downloads / 163 Views
Advisory Board: G. Ausiello M. Broy S. Even J. Hartmanis N. Jones T. Leighton M. Nivat C. Papadimitriou D. Scott
Springer Berlin Heidelberg New York Barcelona Hong Kong London Milan Paris Singapore Tokyo
Klaus Weihrauch
Computable Analysis An Introduction
With 44 Figures
Springer
Author
Prof. Dr. Klaus Weihrauch FernUniversitat Hagen, Fachbereich Informatik Theoretische Informatik I Postfach 940,58084 Hagen Germany Klaus. [email protected] Series Editors
prof. Dr. Wilfried Brauer Institut fUr Informatik, Technische Universitat MUnchen ArcisstraBe 21, 80333 MUnchen, Germany [email protected] Prof. Dr. Grzegorz Rozenberg Leiden Institute of Advanced Computer Science University of Leiden Niels Bohrweg 1,2333 CA Leiden, The Netherlands [email protected] prof. Dr. Arto Salomaa Turku Centre for Computer Science Lemminkaisenkatu 14A, 20520 Turku, Finland [email protected]
Library of Congress Cataloging-in-Publication Data Weihrauch, K. (Klaus), 1943Computable Analysis. An Introduction / Klaus Weihrauch. p. cm. -- (Texts in theoretical computer science) Includes bibliographical references and index. ISBN 3540668179 (alk. paper) 1. Computable functions. 2. Recursion theory. 3. Mathematical analysis. I. Title. II. Series.
ACM Computing Classification (1998): ELl, E1.m, G.1.m ISBN 3-540-66817-9 Springer-Verlag Berlin Heidelberg New York This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use'must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York, a member of BertelsmannSpringer Science+ Business Media GmbH © Springer-Verlag Berlin Heidelberg 2000
The use of general descriptive names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and therefore free for general use. Cover Design: design & production GmbH, Heidelberg Typesetting: Camera ready by author SPIN: 10694615 45/3142/PS - 5432 1 0
For Susanne
Preface
Computable analysis is a branch of computability theory studying those fum:tions on the real numbers and related sets which can be computed by machines such as digital computers. The increasing demand for reliable software in scientific computation and engineering requires a sound and broad foundation not only of the analytical/numerical but also of the computational aspects of real number computation. Although many researchers have been active in computable analysis, it has never belonged to the main stream of research in computability. Our knowledge of this
