skip to content

Resolute sets and initial segment complexity

Presented by: 
R Downey Victoria University of Wellington
Friday 6th July 2012 - 16:00 to 17:00
INI Seminar Room 1
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 degrees. Our investigations are only just beginning and I will report on our progress. Joint work with George Barmpalias.
The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons