Abstract A Polish space is not always homeomorphic to a computably presented Polish space. In this article, we examine degrees of non-computability of presenting homeomorphic copies of compact Polish spaces. We show that there exists a bold 0 prime $\mathbf {0}'$ 0 ' -computable low Subscript 3 $_3$ 3 compact Polish space which is not homeomorphic to a computable one, and that, for any natural number n greater than or equals 2 $n\geq 2$ n ≥ 2 , there exists a Polish space upper X Subscript n $X_n$ X n such that exactly the high Subscript n $_{n}$ n -degrees are required to present the homeomorphism type of upper X Subscript n $X_n$ X n . Along the way we investigate the computable aspects of Čech homology groups. We also show that no compact Polish space has a least presentation with respect to Turing reducibility.

Abstract We investigate computability theoretic and descriptive set theoretic contents of various kinds of analytic choice principles by performing a detailed analysis of the Medvedev lattice of $\Sigma ^1_1$ -closed sets. Among others, we solve an open problem on the Weihrauch degree of the parallelization of the $\Sigma ^1_1$ -choice principle on the integers. Harrington’s unpublished result on a jump hierarchy along a pseudo-well-ordering plays a key role in solving this problem.

Abstract We prove the Decomposability Conjecture for functions of Baire class $2$ from a Polish space to a separable metrizable space. This partially answers an important open problem in descriptive set theory.

Abstract There are close similarities between the Weihrauch lattice and the zoo of axiom systems in reverse mathematics. Following these similarities has often allowed researchers to translate results from one setting to the other. However, amongst the big five axiom systems from reverse mathematics, so far $\mathrm {ATR}_0$ has no identified counterpart in the Weihrauch degrees. We explore and evaluate several candidates, and conclude that the situation is complicated.

Abstract In this article, we study an analogue of tt -reducibility for points in computable metric spaces. We characterize the notion of the metric tt -degree in the context of first-level Borel isomorphism. Then, we study this concept from the perspectives of effective topological dimension theory and of effective fractal dimension theory.

In computable analysis testing a real number for being zero is a fundamental example of a non-computable task. This causes problems for division: We cannot ensure that the number we want to divide by is not zero. In many cases, any real number would be an acceptable outcome if the divisor is zero - but even this cannot be done in a computable way. In this note we investigate the strength of the computational problem Robust division: Given a pair of real numbers, the first not greater than the other, output their quotient if well-defined and any real number else. The formal framework is provided by Weihrauch reducibility. One particular result is that having later calls to the problem depending on the outcomes of earlier ones is strictly more powerful than performing all calls concurrently. However, having a nesting depths of two already provides the full power. This solves an open problem raised at a recent Dagstuhl meeting on Weihrauch reducibility. As application for Robust division, we show that it suffices to execute Gaussian elimination.

Every co-c.e. closed set (Π01 class) in Cantor space is represented by a co-c.e. tree. Our aim is to clarify the interaction between the Medvedev and Muchnik degrees of co-c.e. closed subsets of Cantor space and the Turing degrees of their co-c.e. representations. Among other results, we present the following theorems: if v and w are different c.e. degrees, then the collection of the Medvedev (Muchnik) degrees of all Π01 classes represented by v and the collection represented by w are also different; the ideals generated from such collections are also different; the collections of the Medvedev and Muchnik degrees of all Π01 classes represented by incomplete co-c.e. sets are upward dense; the collection of all Π01 classes represented by K-trivial sets is Medvedev-bounded by a single Π01 class represented by an incomplete co-c.e. set; and the Π01 classes have neither nontrivial infinite suprema nor infima in the Medvedev lattice.

We propose studying uniform Kurtz randomness, which is the uniform relativization of Kurtz randomness. This notion has more natural properties than the usual relativization. For instance, van Lambalgen's theorem holds for uniform Kurtz randomness but not for (the usual relativization of) Kurtz randomness. Another advantage is that lowness for uniform Kurtz randomness has many characterizations, such as those via complexity, martingales, Kurtz tt-traceability and Kurtz dimensional measure.