Comparing integrability and measurability in different models of computation

Christine Gassner (1) , Arno Pauly (2) , Florian Steinberg (3)

1 Universität Greifswald - University of Greifswald
2 Swansea University
3 TOCCATA - Formally Verified Programs, Certified Tools and Numerical Computations

Computable analysis uses representations to encode elements of abstract mathematical structures by objects that can be operated on by digital computers [7, 6]. For many spaces that are of importance in applications, canonical representations are available. These representations are usually justified by minimality results. Often, spaces can be viewed from several perspectives and thus different representations are eligible. For instance, the space of continuous functions on the unit interval can either be viewed as a function space and equipped with the minimal representation such that evaluation is computable, or as a metric space with respect to the supremum norm and equipped with an appropriate Cauchy representation. In this example, the computability structures coincide, which can be interpreted as a stability result for the com-putability structure on the continuous functions. In other cases, where the spaces already differ topologically, it can not be expected that the computability structures coincide and one may ask for the degree of incomputability of the translations [5]. We start by comparing the natural computability structure on the space of continuous functions to the structure it inherits from the space of integrable functions as a subspace. While the inclusion mapping, and with it the translation from a continuous to an integrable function, is computable, recovering a continuous function from its description as integrable function is not computable. We prove that this task is exactly as difficult as computing the limit operator. The difficulty of computational tasks is compared by means of Weihrauch reductions and the limit operator is the operator that assigns to a converging sequence in Baire space its limit. Weihrauch reductions are standard for such comparisons in computable analysis and the limit operator is one of the standard objects to gauge incomputability against [2]. We go on to investigate the class of Borel functions of lowest non-trivial complexity: The ∆ 0 2-measurable functions. These functions can be represented as the space C([0, 1], [0, 1]) of piecewise continuous functions as shown in [4, 3]. We prove that the assignment of a piece-wise continuous function to the corresponding integrable function is again Weihrauch equivalent to the limit operator. As integrable functions are identified when they coincide almost everywhere, this assignment is not an inclusion and the result does not allow a direct interpretation as comparison of two representations of the same space. The techniques employed in proving the above statements can be adapted to address the effective relationship between measurability and integrability and draw connections between computable analysis and more algebraic modes of computation [1]. To illustrate this, we compare semidecidable sets in the BSS-model with the semidecidable subsets of R in computable analysis. Computable analysis makes the open subsets of the reals a represented space O(R) by coding them as countable unions of rational intervals. The semidecidable sets are exactly the sets that are effectively open, i.e. of the form n∈N (a n , b n), where (a n) n∈N and (b n) n∈N are computable sequences of rationals. In the BSS-model, the semidecidable sets are the semialgebraic sets S R ,

Domaines: Logique en informatique [cs.LO]

Christine Gassner, Arno Pauly, Florian Steinberg. Comparing integrability and measurability in different models of computation. CIE 2018 - 14th Conference on Computability in Europe, Jul 2018, Kiel, Germany. ⟨hal-02019195⟩