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.