42 citations · 57 across the 11 of their papers we have counts for
14 papers
Independence and Induction in Reverse Mathematics
David Belanger, Chi Tat Chong, Rupert Hölzl +1
We continue the project of the study of reverse mathematics principles inspired by cardinal invariants. In this article in particular we focus on principles encapsulating the exist…
Randomness versus superspeedability
Rupert Hölzl, Philip Janicki, Wolfgang Merkle +1
Speedable numbers are real numbers which are algorithmically approximable from below and whose approximations can be accelerated nonuniformly. We begin this article by answering a…
Benign approximations and non-speedability
Rupert Hölzl, Philip Janicki
A left-computable number is called regainingly approximable if there is a computable increasing sequence of rational numbers converging to such that $x - x_n < 2^…
Regainingly approximable numbers and sets
Peter Hertling, Rupert Hölzl, Philip Janicki
We call an regainingly approximable if there exists a computable nondecreasing sequence of rational numbers converging to with for…
Computable classifications of continuous, transducer, and regular functions
Johanna N. Y. Franklin, Rupert Hölzl, Alexander Melnikov +2
We develop a systematic algorithmic framework that unites global and local classification problems using index sets. We prove that the classification problem for continuous (binary…
Degrees of Randomized Computability
Rupert Hölzl, Christopher P. Porter
In this survey we discuss work of Levin and V'yugin on collections of sequences that are non-negligible in the sense that they can be computed by a probabilistic algorithm with pos…
Rank and randomness
Rupert Hölzl, Christopher P. Porter
We show that for each computable ordinal it is possible to find in each Martin-Löf random degree a sequence of Cantor-Bendixson rank , while ensuring that the…
The Vitali Covering Theorem in the Weihrauch Lattice
Vasco Brattka, Guido Gherardi, Rupert Hölzl +1
We study the uniform computational content of the Vitali Covering Theorem for intervals using the tool of Weihrauch reducibility. We show that a more detailed picture emerges than…
Randomness for computable measures and initial segment complexity
Rupert Hölzl, Christopher P. Porter
We study the possible growth rates of the Kolmogorov complexity of initial segments of sequences that are random with respect to some computable measure on , the so-called pro…
Universality, optimality, and randomness deficiency
Rupert Hölzl, Paul Shafer
A Martin-Löf test is universal if it captures all non-Martin-Löf random sequences, and it is optimal if for every ML-test there is a such that $…
On Martin's Pointed Tree Theorem
Rupert Hölzl, Frank Stephan, Liang Yu
We investigate the reverse mathematics strength of Martin's pointed tree theorem (MPT) and one of its variants, weak Martin's pointed tree theorem (wMPT).
Probabilistic Computability and Choice
Vasco Brattka, Guido Gherardi, Rupert Hölzl
We study the computational power of randomized computations on infinite objects, such as real numbers. In particular, we introduce the concept of a Las Vegas computable multi-value…
Randomness and Semi-measures
Laurent Bienvenu, Rupert Hölzl, Christopher P. Porter +1
A semi-measure is a generalization of a probability measure obtained by relaxing the additivity requirement to super-additivity. We introduce and study several randomness notions f…
Denjoy, Demuth, and Density
Laurent Bienvenu, Rupert Hölzl, Joseph S. Miller +1
We consider effective versions of two classical theorems, the Lebesgue density theorem and the Denjoy-Young-Saks theorem. For the first, we show that a Martin-Loef random real $z\i…