# Logic Seminar, Bill Calhoun (Bloomsburg University): "Triviality and lowness for K-reducibility and related reducibilities"

Monday, November 9, 2015
4:45 PM - 6:00 PM (ET)
Exley Science Center (Tower)
Event Type
Seminar/Colloquium
Contact
Caryn Canalia
Department
Mathematics and Computer Science
https://eaglet.wesleyan.edu/MasterCalendar/EventDetails.aspx?EventDetailId=65647

n 2 !, where K is prefix-free Kolmogorov complexity. The set A is low

for K if KA(y) = K(y)+O(1) for y 2 2<!. These definitions seem quite

different. K-triviality indicates that initial segments of A have the lowest

possible complexity, while lowness for K indicates that A is too weak as

an oracle to reduce the complexity of any string. The remarkable equivalence

of the two definitions was shown by Nies [2]. Replacing prefix-free

complexity by monotone complexity in the definition of K-trivial, we obtain

the Km-trivial sets. Every K-trivial set is Km-trivial and all Turing

degrees _ 00 contain a Km-trivial set [1]. Yet, not every Turing degree

contains a Km-trivial set. We obtain a superset of the Km-trivial sets by

defining A to be almost-K-trivial if there is a real number a such that

K(A _ n) _+ aK(n). Every Km-trivial set is almost-K-trivial. However,

the Turing degree of a computably dominated ML-random cannot contain

any almost-K-trivial set. An interesting question is to determine

which Turing degrees contain Km-trivial sets (or almost-K-trivial sets).

Recently, this question has been considered for minimal Turing degrees.

We also consider lowness for monotone and a priory complexity.

References

1. Calhoun, W.C.: Triviality and minimality in the degrees of monotone complexity,

Journal of Logic and Computation 22, 197-206 (2012).

2. Nies, Andr´e: Lowness properties and randomness, Advances in Mathematics

197, 274-305 (2005).