Title: Preservation of randomness and genericity under symmetric differences
Abstract:
Title: Preservation of randomness and genericity under symmetric differences
Abstract:
Given a class $\mathcal U$ of subsets of the natural numbers, let us say that a subset $A$ of the natural numbers is $\mathcal U$-stabilising if the symmetric difference (or bitwise addition) $A+X$ of $A$ and $X$ is an element of $\mathcal U$ for every element $X$ of $\mathcal U$.
Several people have asked, using varying terminology, to characterise the Martin-Löf-stabilising sets, i.e. the sets $A$ such that $X+A$ is Martin-Löf random for every Martin-Löf random set $X$. We show that the Martin-Löf-stabilising sets are exactly the $K$-trivial sets.
We also show that the 1-generic-stabilising sets are exactly the computable sets, using an argument which (surprisingly) makes use of Kolmogorov complexity and facts about the $K$-trivial sets.
Joint work with Joseph S. Miller
Title: Being low for $\mathrm{K}$ along sequences and elsewhere
Abstract:
Given a set $D$ of strings, say a sequence $X$ is low for prefix-free Kolmogorov complexity $\mathrm{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 $\mathrm{K}$ on $D$ in case $X$ is low for $\mathrm{K}$ on some, then necessarily infinite, subset of $D$. The usual notions of being low for $\mathrm{K}$ and being weakly low for $\mathrm{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 $\mathrm{K}$ or weakly low for $\mathrm{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 $\mathrm{K}$ along a sequence $A$ in case $X$ is low or weakly low, respectively, for $\mathrm{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 $\mathrm{K}$ along $A$ on $I$ in case $X$ is low or weakly low, respectively, for $\mathrm{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 $\mathrm{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 $\mathrm{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 $\mathrm{K}$, then $X$ is weakly low along almost all sequences (in the sense of Lebesgue measure). Hence $X$ is weakly low for $\mathrm{K}$ if and only if $X$ is weakly low for $\mathrm{K}$ along almost all sequences if and only if X is weakly low for $\mathrm{K}$ along some sequence. Finally, for any infinite set $D$ of strings, the set of sequences $X$ such that $X$ is low for $\mathrm{K}$ on $D$ has measure 0 whereas the set of sequences $X$ such that $X$ is weakly low for $\mathrm{K}$ on $D$ has measure 1.
Joint work with Liang Yu.
Title: Randomness for Computable Measures and Initial Segment Complexity
Joint work with Christopher P. Porter.
Title: The complexity of free abelian groups
Abstract:
Vector spaces are defined by a set of first-order axioms; the theorem every vector space has a basis is second-order, but is a consequence of these axioms.
In contrast, free abelian groups are typically defined by having a basis.
It is then natural to wonder if free abelian groups could also be defined by some set of first-order axioms.
A negative answer might take the form of a theorem that the index set of computable free abelian groups is not arithmetic.
Unfortunately, this theorem is false, at least in standard computability theory.
It can be rescued, however, by moving to uncountable computability theory.