# Special Issue for the "Seventh International Conference on Computability and Complexity in Analysis (CCA 2010)"

2010

Editors: Ning Zhong, Xizhong Zheng, S. Barry Cooper, Klaus Weihrauch

This Special issue of the journal Loical Methods in Computer Science (LMCS) contains a selection of 8 articles in the area of Computability and Complexity in Analysis. Many, but not all of them were presented at the Seventh International Conference on Computability and Complexity in Analysis (CCA 2010) that took place on June 21-25, 2010 in Zhenjiang, China. It was the 16th event in a series of workshops, seminars and conferences in this area. For more information about CCA see cca-net.de.

The conference and this special issue are concerned with Computable Analysis, the theory of computability and complexity over real-valued data. Computability theory studies the limitations and abilities of computers in principle. Computational complexity theory provides a framework for understanding the cost of solving computational problems, as measured by the requirement for resources such as time and space. In particular, Computable Analysis supplies an algorithmic foundation for numerical computation.

We thank all authors for their contributions and the referees for their thorough and diligent work. Finally, we thank the members of the organising committee of the conference at the University of Zhenjiang for their help and the people from LMCS for their support.

Martín Escardó, University of Birmingham, UK,
Klaus Weihrauch, University of Hagen,
Xizhong Zheng, Arcadia University and Jiangsu University,
Ning Zhong, University of Cincinnati,
Guest Editors.

### 1. Banach Spaces as Data Types

,.
We introduce the operators "modified limit" and "accumulation" on a Banach space, and we use this to define what we mean by being internally computable over the space. We prove that any externally computable function from a computable metric space to a computable Banach space is internally computable. We motivate the need for internal concepts of computability by observing that the complexity of the set of finite sets of closed balls with a nonempty intersection is not uniformly hyperarithmetical, and thus that approximating an externally computable function is highly complex.

### 2. Noncomputable functions in the Blum-Shub-Smale model

, ; , ; ,.
Working in the Blum-Shub-Smale model of computation on the real numbers, we answer several questions of Meer and Ziegler. First, we show that, for each natural number d, an oracle for the set of algebraic real numbers of degree at most d is insufficient to allow an oracle BSS-machine to decide membership in the set of algebraic numbers of degree d + 1. We add a number of further results on relative computability of these sets and their unions. Then we show that the halting problem for BSS-computation is not decidable below any countable oracle set, and give a more specific condition, related to the cardinalities of the sets, necessary for relative BSS-computability. Most of our results involve the technique of using as input a tuple of real numbers which is algebraically independent over both the parameters and the oracle of the machine.

### 3. Turing machines on represented sets, a model of computation for Analysis

, ; ,.
We introduce a new type of generalized Turing machines (GTMs), which are intended as a tool for the mathematician who studies computability in Analysis. In a single tape cell a GTM can store a symbol, a real number, a continuous real function or a probability measure, for example. The model is based on TTE, the representation approach for computable analysis. As a main result we prove that the functions that are computable via given representations are closed under GTM programming. This generalizes the well known fact that these functions are closed under composition. The theorem allows to speak about objects themselves instead of names in algorithms and proofs. By using GTMs for specifying algorithms, many proofs become more rigorous and also simpler and more transparent since the GTM model is very simple and allows to apply well-known techniques from Turing machine theory. We also show how finite or infinite sequences as names can be replaced by sets (generalized representations) on which computability is already defined via representations. This allows further simplification of proofs. All of this is done for multi-functions, which are essential in Computable Analysis, and multi-representations, which often allow more elegant formulations. As a byproduct we show that the computable functions on finite and infinite sequences of symbols are closed under programming with GTMs. We conclude with examples of application.

### 4. Co-c.e. spheres and cells in computable metric spaces

,.
We investigate conditions under which a co-computably enumerable set in a computable metric space is computable. Using higher-dimensional chains and spherical chains we prove that in each computable metric space which is locally computable each co-computably enumerable sphere is computable and each co-c.e. cell with co-c.e. boundary sphere is computable.

### 5. Real Analytic Machines and Degrees

, ; ,.
We study and compare in two degree-theoretic ways (iterated Halting oracles analogous to Kleene's arithmetical hierarchy and the Borel hierarchy of descriptive set theory) the capabilities and limitations of three models of analytic computation: BSS machines (aka real-RAM) and strongly/weakly analytic machines as introduced by Hotz et. al. (1995).

### 6. Algorithmic Randomness and Capacity of Closed Sets

, ; , ; , ; ,.
We investigate the connection between measure, capacity and algorithmic randomness for the space of closed sets. For any computable measure m, a computable capacity T may be defined by letting T(Q) be the measure of the family of closed sets K which have nonempty intersection with Q. We prove an effective version of Choquet's capacity theorem by showing that every computable capacity may be obtained from a computable measure in this way. We establish conditions on the measure m that characterize when the capacity of an m-random closed set equals zero. This includes new results in classical probability theory as well as results for algorithmic randomness. For certain computable measures, we construct effectively closed sets with positive capacity and with Lebesgue measure zero. We show that for computable measures, a real q is upper semi-computable if and only if there is an effectively closed set with capacity q.

, ; ,.