A unifying approach to the Gamma question

作者:Monin Benoit*; Nies Andre
来源:Annual ACM/IEEE Symposium on Logic in Computer Science, 2015-07-06 To 2015-07-10.
DOI:10.1109/LICS.2015.60

摘要

The Gamma question was formulated by Andrews et al. in "Asymptotic density, computable traceability and 1-randomness" (2013, available at http://www.math.wisc.edu/similar to lempp/papers/traceable.pdf). It is related to the recent notion of coarse computability which stems from complexity theory. The Gamma value of an oracle set measures to what extent each set computable with the oracle is approximable, in the sense of density, by a computable set. The closer to 1 this value is, the closer the oracle is to being computable. The Gamma question asks whether this value can be strictly in between 0 and 1/2. We say that an oracle is weakly Schnorr engulfing if it computes a Schnorr test that succeeds on all computable reals. We show that each non weakly Schnorr engulfing oracle has a Gamma value of at least 1/2. Together with a recent result of Kjos-Hanssen, Stephan, and Terwijn, this establishes new examples of such oracles. We also give a unifying approach to oracles with Gamma value 0. We say that an oracle is infinitely often equal with bound h if it computes a function that agrees infinitely often with each computable function bounded by h. We show that every oracle which is infinitely equal with bound 2(dn) for d > 1 has a Gamma value of 0. This provides new examples of such oracles as well. We present a combinatorial characterization of being weakly Schnorr engulfing via traces, which is inspired by the study of cardinal characteristics in set theory.

  • 出版日期2015