Arrow Research search

Author name cluster

Thorsten Kräling

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
2 author rows

Possible papers

2

I&C Journal 2014 Journal Article

Initial segment complexities of randomness notions

  • Rupert Hölzl
  • Thorsten Kräling
  • Frank Stephan
  • Guohua Wu

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 is no function f such that for all m and all n > f ( m ) it holds that C ( A ( 0 ) A ( 1 ) … A ( n ) ) ⩽ n − m; before the proof of this equivalence the notion defined via the latter condition was known as Kolmogorov random. In the present work it is shown that characterisations of this style can also be given for other randomness criteria like strong randomness (also known as weak 2-randomness), Kurtz randomness relative to K, Martin-Löf randomness of PA-incomplete sets, and strong Kurtz randomness; here one does not just quantify over all functions f but over functions f of a specific form. For example, A is Martin-Löf random and PA-incomplete iff there is no A-recursive function f such that for all m and all n > f ( m ) it holds that C ( A ( 0 ) A ( 1 ) … A ( n ) ) ⩽ n − m. The characterisation for strong randomness relates to functions which are the concatenation of an A-recursive function executed after a K-recursive function; this solves an open problem of Nies. In addition to this, characterisations of a similar style are also given for Demuth randomness, weak Demuth randomness and Schnorr randomness relative to K. Although the unrelativised versions of Kurtz randomness and Schnorr randomness do not admit such a characterisation in terms of plain Kolmogorov complexity, Bienvenu and Merkle gave one in terms of Kolmogorov complexity defined by computable machines.

Details DOI

MFCS Conference 2009 Conference Paper

Time-Bounded Kolmogorov Complexity and Solovay Functions

  • Rupert Hölzl 0001
  • Thorsten Kräling
  • Wolfgang Merkle

Abstract A Solovay function is a computable upper bound g for prefix-free Kolmogorov complexity K that is nontrivial in the sense that g agrees with K, up to some additive constant, on infinitely many places n. We obtain natural examples of Solovay functions by showing that for some constant c 0 and all computable functions t such that c 0 n ≤ t ( n ), the time-bounded version K t of K is a Solovay function. By unifying results of Bienvenu and Downey and of Miller, we show that a right-computable upper bound g of K is a Solovay function if and only if Ω g is Martin-Löf random. Letting \(\mathrm{\Omega}_g=\sum 2^{-g(n)}\), we obtain as a corollary that the Martin-Löf randomness of the various variants of Chaitin’s Ω extends to the time-bounded case in so far as \(\mathrm{\Omega}_{K^t}\) is Martin-Löf random for any t as above. As a step in the direction of a characterization of K -triviality in terms of jump-traceability, we demonstrate that a set A is K-trivial if and only if A is Og ( n ) − K ( n )-jump traceable for all Solovay functions g, where the equivalence remains true when we restrict attention to functions g of the form K t, either for a single or all functions t as above. Finally, we investigate the plain Kolmogorov complexity C and its time-bounded variant C t of initial segments of computably enumerable sets. Our main theorem here is a dichotomy similar to Kummer’s gap theorem and asserts that every high c. e. Turing degree contains a c. e. set B such that for any computable function t there is a constant c t > 0 such that for all m it holds that C \(^t(B\upharpoonright m) \geq c_t \cdot m\), whereas for any nonhigh c. e. set A there is a computable time bound t and a constant c such that for infinitely many m it holds that C \(^t(A\upharpoonright m) \leq \log m + c\). By similar methods it can be shown that any high degree contains a set B such that C \(^t(B\upharpoonright m) \geq^+ m/4\). The constructed sets B have low unbounded but high time-bounded Kolmogorov complexity, and accordingly we obtain an alternative proof of the result due to Juedes, Lathrop, and Lutz [JLL] that every high degree contains a strongly deep set.

Details
v2026.09.13