Computable Real-Valued Functions on Recursive Open and Closed Subsets of Euclidean Space

In this paper we study intrinsic notions of “computability” for open and closed subsets of Euclidean space. Here we combine together the two concepts, computability on abstract metric spaces and computability for continuous functions, and delineate the basic properties of computable open and closed sets. The paper concludes with a comprehensive examination of the Effective Riemann Mapping Theorem and related questions.     

Effective Borel measurability and reducibility of functions

The investigation of computational properties of discontinuous functions is an important concern in computable analysis. One method to deal with this subject is to consider effective variants of Borel measurable functions. We introduce such a notion of Borel computability for single‐valued as well as for multi‐valued functions by a direct effectivization of the classical definition. On Baire space the finite levels of the resulting hierarchy of functions can be characterized using a notion of reducibility for functions and corresponding complete functions. We use this classification and an effective version of a Selection Theorem of Bhattacharya‐Srivastava in order to prove a generalization of the Representation Theorem of Kreitz‐Weihrauch for Borel measurable functions on computable metric spaces: such functions are Borel measurable on a certain finite level, if and only if they admit a realizer on Baire space of the same quality. This Representation Theorem enables us to introduce a realizer reducibility for functions on metric spaces and we can extend the completeness result to this reducibility. Besides being very useful by itself, this reducibility leads to a new and effective proof of the Banach‐Hausdorff‐Lebesgue Theorem which connects Borel measurable functions with the Baire functions. Hence, for certain metric spaces the class of Borel computable functions on a certain level is exactly the class of functions which can be expressed as a limit of a pointwise convergent and computable sequence of functions of the next lower level. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

On Nondeterminism,Enumeration Reducibility and Polynomial Bounds

Enumeration reducibility is a notion of relative computability between sets of natural numbers where only positive information about the sets is used or produced. Extending e-reducibility to partial functions characterises relative computability between partial functions. We define a polynomial time enumeration reducibility that retains the character of enumeration reducibility and show that it is equivalent to conjunctive non-deterministic polynomial time reducibility. We define the polynomial time e-degrees as the equivalence classes under this reducibility and investigate their structure on the recursive sets, showing in particular that the pe-degrees of the computable sets are dense and do not form a lattice, but that minimal pairs exist. We define a jump operator and use it to produce a characterisation of the polynomial hierarchy.     

Computability of Self-Similar Sets

We investigate computability of a self-similar set on a Euclidean space. A nonempty compact subset of a Euclidean space is called a self-similar set if it equals to the union of the images of itself by some set of contractions. The main result in this paper is that if all of the contractions are computable, then the self-similar set is a recursive compact set. A further result on the case that the self-similar set forms a curve is also discussed.     

Negative Dense Linear Orders

Considering dense linear orders, we establish their negative representability over every infinite negative equivalence, as well as uniformly computable separability by computable gaps and the productivity of the set of computable sections of their negative representations. We construct an infinite decreasing chain of negative representability degrees of linear orders and prove the computability of locally computable enumerations of the field of rational numbers.     

Effectiveness in RPL, with applications to continuous logic

In this paper, we introduce a foundation for computable model theory of rational Pavelka logic (an extension of ?ukasiewicz logic) and continuous logic, and prove effective versions of some related theorems in model theory. We show how to reduce continuous logic to rational Pavelka logic. We also define notions of computability and decidability of a model for logics with computable, but uncountable, set of truth values; we show that provability degree of a formula with respect to a linear theory is computable, and use this to carry out an effective Henkin construction. Therefore, for any effectively given consistent linear theory in continuous logic, we effectively produce its decidable model. This is the best possible, since we show that the computable model theory of continuous logic is an extension of computable model theory of classical logic. We conclude with noting that the unique separable model of a separably categorical and computably axiomatizable theory (such as that of a probability space or an L^p Banach lattice) is decidable.     

Approximate decidability in euclidean spaces

We study concepts of decidability (recursivity) for subsets of Euclidean spaces ?^k within the framework of approximate computability (type two theory of effectivity). A new notion of approximate decidability is proposed and discussed in some detail. It is an effective variant of F. Hausdorff's concept of resolvable sets, and it modifies and generalizes notions of recursivity known from computable analysis, formerly used for open or closed sets only, to more general types of sets. Approximate decidability of sets can equivalently be expressed by computability of the characteristic functions by means of appropriately working oracle Turing machines. The notion fulfills some natural requirements and is hereditary under canonical embeddings of sets into spaces of higher dimensions. However, it is not closed under binary union or intersection of sets. We also show how the framework of resolvability and approximate decidability can be applied to investigate concepts of reducibility for subsets of Euclidean spaces.     

Effective Structures

The connection between some special properties of the computable functions in an abstract structure and the existence of a recursive and semi-recursive representation of the structure is studied. The considerations are based on the notion of computability on many-sorted abstract structures.     

Computability of measurable sets via effective topologies

We investigate in the frame of TTE the computability of functions of the measurable sets from an infinite computable measure space such as the measure and the four kinds of set operations. We first present a series of undecidability and incomputability results about measurable sets. Then we construct several examples of computable topological spaces from the abstract infinite computable measure space, and analyze the computability of the considered functions via respectively each of the standard representations of the computable topological spaces constructed. The authors are supported by grants of NSFC and DFG.     

Uniformity in Computable Structure Theory

We investigate the effects of adding uniformity requirements to concepts in computable structure theory such as computable categoricity (of a structure) and intrinsic computability (of a relation on a computable structure). We consider and compare two different notions of uniformity, previously studied by Kudinov and by Ventsov. We discuss some of their results and establish new ones, while also exploring the connections with the relative computable structure theory of Ash, Knight, Manasse, and Slaman and Chisholm and with previous work of Ash, Knight, and Slaman on uniformity in a general computable structure-theoretical setting.     

On some results of analysis for fuzzy metric spaces

A necessary and sufficient condition for a fuzzy metric space to be complete is given. We prove that a subspace of a separable fuzzy metric space is separable and every separable fuzzy metric space is second countable. Uniform limit theorem is generalized to fuzzy metric spaces.     

A Real Number Structure that is Effectively Categorical

On countable structures computability is usually introduced via numberings. For uncountable structures whose cardinality does not exceed the cardinality of the continuum the same can be done via representations. Which representations are appropriate for doing real number computations? We show that with respect to computable equivalence there is one and only one equivalence class of representations of the real numbers which make the basic operations and the infinitary normed limit operator computable. This characterizes the real numbers in terms of the theory of effective algebras or computable structures, and is reflected by observations made in real number computer arithmetic. Demanding computability of the normed limit operator turns out to be essential: the basic operations without the normed limit operator can be made computable by more than one class of representations. We also give further evidence for the well-known non-appropriateness of the representation to some base b by proving that strictly less functions are computable with respect to these representations than with respect to a standard representation of the real numbers. Furthermore we consider basic constructions of representations and the countable substructure consisting of the computable elements of a represented, possibly uncountable structure. For countable structures we compare effectivity with respect to a numbering and effectivity with respect to a representation. Special attention is paid to the countable structure of the computable real numbers.     

Computable Families of Superatomic Boolean Algebras

We describe the families of superatomic Boolean algebras which have a computable numbering. We define the notion of majorizability and establish a criterion that is formulated only on using algorithmic terms and majorizability. We give some examples showing that the condition of majorizability is essential. We also prove some criterion for the existence of a computable numbering for a family of -atomic algebras ( is a computable ordinal).     

Borel complexity and computability of the Hahn–Banach Theorem

The classical Hahn–Banach Theorem states that any linear bounded functional defined on a linear subspace of a normed space admits a norm-preserving linear bounded extension to the whole space. The constructive and computational content of this theorem has been studied by Bishop, Bridges, Metakides, Nerode, Shore, Kalantari Downey, Ishihara and others and it is known that the theorem does not admit a general computable version. We prove a new computable version of this theorem without unrolling the classical proof of the theorem itself. More precisely, we study computability properties of the uniform extension operator which maps each functional and subspace to the set of corresponding extensions. It turns out that this operator is upper semi-computable in a well-defined sense. By applying a computable version of the Banach–Alaoglu Theorem we can show that computing a Hahn–Banach extension cannot be harder than finding a zero in a compact metric space. This allows us to conclude that the Hahn–Banach extension operator is -computable while it is easy to see that it is not lower semi-computable in general. Moreover, we can derive computable versions of the Hahn–Banach Theorem for those functionals and subspaces which admit unique extensions. This work has been partially supported by the National Research Foundation (NRF) Grant FA2005033000027 on “Computable Analysis and Quantum Computing”. An extended abstract version has been published in the conference proceedings [7].     

Multiplication Operators on the Lipschitz Space of a Tree

In this paper, we study the multiplication operators on the space of complex-valued functions f on the set of vertices of a rooted infinite tree T which are Lipschitz when regarded as maps between metric spaces. The metric structure on T is induced by the distance function that counts the number of edges of the unique path connecting pairs of vertices, while the metric on ℂ is Euclidean. After observing that the space L{\mathcal{L}} of such functions can be endowed with a Banach space structure, we characterize the multiplication operators on L{\mathcal{L}} that are bounded, bounded below, and compact. In addition, we establish estimates on the operator norm and on the essential norm, and determine the spectrum. We then prove that the only isometric multiplication operators on L{\mathcal{L}} are the operators whose symbol is a constant of modulus one. We also study the multiplication operators on a separable subspace of L{\mathcal{L}} we call the little Lipschitz space.     

On local non‐compactness in recursive mathematics

A metric space is said to be locally non‐compact if every neighborhood contains a sequence that is eventually bounded away from every element of the space, hence contains no accumulation point. We show within recursive mathematics that a nonvoid complete metric space is locally non‐compact iff it is without isolated points. The result has an interesting consequence in computable analysis: If a complete metric space has a computable witness that it is without isolated points, then every neighborhood contains a computable sequence that is eventually computably bounded away from every computable element of the space. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

Hyperarithmetical Boolean Algebras with a Distinguished Ideal

We prove a general theorem that allows us to pass from a hyperarithmetical Boolean algebra with a distinguished ideal to some computable Boolean algebra connected with the former by natural algebraic operations. Some examples are given.     

Geometric Gibbs theory

We extend the classical Gibbs theory for smooth potentials to the geometric Gibbs theory for certain continuous potentials. We study the existence and uniqueness and the compatibility of geometric Gibbs measures associated with these continuous potentials. We introduce a complex Banach manifold structure on the space of these continuous potentials as well as on the space of all geometric Gibbs measures. We prove that with this complex Banach manifold structure, the space is complete and, moreover, is the completion of the space of all smooth potentials as well as the space of all classical Gibbs measures. There is a maximum metric on the space, which is incomplete. We prove that the topology induced by the newly introduced complex Banach manifold structure and the topology induced by the maximal metric are the same. We prove that a geometric Gibbs measure is an equilibrium state, and the infimum of the metric entropy function on the space is zero.

     

Embedding metric spaces in Euclidean space

In this paper, we give necessary and sufficient conditions for embedding a given metric space in Euclidean space. We shall introduce the notions of flatness and dimension for metric spaces and prove that a metric space can be embedded in Euclidean n-space if and only if the metric space is flat and of dimension less than or equal to n.     

Geometric Gibbs theory In Memory of Professor Shantao Liao

We extend the classical Gibbs theory for smooth potentials to the geometric Gibbs theory for certain continuous potentials. We study the existence and uniqueness and the compatibility of geometric Gibbs measures associated with these continuous potentials. We introduce a complex Banach manifold structure on the space of these continuous potentials as well as on the space of all geometric Gibbs measures. We prove that with this complex Banach manifold structure, the space is complete and, moreover, is the completion of the space of all smooth potentials as well as the space of all classical Gibbs measures. There is a maximum metric on the space,which is incomplete. We prove that the topology induced by the newly introduced complex Banach manifold structure and the topology induced by the maximal metric are the same. We prove that a geometric Gibbs measure is an equilibrium state, and the infimum of the metric entropy function on the space is zero.