Abstract:
The author investigates properties of infinite binary sequences that are invariant relative to algorithmic equivalence of sequences. Any two properties that differ on a set for which some natural measure is equal to 0 are identified with one another. It is shown that the class of all computable subsequences and the class of all random subsequences cannot be separated into nontrivial subclasses by such properties. The principal technical results of the paper are associated with the study of the invariant properties that may be possessed by noncomputable sequences that are algorithmically not equivalent to any random sequences.
Fulltext:
PDF file (2253 kB)