Zobrazeno 1 - 10
of 625
pro vyhledávání: '"03D30"'
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 an upper bound and prove that there are no cofinal chains (of any orde
Externí odkaz:
http://arxiv.org/abs/2411.07792
Autor:
Titov, Ivan
Solovay reducibility $\redsolovay$ was introduced by Robert M. Solovay in 1975 via translation functions on rationals. In 2022, its totalized version $\redsolovaytotal$ (i.e., Solovay reducibility via a total function on rationals) has been examined
Externí odkaz:
http://arxiv.org/abs/2410.15563
Autor:
Marcone, Alberto, Osso, Gian Marco
This paper classifies different fragments of the Galvin-Prikry theorem, an infinite dimensional generalization of Ramsey's theorem, in terms of their uniform computational content (Weihrauch degree). It can be seen as a continuation of arXiv:2003.042
Externí odkaz:
http://arxiv.org/abs/2410.06928
Autor:
Li, Ang
This paper continues to study the connection between reverse mathematics and Weihrauch reducibility. In particular, we study the problems formed from Maltsev's theorem on the order types of countable ordered groups. Solomon showed that the theorem is
Externí odkaz:
http://arxiv.org/abs/2409.19229
Autor:
Andrews, Uri, Mauro, Luca San
Coskey, Hamkins, and Miller [CHM12] proposed two possible analogues of the class of countable Borel equivalence relations in the setting of computable reducibility of equivalence relations on the computably enumerable (c.e.) sets. The first is based
Externí odkaz:
http://arxiv.org/abs/2409.17018
Autor:
Lau, Desmond
Fix a set-theoretic universe $V$. We look at small extensions of $V$ as generalised degrees of computability over $V$. We also formalise and investigate the complexity of certain methods one can use to define, in $V$, subclasses of degrees over $V$.
Externí odkaz:
http://arxiv.org/abs/2409.03441
Autor:
Li, Ang
An infinite binary sequence is Bennett deep if, for any computable time bound, the difference between the time-bounded prefix-free Kolmogorov complexity and the prefix-free Kolmogorov complexity of its initial segments is eventually unbounded. It is
Externí odkaz:
http://arxiv.org/abs/2409.00631
Autor:
Pradic, Cécilia
We study the equational theory of the Weihrauch lattice with composition and iterations, meaning the collection of equations between terms built from variables, the lattice operations $\sqcup$, $\sqcap$, the composition operator $\star$ and its itera
Externí odkaz:
http://arxiv.org/abs/2408.14999
Autor:
Titov, Ivan
The original notion of Solovay reducibility was introduced by Robert M. Solovay (unpublished notes) in 1975 as a measure of relative randomness. The S2a-reducibility introduced by Xizhong Zheng and Robert Rettinger (DOI:10.1007/978-3-540-27798-9_39)
Externí odkaz:
http://arxiv.org/abs/2408.04074
Autor:
Merkle, Wolfgang, Titov, Ivan
While the set of Martin-L\"of random left-c.e. reals is equal to the maximum degree of Solovay reducibility, Miyabe, Nies and Stephan(DOI:10.4115/jla.2018.10.3) have shown that the left-c.e. Schnorr random reals are not closed upwards under Solovay r
Externí odkaz:
http://arxiv.org/abs/2407.14869