Initial segment complexities of randomness notions

• Main Authors: Hölzl, Rupert, Kräling, Thorsten, Stephan, Frank, Wu, Guohua
• Other Authors: School of Physical and Mathematical Sciences
• Format: Article
• Language: English
• Published: 2014
• Subjects: DRNTU::Science::Mathematics
• Online Access: https://hdl.handle.net/10356/103751; http://hdl.handle.net/10220/19262
• Institution: Nanyang Technological University

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...