Fourth Workshop on
Computability and Complexity in Analysis

September 17-19, 2000, Swansea, Wales


The aim of the workshop has been to bring together people interested in computability and complexity aspects of analysis and to explore connections with numerical methods, physics and, of course, computer science. Submissions on any aspect of these subjects are welcome.

Program Committee

Ker-I Ko (Stony Brook, USA)
Marian Pour-El (Minnesota , USA)
Dana Scott (Carnegie-Mellon, USA)
Viggo Stoltenberg-Hansen (Uppsala, Sweden)
John V. Tucker (Swansea, Wales)
Klaus Weihrauch, chair (Hagen, Germany)
Mariko Yasugi (Kyoto Sangyo, Japan)
Ning Zhong (Cincinnati, USA)
Jeff Zucker (McMaster, Canada)

Organizing Committee

Jens Blanck (Swansea, Wales)
Vasco Brattka (Hagen, Germany)
Peter Hertling (Hagen, Germany)

Competition & Forum

As part of the workshop a friendly competition between systems for exact real computation, organized by

David Lester (Manchester, England)

has taken place. The systems have been run on a set of problems and evaluated. The systems should compute an approximation to the exact result to any predetermined accuracy. For further information, including a list of proposed problems, see
Competitors should give an overview of their systems. We wish to inaugurate an ongoing open forum for real number programming. Submissions on implementation issues are encouraged for the workshop.


September 17
14:00 Opening
14:10 Ning Zhong
Turing Computability of the Schrödinger Propagator
14:35 Abbas Edalat and André Lieutier
Domain of Differentiable Functions
15:00 Break
15:30 Keye Martin
Complexity and Verification of a Renee Equation
15:55 Matthias Schröder
Admissible Representations of Limit Spaces
16:20 Break
16:50 Yoshiki Tsujii, Mariko Yasugi and Takakazu Mori
Some Properties of the Effectively Uniform Topological Space
17:15 Armin Hemmerling
Standard Representations of Effective Metric Spaces
17:40 Break
18:30 Dinner
September 18
8:35 Ulrich Kohlenbach
On the Computational Content of the Krasnoselski and Ishikawa Fixed Point Theorems
9:00 Dmitry Buy
Some Remarks about Fixpoint Theorems
9:25 Izumi Takeuti
Effective Fixed Point Theorem Over a Non-Separable Space
9:50 Break
10:20 Martin Ziegler and Vasco Brattka
A Computable Spectral Theorem
10:45 Tobias Gärtner and Günter Hotz
Recursive Analytic Functions of a Complex Variable
11:10 Break
11:40 Abbas Edalat, Elham Kashefi and André Lieutier
The Convex Hull is Computable!
12:05 Marko Krznaric
Computing a Required Abolute Precision from an Exact Floating Point Number
12:30 Lunch break
14:30 Namhyun Hur and James H. Davenport
A Generic Root Operation for Exact Real Arithmetic
14:55 Tom Kelsey
Exact Numerical Computation via Symbolic Computation
15:20 Break
15:50 Norbert Th. Müller
The iRRAM: Exact Arithmetic in C++
16:15 Paul Gowland and David Lester
A Survey on Exact Computer Arithmetic
16:40 Break
17:10 Competition
18:10 Break
19:00 Dinner
September 19
8:35 Jens Blanck
Effectivity of Regular Spaces
9:00 Hiroyasu Kamo
Effective Contraction Theorem and its Application
9:25 Charles Meyssonnier, Paolo Boldi and Sebastiano Vigna
delta-approximable Functions
9:50 Break
10:20 Daniel Richardson
The Uniformity Conjecture
10:45 Klaus Weihrauch
On Computable Metric Spaces Tietze-Urysohn Extension is Computable
11:10 Break
11:40 Takakazu Mori
Computabilities of Functions on Effectively Separable Metric Spaces
12:05 Forum
12:30 Lunch break
14:30 Peter Hertling
Banach-Mazur Computable Functions on Metric Spaces
14:55 George Kapoulas
Polynomially Time Computable Functions over p-adic Fields
15:20 Break
15:50 Hideki Tsuiki
Computational Dimension of Topological Spaces Based on Embeddings to n-bottom-Sequence Spaces
16:15 Margarita V. Korovina and Oleg V. Kudinov
A Formalisation of Computability of Operators and Real-Valued Functionals via Domain Theory
16:40 Break
17:10 Ashley Burrows and David Lester
Exact Arithmetic and the Korteweg-de Vries Equation
17:35 Vasco Brattka
A Computable Kolmogorov Superposition Theorem
18:00 End of CCA2000

Some participants of CCA2000 (picture by Elham Kashefi)


Jens Blanck, Vasco Brattka, and Peter Hertling (Eds.)

Computability and Complexity in Analysis

4th International Workshop, CCA 2000, Swansea, UK, September 17-19, 2000, Selected Papers

Springer-Verlag Berlin Heidelberg New York, 2001
ISBN 3-540-42197-1, 395 pp.

Online version


The venue of the workshop is Department of Computer Science, University of Wales Swansea.

How to get there

If you arrive at Heathrow the fastest way is to take the raillink bus to Reading and change to train. Tickets can be bought for the whole trip at the train ticket desks in the terminals. The trains are operated by Great Western. There are also buses operated by National Express leaving from the central bus station. Once in Swansea you should take a taxi to the university.

If you arrive by car on the M4 you should leave at Junction 42 for Swansea and Gower. Continue to head for Gower until the signs for the university appears on the right hand side.

Here you can find a map of Swansea.

Finding your way on campus

The conference will take place in building 8.1. The accommodation is in building 20. The lunches and the dinner on Sunday will be served in building 17.

Here is a map of the campus.


Accomodation is available on campus for 32 pounds per night including breakfast. Bookings need to be made as soon as possible:
CCA 2000
Mrs Jill Edwards
Department of Computer Science
University of Wales Swansea
Singleton Park
Swansea SA2 8PP
Phone +44 1792 295393
[Email removed]

The on campus accommodation is in building 20. There should be porters there to give you keys to your room.

Finding something to eat

There is a pub situated just outside the campus to the southwest. Plenty of restaurants can of course be found in the city of Swansea, which is about 3 km away. The Dylan Thomas Centre, between the museum and Sainsbury's on the city map, serves excellent meals at reasonable prices. The former fishing village of Mumbles is situated 4 km south of campus and has a number of restaurants.


A conference fee of 60 pounds including 2 evening meals and two lunches will apply.

Start |  Introduction |  Members |  Events |  Links
© 1997-2000 Vasco Brattka, FernUniversität Hagen