Wolfgang Merkle: Being low for K along sequences and elsewhere

Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 02 March 2016, 17:00 hrs

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

Speaker: Wolfgang Merkle, University of Heidelberg

Title: Being low for K along sequences and elsewhere

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

Abstract:
Given a set D of strings, say a sequence X is low for prefix-free
Kolmogorov complexity K on D in case access to X as an oracle does not
improve the prefix-free complexity of any string in D by more than an
additive constant. Furthermore, say X is weakly low for K on D in case
X is low for K on some, then necessarily infinite, subset of D. The
usual notions of being low for K and being weakly low for K are
obtained by letting D be equal to the set of all strings. We
investigate into the question what can be said about sequences that
are low for K or weakly low for K on specific sets of strings, e.g.,
on the set of initial segments of some sequence. Accordingly, say X is
low or weakly low for K along a sequence A in case X is low or weakly
low, respectively, for K on the set of initial segments of A. More
specifically, for an infinite subset I of the natural numbers, say X
is low or weakly low for K along A on I in case X is low or weakly
low, respectively, for K on the set of initial segments of A with
length in I.
Among others, we demonstrate the following results. If a sequence X is
not low for K, then for any sequence A and any infinite computable set
I, the sequence X is not low along A on I. As an immediate corollary,
a sequence X is low for K if and only if X is low along all sequences
on all infinite computable sets if and only if X is low along some
sequence on some infinite computable set. Furthermore, in case a
sequence X is weakly low for K, then X is weakly low along almost all
sequences (in the sense of Lebesgue measure). Hence X is weakly low
for K if and only if X is weakly low for K along almost all sequences
if and only if X is weakly low for K along some sequence. Finally, for
any infinite set D of strings, the set of sequences X such that X is
low for K on D has measure 0 whereas the set of sequences X such that
X is weakly low for K on D has measure 1.

This is joint work with Yu Liang and was presented at CCR 2016.

Leave a Reply

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

Time limit is exhausted. Please reload CAPTCHA.