RELATIONS BETWEEN VARIETIES OF KOLMOGOROV COMPLEXITIES

There are several sorts of Kolmogorov complexity, better to say severa l Kolmogorov complexities: decision complexity, simple complexity, pre fix complexity, monotonic complexity, a priori complexity. The last th ree can and the first two cannot be used for defining randomness of an infinite binary sequence. All those five versions of Kolmogorov compl exity were considered, from a unified point of view, in a paper by the first author which appeared in Watanabe's book [23]. Upper and lower bounds for those complexities and also for their differences were anno unced in that paper without proofs. (Some of those bounds are mentione d in Section 4.4.5 of [16].) The purpose of this paper (which can be r ead independently of [23]) is to give proofs for the bounds from [23]. The terminology used in this paper is somehow nonstandard: we call '' Kolmogorov entropy'' what is usually called ''Kolmogorov complexity.'' This is a Moscow tradition suggested by Kolmogorov himself. By this t radition the term ''complexity'' relates to any mode of description an d ''entropy'' is the complexity related to an optimal mode (i.e., to a mode that, roughly speaking, gives the shortest descriptions).