The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

SAS

Seminar

Resolute sets and initial segment complexity

Downey, R (Victoria University of Wellington)
Friday 06 July 2012, 16:00-17:00

Seminar Room 1, Newton Institute

Abstract

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.

Presentation

[pdf ]

Video

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.

Back to top ∧