Initial segment complexities of randomness notions

Schnorr famously proved that Martin-Löf-randomness of a sequence A can be characterised via the complexity of A ʼs initial segments. Nies, Stephan and Terwijn as well as independently Miller showed that a set is 2-random (that is, Martin-Löf random relative to the halting problem K ) iff there i...

Full description

Bibliographic Details
Main Authors: Hölzl, Rupert, Kräling, Thorsten, Stephan, Frank, Wu, Guohua
Other Authors: School of Physical and Mathematical Sciences
Format: Journal Article
Language:English
Published: 2014
Subjects:
Online Access:https://hdl.handle.net/10356/103751
http://hdl.handle.net/10220/19262