Computer Science – Information Theory
Scientific paper
2008-02-04
Computer Science
Information Theory
Scientific paper
Two objects are independent if they do not affect each other. Independence is well-understood in classical information theory, but less in algorithmic information theory. Working in the framework of algorithmic information theory, the paper proposes two types of independence for arbitrary infinite binary sequences and studies their properties. Our two proposed notions of independence have some of the intuitive properties that one naturally expects. For example, for every sequence $x$, the set of sequences that are independent (in the weaker of the two senses) with $x$ has measure one. For both notions of independence we investigate to what extent pairs of independent sequences, can be effectively constructed via Turing reductions (from one or more input sequences). In this respect, we prove several impossibility results. For example, it is shown that there is no effective way of producing from an arbitrary sequence with positive constructive Hausdorff dimension two sequences that are independent (even in the weaker type of independence) and have super-logarithmic complexity. Finally, a few conjectures and open questions are discussed.
Calude Cristian
Zimand Marius
No associations
LandOfFree
Algorithmically independent sequences does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Algorithmically independent sequences, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Algorithmically independent sequences will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-44925