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...
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 |
Similar Items
-
A new notion of weighted centers for semidefinite programming
by: Chua, Chek Beng.
Published: (2009) -
Nonhemimaximal degrees and the high/low hierarchy
by: Fang, Chengling, et al.
Published: (2013) -
On a problem of Ishmukhametov
by: Yamaleev, Mars, et al.
Published: (2014) -
ω-change randomness and weak demuth randomness
by: Franklin, Johanna N. Y., et al.
Published: (2015) -
Critical events detection and management in complex networks
by: Yu, Yi
Published: (2016)