Zobrazeno 1 - 10
of 68
pro vyhledávání: '"Day, Adam R."'
We define a family of three related reducibilities, $\leq_T$, $\leq_{tt}$ and $\leq_m$, for arbitrary functions $f,g:X\rightarrow\mathbb R$, where $X$ is a compact separable metric space. The $\equiv_T$-equivalence classes mostly coincide with the pr
Externí odkaz:
http://arxiv.org/abs/1906.07600
Autor:
Day, Adam R.
We develop the theory of algorithmic randomness for the space $A^G$ where $A$ is a finite alphabet and $G$ is a computable amenable group. We give an effective version of the Shannon-McMillan-Breiman theorem in this setting. We also extend a result o
Externí odkaz:
http://arxiv.org/abs/1802.03831
Autor:
Day, Adam R., Marks, Andrew S.
Publikováno v:
J. Symb. Log 82 (2018), 13-28
We investigate the class of bipartite Borel graphs organized by the order of Borel homomorphism. We show that this class is unbounded by finding a jump operator for Borel graphs analogous to a jump operator of Louveau for Borel equivalence relations.
Externí odkaz:
http://arxiv.org/abs/1604.02228
Autor:
Day, Adam R.
This paper uses the framework of reverse mathematics to investigate the strength of two recurrence theorems of topological dynamics. It establishes that one of these theorems, the existence of an almost periodic point, lies strictly between WKL and A
Externí odkaz:
http://arxiv.org/abs/1305.5858
Autor:
Bienvenu, Laurent, Day, Adam R., Greenberg, Noam, Kučera, Antonín, Miller, Joseph S., Nies, André, Turetsky, Dan
Every K-trivial set is computable from an incomplete Martin-L\"of random set, i.e., a Martin-L\"of random set that does not compute 0'.
Externí odkaz:
http://arxiv.org/abs/1305.5514
Autor:
Day, Adam R., Miller, Joseph S.
We present a notion of forcing that can be used, in conjunction with other results, to show that there is a Martin-L\"of random set X such that X does not compute 0' and X computes every K-trivial set.
Externí odkaz:
http://arxiv.org/abs/1304.2789
An infinite binary sequence A is absolutely undecidable if it is impossible to compute A on a set of positions of positive upper density. Absolute undecidability is a weakening of bi-immunity. Downey, Jockusch and Schupp asked whether, unlike the cas
Externí odkaz:
http://arxiv.org/abs/1210.4937
Autor:
Day, Adam R., Dzhafarov, Damir D.
Posner and Robinson (1981) proved that if $S \subseteq \omega$ is non-computable, then there exists a $G \subseteq \omega$ such that $S \oplus G \geq_T G'$. Shore and Slaman (1999) extended this result to all $n \in \omega$, by showing that if $S \nl
Externí odkaz:
http://arxiv.org/abs/1209.3282
Autor:
Day, Adam R., Reimann, Jan
Publikováno v:
Notre Dame J. Formal Logic 55, no. 1 (2014), 1-10
We study pairs of reals that are mutually Martin-L\"{o}f random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgen's Theorem holds for non-computable probability measures, too
Externí odkaz:
http://arxiv.org/abs/1207.2533
Autor:
Day, Adam R., Miller, Joseph S.
We prove that a set is K-trivial if and only if it is not weakly ML-cuppable. Further, we show that a set below zero jump is K-trivial if and only if it is not ML-cuppable. These results settle a question of Ku\v{c}era, who introduced both cuppabilit
Externí odkaz:
http://arxiv.org/abs/1206.1603