Edit abstract data
In this paper we revisit the notion of sophistication for infinite sequences.
Koppel defined sophistication of an object as the length of the shortest
(finite) total program (p) that with some (finite or infinite) data (d) produce
it and |p|+|d| is smaller than the shortest description of the object plus a
constant. However the notion of ``description of infinite sequences''
is not appropriately defined. In this work, we propose a new definition of
sophistication for infinite sequences as the ratio between sophistication of the
initial segments and its length. As the main result we prove that highly
sophisticated sequences are dense when the sophistication is defined with limsup
and are rare when we consider the liminf. We also prove that, similarly to what
happens for finite strings, sophistication and depth, for infinite sequences are
distinct complexity measures.