3 citations · 6 across the 6 of their papers we have counts for
8 papers
Statman's Hierarchy Theorem
Bram Westerbaan, Bas Westerbaan, Rutger Kuyper +3
In the Simply Typed -calculus Statman investigates the reducibility relation between types: for , types freely generated using an…
On Weihrauch Reducibility and Intuitionistic Reverse Mathematics
Rutger Kuyper
We show that there is a strong connection between Weihrauch reducibility on one hand, and provability in EL_0, the intuitionistic version of RCA_0, on the other hand. More precisel…
Levels of uniformity
Rutger Kuyper
We introduce a hierarchy of degree structures between the Medvedev and Muchnik lattices which allow varying amounts of non-uniformity. We use these structures to introduce the noti…
Coarse Reducibility and Algorithmic Randomness
Denis R. Hirschfeldt, Carl G. Jockusch, Rutger Kuyper +1
A coarse description of a subset A of omega is a subset D of omega such that the symmetric difference of A and D has asymptotic density 0. We study the extent to which noncomputabl…
First-order logic in the Medvedev lattice
Rutger Kuyper
Kolmogorov introduced an informal calculus of problems in an attempt to provide a classical semantics for intuitionistic logic. This was later formalised by Medvedev and Muchnik as…
Natural Factors of the Medvedev Lattice Capturing IPC
Rutger Kuyper
Skvortsova showed that there is a factor of the Medvedev lattice which captures intuitionistic propositional logic (IPC). However, her factor is unnatural in the sense that it is c…
Effective Genericity and Differentiability
Rutger Kuyper, Sebastiaan A. Terwijn
We prove that a real x is 1-generic if and only if every differentiable computable function has continuous derivative at x. This provides a counterpart to recent results connecting…
Natural Factors of the Muchnik Lattice Capturing IPC
Rutger Kuyper
We give natural examples of factors of the Muchnik lattice which capture intuitionistic propositional logic (IPC), arising from the concepts of lowness, 1-genericity, hyperimmune-f…