Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Sophisticated Infinite Sequences

Edit abstract data

Author(s): Luis Antunes and André Souto
Slot: Mon, 12:00-12:20, Senate (col. 3)


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.

websites: Arnold Beckmann 2008-05-19 Valid HTML 4.01! Valid CSS!