70 citations · 229 across the 50 of their papers we have counts for
6 papers · 1 filter
An additivity theorem for plain Kolmogorov complexity
Bruno Bauwens, Alexander Shen
We prove the formula C(a,b) = K(a|C(a,b)) + C(b|a,C(a,b)) + O(1) that expresses the plain complexity of a pair in terms of prefix and plain conditional complexities of its componen…
Random semicomputable reals revisited
Laurent Bienvenu, Alexander Shen
The aim of this expository paper is to present a nice series of results, obtained in the papers of Chaitin (1976), Solovay (1975), Calude et al. (1998), Kucera and Slaman (2001). T…
Are random axioms useful?
Alexander Shen
The famous Gödel incompleteness theorem says that for every sufficiently rich formal theory (containing formal arithmetic in some natural sense) there exist true unprovable stateme…
Probability-free pricing of adjusted American lookbacks
A. Philip Dawid, Steven de Rooij, Peter Grunwald +5
Consider an American option that pays G(X^*_t) when exercised at time t, where G is a positive increasing function, X^*_t := \sup_{s\le t}X_s, and X_s is the price of the underlyin…
Algorithmic tests and randomness with respect to a class of measures
Laurent Bienvenu, Peter Gacs, Mathieu Hoyrup +2
The paper considers quantitative versions of different randomness notions: algorithmic test measures the amount of non-randomness (and is infinite for non-random sequences). We sta…
Kolmogorov complexity as a language
Alexander Shen
The notion of Kolmogorov complexity (=the minimal length of a program that generates some object) is often useful as a kind of language that allows us to reformulate some notions a…