Information measures for infinite sequences

We revisit the notion of computational depth and sophistication for infinite sequences and study the density of the sets of deep and sophisticated infinite sequences. Koppel defined the sophistication of an object as the length of the shortest total program that, given some data as input, produces the object and such that the sum of the size of the program with the size of the data is as concise as the smallest description of the object. However, the notion of sophistication is not properly defined for all sequences. We propose a new definition of sophistication for infinite sequences as the limit of the ratio of the sophistication of the initial segments and its length. We prove that the set of sequences with sophistication equal to zero has Lebesgue measure one and that the set of sophisticated sequences is dense, when the sophistication is, respectively, defined either using lim inf or lim sup. Antunes, Fortnow, van Melkebeek and Vinodchandran captured the notion of useful information by computational depth, the difference between time bounded and unbounded Kolmogorov complexities. We show that the set of deep infinite sequences is dense. We also prove that sophistication and depth for infinite sequences are distinct information measures.