Ian Herbert: Weak Lowness Notions and Weak Reducibilities

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.

Leave a Reply

Your email address will not be published. Required fields are marked *