Project Details
Projekt
Computable Analysis and Degrees of Randomness (CADoR)
Subject Area
Theoretical Computer Science
Term
since 2025
Project identifier
Deutsche Forschungsgemeinschaft (DFG) - Project number 556436876
The project "Computable Analysis and Degrees of Randomness (CADoR)" is situated at the intersection of computable analysis and algorithmic randomness. In computable analysis, the effective approximability of real numbers is investigated. The two most important notions of approximability are that of a computably approximable number, which refers to a real number that is the limit of a computable sequence of rational numbers, and that of a left-c.e. number, where it is required in addition that the approximating sequence is nondecreasing. Both approximation concepts can be further refined by additional conditions. In algorithmic randomness, randomness notions for infinite binary sequences (henceforth just called sequences) are studied. The two most important approaches for doing so are to consider a sequence random if it is incompressible or if it is unpredictable. Formally, unpredictability means that when successively betting on the bits of the sequence with fair pay-off, the achievable capital is bounded. Which compression methods and betting strategies are considered admissible must be suitably restricted to specific effective procedures. Depending on the strength of the admissible procedures, randomness notions of varying strength are obtained. In addition to such absolute randomness notions, also relative randomness notions such as Solovay reducibility are investigated. This allows for the comparison of the degree of randomness of two sequences. There are close connections between algorithmic randomness and computable analysis, which have been studied since the 1970s. Here real numbers are identified with sequences via their binary representation. Of particular interest to the CADoR project are connections between the degree of randomness of a real number and the quality and, in particular, the convergence speed of ist effective approximations. Two other focal points are investigations into the approximation concepts as well as into the absolute and relative notions of randomness themselves. All three focal points have in common that the respective questions have so far been mainly studied in the context of left-c.e. numbers, and a number of central results have been achieved for this case. The CADoR project aims to explore whether and in what form such results can be extended to more comprehensive classes such as computably approximable numbers or all real numbers. Initially, it must be clarified how concepts such as the speedability of a real number or Solovay reducibility should be extended; in the left-c.e. case, these concepts are defined in a straightforward natural way, whereas for the extension to larger sets of real numbers, several non-equivalent variants suggest themselves.
DFG Programme
Research Grants
