Computability and Complexity in Analysis: 4th International Workshop, CCA 2000 Swansea, UK, September 17–19, 2000 Selected Papers

Jens Blanck (auth.), Jens Blanck, Vasco Brattka, Peter Hertling (eds.)3540421971, 9783540421979

The workshop on Computability and Complexity in Analysis, CCA 2000, was hosted by the Department of Computer Science of the University of Wales Swansea, September 17{19, 2000. It was the fourth workshop in a successful series of workshops: CCA’95 in Hagen, Germany, CCA’96 in Trier, Germany, and CCA’98 in Brno, Czech Republic. About 40 participants from the countries United Kingdom, Germany, Japan, Italy, Russia, France, Denmark, Greece, and Ireland contributed to the success of this meeting. Altogether, 28 talkswere p- sented in Swansea. These proceedings include 23 papers which represent a cro- section through recent research on computability and complexity in analysis. The workshop succeeded in bringing together people interested in computability and complexity aspects of analysis and in exploring connections with nume- cal methods, physics and, of course, computer science. It was rounded o by a number of talks and papers on exact computer arithmetic and by a competition of v e implemented systems. A report on this competition has been included in these proceedings. We would like to thank the authors for their contributions and the referees for their careful work, and we hope for further inspiring and constructive meetings of the same kind. April 2001 Jens Blanck Vasco Brattka Peter Hertling Organization CCA2000was hosted by the Department of Computer Science of the University of Wales Swansea and took place on September 17{19, 2000.

---

Table of contents :
Effectivity of Regular Spaces….Pages 1-15
The Degree of Unsolvability of a Real Number….Pages 16-29
A Survey of Exact Arithmetic Implementations….Pages 30-47
Standard Representations of Effective Metric Spaces….Pages 48-68
Banach-Mazur Computable Functions on Metric Spaces….Pages 69-81
A Generic Root Operation for Exact Real Arithmetic….Pages 82-87
Effective Contraction Theorem and Its Application….Pages 88-100
Polynomially Time Computable Functions over p -Adic Fields….Pages 101-118
On the Computational Content of the Krasnoselski and Ishikawa Fixed Point Theorems….Pages 119-145
Formalisation of Computability of Operators and Real-Valued Functionals via Domain Theory….Pages 146-168
Computing a Required Absolute Precision from a Stream of Linear Fractional Transformations….Pages 169-186
δ-Approximable Functions….Pages 187-199
Computabilities of Fine-Continuous Functions….Pages 200-221
The iRRAM: Exact Arithmetic in C++….Pages 222-252
The Uniformity Conjecture….Pages 253-272
Admissible Representations of Limit Spaces….Pages 273-295
Characterization of the Computable Real Numbers by Means of Primitive Recursive Functions….Pages 296-309
Effective Fixed Point Theorem over a Non-Computably Separable Metric Space….Pages 310-322
Computational Dimension of Topological Spaces….Pages 323-335
Some Properties of the Effective Uniform Topological Space….Pages 336-356
On Computable Metric Spaces Tietze-Urysohn Extension Is Computable….Pages 357-368
Is the Linear Schrödinger Propagator Turing Computable?….Pages 369-377
A Computable Spectral Theorem….Pages 378-388
Exact Real Arithmetic Systems: Results of Competition….Pages 389-393