Dagstuhl Seminar on
Computability and Complexity in Analysis 2001
The Seminar 01461 on Computability and Complexity in Analysis
at Schloß Dagstuhl is organized
by
Vasco Brattka (Hagen),
Peter Hertling (Hagen),
Mariko Yasugi (Kyoto),
Ning Zhong (Cincinnati).
It takes place at
Schloß Dagstuhl,
Wadern, Germany, November 1116, 2001.
Motivation
This Dagstuhl seminar is concerned with the theory of
computability and complexity over the real numbers which
is built on the Turing machine model.
This theory was initiated by Turing, Grzegorczyk, Lacombe,
Banach and Mazur, and has seen a rapid growth in recent years.
Recent monographs are by PourEl/Richards, Ko, and Weihrauch.
Computability theory and complexity theory are two
central areas of research in theoretical computer science.
Until recently, most work in these areas concentrated
on problems over discrete structures. In the last
years, though, there has been an enormous growth
of computability theory and complexity theory over the
real numbers and other continuous structures.
One of the reasons for this phenomenon is that more
and more practical computation problems over the real
numbers are being dealt with by computer scientists,
for example, in computational geometry, in the modelling
of dynamical and hybrid systems, but also in classical
problems from numerical mathematics.
The scientists working on these questions come from
different fields, such as theoretical computer science,
domain theory, logic, constructive mathematics,
computer arithmetic, numerical mathematics, analysis etc.
The Dagstuhl seminar provides a unique opportunity for
people from such diverse areas to meet and exchange
ideas and knowledge.
One of the topics of interest is foundational work
concerning the various models and approaches for defining or
describing computability and complexity over the real numbers.
We also hope to gain new insights into the computabilitytheoretic
side of various computational questions from physics
as well as from other fields involving computations over the
real numbers. This, of course, also requires the extension of
existing computability notions to more general classes of objects.
Other topics of interest are complexitytheoretic investigations,
both foundational and with respect to concrete problems.
Last but not least, new implementations of exact real arithmetic
and further developments of already existing software packages
will be of interest.
Participants
 Götz Alefeld,
Universität Karlsruhe, Germany,
On the Theorems of Kantorovich, Moore, and Miranda
 Klaus AmbosSpies,
Universität Heidelberg, Germany
 Goerge Barmpalias,
University of Leeds, UK
 Andrej Bauer,
IMFM Ljubiljana, Slovenia,
On the Relationship between Domain Theory and Type Two Effectivity
 Markus Bläser,
Medizinische Universität Lübeck, Germany,
Weierstrass Approximation Theorems for NP and #P Real Functions
 Vasco Brattka, Universität Hagen, Germany,
Computable Versions of the Closed Graph and the Open Mapping Theorem
 Douglas Bridges,
University of Canterbury  Christchurch, New Zealand,
Apartness spaces as a foundation for constructive topology
 Douglas Cenzer,
University of Florida  Gainesville, USA,
Effectively Closed Sets and Graphs of Computable Real Functions
 Rod Downey,
University of Wellington, New Zealand,
Reals and Randomness
 Martin H. Escardo,
University of Birmingham, UK,
A universal characterization of the Euclidean unit interval
 Tobias Gärtner,
Universität Saarbrücken, Germany
 Magne Haveraaen,
University of Bergen, Norway,
Computational Scalar Fields  A Basis for Partial Differential Equations
 Armin Hemmerling,
Universität Greifswald, Germany,
Approximate Decidability
 Peter Hertling,
Universität Hagen, Germany,
Random sets versus random sequences
 Denis Hirschfeldt,
University of Chicago, USA,
Relative 1Randomess of Reals
 Elham Kashefi,
Imperial College  London, UK,
Quantum Oracle Complexity
 Ulrich Kohlenbach,
BRICS  Aarhus, Denmark,
Proof mining in numerical analysis: effective strong unicity
in L_{1}approximation
 Michal Konecny,
University of Edinburgh, UK,
Continuity of NonExtensional Computation
 Margarita Korovina,
Sobolev Institute of Mathematics  Novosibirsk, Russia,
Higher Order Computability over the Real Numbers
 Marko Krznaric,
Imperial College  London, UK,
Domain Theory and Differential Calculus
 Oleg V. Kudinov,
Sobolev Institute of Mathematics  Novosibirsk, Russia,
PTime Computable Reals and some Complexity Classes
 David Lester,
Manchester University, UK,
Infinite Precision Basic Linear Algebra Systems
or Why Norbert Müller is Right
 Peter Lietz,
TU Darmstadt, Germany,
TTE via Kleene's Function Realizability
 Klaus Meer,
Univ. of Southern Denmark  Odense, Denmark,
A step towards a complexity theory for dynamical systems
 Joseph S. Miller,
Cornell University, USA,
The Sets Fixable by Computable Maps on the nBall
 Takakazu Mori,
KyotoSangyo University, Japan,
Fine Computable Functions and Their Walsh Fourier Coefficients
 Norbert Müller,
Universität Trier, Germany,
Real Numbers and BDDs
 Dag Normann,
University of Oslo, Norway
 Paulo Oliva,
BRICS  Aarhus, Denmark,
On the Computational Complexity of L_{1}Approximation
 Robert Rettinger,
Universität Hagen, Germany
 Matthias Schröder,
Universität Hagen, Germany,
Effectivity in Admissibly Representable Spaces
 Peter M. Schuster,
Universität München, Germany,
Compactness in constructive analysis
 Victor Selivanov,
Pedagogical University  Novosibirsk, Russia
 Olha Shkaravska,
Materialise Ukraine  Kiew, Ukraine
 Alex Simpson,
University of Edinburgh, UK,
Comparing Functional Paradigms for Exact Real Arithmetic
 Dimiter Skordev,
University of Sofia, Bulgaria,
Well Computable Real Numbers
 Bas Spitters,
University of Nijmegen, Netherlands
Unbounded Operators on Hilbert Spaces in Constructive Mathematics
 Ludwig Staiger,
Universität HalleWittenberg, Germany,
Properties of real interpretations of omegawords
 Izumi Takeuti,
Kyoto University, Japan,
Representations of Functionals
 Hideki Tsuiki,
Kyoto University, Japan,
A domaintheoretic account of computability via bottomed sequences
 Klaus Weihrauch, Universität Hagen, Germany,
Computational Complexity on Computable Metric Spaces
 Mariko Yasugi,
KyotoSangyo University, Japan,
Metrization of the uniform space and effective convergence
 Atsushi Yoshikawa,
Kyushu University, Japan,
Computability and Entropy Solutions of Conservation Laws
 Xizhong Zheng,
BTU Cottbus, Germany,
Beyond Computable Real Numbers
 Ning Zhong,
University of Cincinnati, USA,
Computable Analysis of Partial Differential Equations
 Martin Ziegler,
Universität Paderborn, Germany,
Computability on regular subsets of Euclidean space
Proceedings


It is planned to publish a special issue of
Mathematical Logic Quarterly (MLQ),
dedicated to the CCA Dagstuhl Seminar. This issue will
include a limited number of fulllength papers
which must meet scope and standards of MLQ. There will
be no page limit for individual papers, but there is a
total limit of 160 pages for the whole issue. Thus,
extraordinarily long papers might not be included.
Submission deadline: December 31, 2001
Notification: March 15, 2002
Final papers: April 15, 2002
Electronical submissions (PostScript files) are welcome.
For the final version LaTeX files are required.
For the preparation of your submission please use the
following LaTeX header or
LaTeX2e header.
Or you can already use the MLQ Style Files
which have to be used for the final versions of papers.
The special issue is scheduled to appear as
Volume 48 (2002) Supplement 1.

Abstracts
During the seminar participants will be asked to use the following
example
to create an electronical
version of an abstract of their talk and send send it to Michal Konecny.
This abstract will be included in the Dagstuhl Seminar Report.
 

A participant's viewpoint
Picture based on slides of Andrej Bauer.
