6 papers
Chains and antichains in the Weihrauch lattice
Steffen Lempp, Alberto Marcone, Manlio Valenti
We study the existence and the distribution of "long" chains in the Weihrauch degrees, mostly focusing on chains with uncountable cofinality. We characterize when such chains have…
The weakness of finding descending sequences in ill-founded linear orders
Jun Le Goh, Arno Pauly, Manlio Valenti
We explore the Weihrauch degree of the problems ``find a bad sequence in a non-well quasi order'' () and ``find a descending sequence in an ill-founded linear order''…
Computably discrete represented spaces
Eike Neumann, Arno Pauly, Cécilia Pradic +1
In computable topology, a represented space is called computably discrete if its equality predicate is semidecidable. While any such space is classically isomorphic to an initial s…
Categorifying computable reducibilities
Davide Trotta, Manlio Valenti, Valeria de Paiva
This paper presents categorical formulations of Turing, Medvedev, Muchnik, and Weihrauch reducibilities in Computability Theory, utilizing Lawvere doctrines. While the first notion…
The tree pigeonhole principle in the Weihrauch degrees
Damir Dzhafarov, Reed Solomon, Manlio Valenti
We study versions of the tree pigeonhole principle, , in the context of Weihrauch-style computable analysis. The principle has previously been the subject of extensi…
A jump operator on the Weihrauch degrees
Uri Andrews, Steffen Lempp, Alberto Marcone +2
A partial order admits a jump operator if there is a map that is strictly increasing and weakly monotone. Despite its name, the jump in the Weihrauch la…