Resolute sets and initial segment complexity
Seminar Room 1, Newton Institute
Notions of triviality have been remarkably productive in algorithmic
randomness,with $K$-triviality being the most notable. Of course,
ever since the original characterization of Martin-Löf randomness
by initial segment complexity, there has been a longstanding interplay
between initial segment complexity and calibrations of randomness,
as witnessed by concepts such as autocomplexity, and the like.
In this talk I wish to discuss recent work with George Barmpalias on a
triviality notion we call resoluteness
. Resoluteness is defined in
terms of computable shifts by is intimately related to a notion we call
weak resoluteness where $A$ is weakly resolute iff for all computable
orders $h$, $K(A\uparrow n) \ge^+ K(A\uparrow h(n)), $ for all $n$. It
is not difficult to see that $K$-trivials have this property but it
turns out that there are uncountablly many degrees which are completely
$K$-resolute, and there are c.e. degrees also with this property.
These degrees seem related to Lathrop-Lutz ultracompressible
Our investigations are only just beginning and I will report on our progress.
Joint work with George Barmpalias.