Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 12 March 2014, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Ian Herbert

Title: Weak Lowness Notions and Weak Reducibilities

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Abstract: The prefix-free Kolmogorov complexity of a finite binary string

is the length of the shortest description of the string, according to some

universal decoding machine. This gives rise to some `standard’ lowness

notions for reals: A is K-trivial if its initial segments have the

lowest possible complexity and A is low for K if using A as an oracle

does not decrease the complexity of strings by more than a constant

factor. We discuss various ways of weakening these notions and the

relations among these weakenings and between them and standard

notions. We also discuss how these notions behave under reducibilities

that are based on Kolmogorov complexity and are weaker than Turing

reducibility.