5 papers
Bishop's (up)crossing inequality and lower semicomputable random reals revisited
Mikhail Andreev, Alexander Shen
In this paper we provide an easy proof of Barmpalias--Lewis-Pye result saying that all computable increasing sequences converging to random reals converge with the same speed (up t…
Plain stopping time and conditional complexities revisited
Mikhail Andreev, Gleb Posobin, Alexander Shen
In this paper we analyze the notion of "stopping time complexity", informally defined as the amount of information needed to specify when to stop while reading an infinite sequence…
Busy beavers and Kolmogorov complexity
Mikhail Andreev
The idea to find the "maximal number that can be named" can be traced back to Archimedes (see his Psammit). From the viewpoint of computation theory the natural question is "which…
The sum over all prefixes of some binary sequence can be infinite
Mikhail Andreev, Akim Kumok
We consider two quantities that measure complexity of binary strings: is defined as the minus logarithm of continuous a priori probability on the binary tree, and…
Not Every Domain of a Plain Decompressor Contains the Domain of a Prefix-Free One
Mikhail Andreev, Ilya Razenshteyn, Alexander Shen
C.Calude, A.Nies, L.Staiger, and F.Stephan posed the following question about the relation between plain and prefix Kolmogorov complexities (see their paper in DLT 2008 conference…