Resolute sets and initial segment complexity

Duration: 56 mins 33 secs

About this item

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


Created:	2012-07-11 11:43
Collection:	Semantics and Syntax: A Legacy of Alan Turing
Publisher:	Isaac Newton Institute
Copyright:	Downey, R
Language:	eng (English)


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↑n)≥+K(A↑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.

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↑n)≥+K(A↑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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video	640x360	1.84 Mbits/sec	784.62 MB	View	Download
WebM	640x360	1.21 Mbits/sec	515.56 MB	View	Download
Flash Video	484x272	568.68 kbits/sec	235.54 MB	View	Download
iPod Video	480x270	506.18 kbits/sec	209.65 MB	View	Download
MP3	44100 Hz	125.0 kbits/sec	51.65 MB	Listen	Download
Auto *	(Allows browser to choose a format it supports)